Dénombrement de permutations.
Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Dénombrement de permutations.



  1. #1
    RoBeRTo-BeNDeR

    Dénombrement de permutations.


    ------

    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.

    -----

  2. #2
    Médiat

    Re : Dénombrement de permutations.

    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 ...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    RoBeRTo-BeNDeR

    Re : Dénombrement de permutations.

    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.

Discussions similaires

  1. Permutations
    Par Antoniuum dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 07/09/2015, 08h53
  2. permutations
    Par Snowey dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 28/05/2012, 14h25
  3. Analyse combinatoire: dénombrement-permutations-arrangements-combinaisons
    Par snakes1993 dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 26/05/2011, 21h16
  4. Analyse combinatoire: dénombrement-permutations-arrangements-combinaisons
    Par snakes1993 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 25/05/2011, 00h04
  5. Permutations
    Par invite2d0f5281 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 14/12/2009, 12h39