Partition ordonnée

Imaginez cinq cartes distinctes à répartir en trois groupes classés. Le premier reçoit deux cartes, le deuxième une seule et le troisième deux. Les cartes d’un même groupe ne sont pas rangées entre elles, mais échanger le premier et le troisième groupe produit une autre répartition.

Une partition ordonnée conserve donc deux informations : quels éléments sont réunis et quelle place occupe chaque groupe. Le schéma des trois groupes rend visible cette différence entre l’ordre des groupes et l’absence d’ordre à l’intérieur de chacun.

Soit un ensemble fini E contenant n éléments. Une partition ordonnée de E en k parties est une suite (B₁, B₂, …, B_k) de parties non vides, deux à deux disjointes, dont la réunion est E. L’indice donne la place du groupe. L’ordre des éléments à l’intérieur d’un même groupe ne compte pas.

Lorsque la taille du groupe B_i est le nombre positif n_i, la somme des tailles vaut n. Le nombre de partitions ordonnées ayant ces tailles fixées est le coefficient multinomial :

Pour un nombre k fixé sans imposer les tailles, on choisit d’abord une partition en k groupes, puis on ordonne ces groupes. Si S(n,k) désigne le nombre de partitions non ordonnées de n éléments en k groupes non vides, le total est k! S(n,k). En additionnant ce nombre pour toutes les valeurs possibles de k, on obtient le nombre de Fubini d’ordre n.

Cinq cartes distinctes A, B, C, D et E doivent former trois groupes classés. Les tailles imposées sont 2 cartes, puis 1 carte, puis 2 cartes.

1. On choisit les 2 cartes du premier groupe : 10 choix.
2. Parmi les 3 cartes restantes, on choisit celle du deuxième groupe : 3 choix.
3. Les 2 dernières cartes forment nécessairement le troisième groupe : 1 choix.
4. On multiplie les choix successifs : 10 × 3 × 1 = 30.

Le coefficient multinomial donne le même résultat : $5!\mathrm{/}(2!1!2!)=305!/(2!1!2!)=30$. Un contrôle consiste à fixer le premier groupe : chacune des 10 paires laisse exactement 3 choix pour la carte isolée, donc 30 partitions ordonnées.

Dans un classement avec ex æquo, chaque groupe rassemble les concurrents de même rang et l’ordre des groupes porte le classement. Une partition non ordonnée convient seulement si les rangs ne jouent aucun rôle.

Pour un tirage sans remise réparti en lots successifs de tailles fixées, le coefficient multinomial compte les contenus possibles des lots. Une simple combinaison suffit si un seul lot est distingué et si le reste n’est pas séparé en groupes classés.

En dénombrement, cette structure convient lorsque des objets distincts sont affectés à des étapes ordonnées, sans ordre interne à chaque étape. Si l’ordre de passage de chaque objet compte aussi, il faut plutôt compter des permutations.

Partition non ordonnée. Elle retient les groupes, mais pas leur place. Avec {A, B} et {C}, inverser l’écriture des deux groupes ne crée rien de nouveau ; dans une partition ordonnée, cette inversion change le résultat.

Composition d’un entier. Elle ordonne des nombres dont la somme est fixée, pas des groupes d’éléments. La suite de tailles (2, 1, 2) ne dit pas quelles cartes appartiennent à chaque groupe.

Permutation. Une permutation ordonne chaque élément individuellement. Dans la partition ({A, B}, {C}, {D, E}), échanger A et B à l’intérieur du premier groupe ne produit pas une nouvelle partition.

Tailles non fixées. Le seul coefficient multinomial n’est alors pas le total recherché. Il faut additionner sur toutes les suites de tailles positives possibles, ou utiliser la somme des k! S(n,k) lorsque le nombre de groupes varie.

Trop de groupes. Avec des parties non vides, aucune partition n’existe lorsque k > n. Pour n > 0, k doit donc être compris entre 1 et n.

Groupes vides. Une suite de cases pouvant rester vides relève d’une autre convention. Il faut annoncer cette possibilité et employer un dénombrement adapté, car une partition standard ne contient pas de partie vide.

Ensemble vide. La convention usuelle compte une partition ordonnée sans groupe lorsque n = 0. Ce cas charnière vaut 1 ; il ne doit pas être confondu avec une partition comportant un groupe vide.

partition d'un ensemble — Pour revoir les conditions de disjonction, de non-vacuité et de réunion avant d’ajouter un ordre aux groupes.

Coefficients multinomiaux — Pour approfondir le calcul lorsque les tailles successives des groupes sont imposées.

nombre de Bell — Pour comparer le comptage des partitions non ordonnées avec celui des partitions dont les groupes sont classés.