Dénombrement de permutations.

[invite332de63a]

Bonjour à tous,

lors des surveillances du bac, lors de la récupération des copies, je procédais ainsi:

je récupère les copies et les organise dans l'ordre alphabétique en faisant des tas. Chaque tas est composé de copies voisines, c'est à dire des copies qui se suivent directement dans l'ordre alphabétique. Lors de la récupération de chaque copie, on compte le nombre de tas présents sur la table.

Pour formaliser tout cela, s'il y a n élèves, l'ordre de ramassage des copies est donné par une permutation de , pour tout i, est le rang de l'élève de la ième copie ramassée. On appelle fonction de tas la fonction définie sur dans l'ensemble des fonction de sur par est égal au nombre de composantes connexes (maximales) de , un ensemble connexe étant ici un ensemble d'entiers successifs comme .

Pour étudier tout cela, j'ai programmer sur Maple un algorithme permettant de générer toutes les permutations de pour un n donné qui pour chacune d'entre elle calcule le nombre de tas sous la forme d'une liste et compte le nombre de fois ce tas est apparu au paravent. Les résultats obtenus sont donnés sous la forme d'une liste d'éléments de la forme ce qui signifie qu'il y avait k permutations telles que pour tout i de 1 à n, . De plus, je lui ai fait calculer la somme des nombres moyens de tas par permutation multiplié par n, ce résultat est donné avant la liste par la valeur de m. Voici les résultats obtenus pour n allant de 1 à 7 (maple ne voulant pas poursuivre après 7 car ma liste étant trop grande...):


Pour n=1, m= 1, [1, [1]]

Pour n=2, m=4, [2, [1, 1]]

Pour n=3, m=10, [4, [1, 1, 1]], [2, [1, 2, 1]]

Pour n=4, m=20, [8, [1, 1, 1, 1]], [4, [1, 1, 2, 1]], [8, [1, 2, 2, 1]], [4, [1, 2, 1, 1]]

Pour n=5, m=35, [16, [1, 1, 1, 1, 1]], [8, [1, 1, 1, 2, 1]], [16, [1, 1, 2, 2, 1]], [8, [1, 1, 2, 1, 1]], [32, [1, 2, 2, 2, 1]], [16, [1, 2, 2, 1, 1]], [12, [1, 2, 3, 2, 1]], [8, [1, 2, 1, 1, 1]], [4, [1, 2, 1, 2, 1]]

Pour n=6, m=56, [32, [1, 1, 1, 1, 1, 1]], [16, [1, 1, 1, 1, 2, 1]], [32, [1, 1, 1, 2, 2, 1]], [16, [1, 1, 1, 2, 1, 1]], [64, [1, 1, 2, 2, 2, 1]], [32, [1, 1, 2, 2, 1, 1]], [24, [1, 1, 2, 3, 2, 1]], [16, [1, 1, 2, 1, 1, 1]], [8, [1, 1, 2, 1, 2, 1]], [128, [1, 2, 2, 2, 2, 1]], [64, [1, 2, 2, 2, 1, 1]], [48, [1, 2, 2, 3, 2, 1]], [32, [1, 2, 2, 1, 1, 1]], [16, [1, 2, 2, 1, 2, 1]], [72, [1, 2, 3, 3, 2, 1]], [24, [1, 2, 3, 2, 1, 1]], [48, [1, 2, 3, 2, 2, 1]], [16, [1, 2, 1, 1, 1, 1]], [8, [1, 2, 1, 1, 2, 1]], [16, [1, 2, 1, 2, 2, 1]], [8, [1, 2, 1, 2, 1, 1]]

Pour n=7, m=84, [64, [1, 1, 1, 1, 1, 1, 1]], [32, [1, 1, 1, 1, 1, 2, 1]], [64, [1, 1, 1, 1, 2, 2, 1]], [32, [1, 1, 1, 1, 2, 1, 1]], [128, [1, 1, 1, 2, 2, 2, 1]], [64, [1, 1, 1, 2, 2, 1, 1]], [48, [1, 1, 1, 2, 3, 2, 1]], [32, [1, 1, 1, 2, 1, 1, 1]], [16, [1, 1, 1, 2, 1, 2, 1]], [256, [1, 1, 2, 2, 2, 2, 1]], [128, [1, 1, 2, 2, 2, 1, 1]], [96, [1, 1, 2, 2, 3, 2, 1]], [64, [1, 1, 2, 2, 1, 1, 1]], [32, [1, 1, 2, 2, 1, 2, 1]], [144, [1, 1, 2, 3, 3, 2, 1]], [48, [1, 1, 2, 3, 2, 1, 1]], [96, [1, 1, 2, 3, 2, 2, 1]], [32, [1, 1, 2, 1, 1, 1, 1]], [16, [1, 1, 2, 1, 1, 2, 1]], [32, [1, 1, 2, 1, 2, 2, 1]], [16, [1, 1, 2, 1, 2, 1, 1]], [512, [1, 2, 2, 2, 2, 2, 1]], [256, [1, 2, 2, 2, 2, 1, 1]], [192, [1, 2, 2, 2, 3, 2, 1]], [128, [1, 2, 2, 2, 1, 1, 1]], [64, [1, 2, 2, 2, 1, 2, 1]], [288, [1, 2, 2, 3, 3, 2, 1]], [96, [1, 2, 2, 3, 2, 1, 1]], [192, [1, 2, 2, 3, 2, 2, 1]], [64, [1, 2, 2, 1, 1, 1, 1]], [32, [1, 2, 2, 1, 1, 2, 1]], [64, [1, 2, 2, 1, 2, 2, 1]], [32, [1, 2, 2, 1, 2, 1, 1]], [432, [1, 2, 3, 3, 3, 2, 1]], [144, [1, 2, 3, 3, 2, 1, 1]], [288, [1, 2, 3, 3, 2, 2, 1]], [144, [1, 2, 3, 4, 3, 2, 1]], [48, [1, 2, 3, 2, 1, 1, 1]], [24, [1, 2, 3, 2, 1, 2, 1]], [192, [1, 2, 3, 2, 2, 2, 1]], [96, [1, 2, 3, 2, 2, 1, 1]], [72, [1, 2, 3, 2, 3, 2, 1]], [32, [1, 2, 1, 1, 1, 1, 1]], [16, [1, 2, 1, 1, 1, 2, 1]], [32, [1, 2, 1, 1, 2, 2, 1]], [16, [1, 2, 1, 1, 2, 1, 1]], [64, [1, 2, 1, 2, 2, 2, 1]], [32, [1, 2, 1, 2, 2, 1, 1]], [24, [1, 2, 1, 2, 3, 2, 1]], [16, [1, 2, 1, 2, 1, 1, 1]], [8, [1, 2, 1, 2, 1, 2, 1]]


Ainsi plusieurs problèmes se posent à moi,

* dénombrer le nombre de type répartitions de tas possibles pour n donné ainsi que le nombre de permutation étant de ce type.

* ce nombre m semble suivre la suite A000292, pourquoi??

Auriez-vous des pistes? Le dénombrement des types de répartitions possibles me fait penser à un dénombrement d'escalier de Dick comme présenté dans la vidéo suivante: ICI à partir de 13 min 20. En effet, on part de (1,1), en avançant d'un carreau on peut monter ou descendre d'un carreau, ou rester à la même ordonnée et on doit arriver au point (n,1) avec à tout instant une ordonnée strictement positive.

Des pistes?

Merci à tous,

RoBeRto.
-----

[Médiat]

Bonjour,

Je ne comprends pas vos calculs :
Pour n= 2, il n'y a que 2 permutations (1, 2) et (2, 1)

1ère interprétation : (2, 1) est une composante connexe, dans ce cas le nombre moyen de composante connexe est 1, multiplié par n=2 je trouve 2
2ième interprétation : (2, 1) n'est pas une composante connexe, dans ce cas le nombre moyen de composante connexe est 1,5, multiplié par n=2 je trouve 3

Je ne vois pas comment trouver 4 ...

[invite332de63a]

Bonjour,

pour n=2, le nombre de tas ne peut être que 1 quelque soit l'ordre de tirage de la première puis de la seconde copie. Ainsi le logiciel donne: 2, [1,1]. Attention m est la somme des nombre moyens de tas pour chaque permutation multiplié par n. Ici il y a 2 permutations, pour chacun d'entre elle le nombre moyen de tas est 1, d'où m=2(1+1)=4.

À l'origine je calculais plutôt la moyenne des nombres moyens de tas par permutations, mais comme je voulais voir si cette suite était référencée dans OEIS, voilà pourquoi j'ai changé légèrement la définition.