Donnes et formule du multinôme

Exercice de TD · niveau 2 · mathématiques (PTSI), chapitre 15 — Dénombrement · B. Listes, arrangements, permutations

Énoncé

a) De combien de façons peut-on distribuer les $32$ cartes d'un jeu en quatre mains de $8$ cartes, les quatre joueurs étant distincts ?

b) Montrer que le nombre de façons de répartir $n$ objets distincts dans $k$ boîtes étiquetées, la $i$ -ème recevant exactement $n_{i}$ objets ( $n_{1} + \dots + n_{k} = n$ ), vaut $\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$ . Retrouver ainsi le nombre d'anagrammes du mot ANANAS.

c) (Formule du multinôme) En développant $(x + y + z)^{n}$ comme le cours développe $(a + b)^{n}$ , montrer que $(x + y + z)^{n} = \sum \frac{n !}{i ! j ! ℓ !} x^{i} y^{j} z^{ℓ},$ la somme portant sur les triplets $(i, j, ℓ)$ d'entiers naturels de somme $n$ . Quel est le coefficient de $x^{2} y^{2} z$ dans $(x + y + z)^{5}$ ?

Corrigé

La stratégie. Choisir successivement les places, et appliquer le principe de multiplication. Il s'applique parce qu'à chaque étape, le nombre de choix possibles ne dépend que du nombre d'objets encore disponibles, jamais de l'identité de ceux qu'on a déjà placés.

a) La donne. Le premier joueur reçoit $8$ cartes parmi $32$ : $(8 32)$ choix ; le deuxième $8$ parmi les $24$ restantes : $(8 24)$ ; le troisième $8$ parmi $16$ : $(8 16)$ ; le dernier prend les $8$ dernières : $(8 8) = 1$ . En écrivant les coefficients avec des factorielles, les termes intermédiaires se simplifient en chaîne : $(8 32) (8 24) (8 16) = \frac{32 !}{8 ! 24 !} \cdot \frac{24 !}{8 ! 16 !} \cdot \frac{16 !}{8 ! 8 !} = \frac{32 !}{( 8 ! ) ^{4}} = 99561092450391000,$ soit environ $1 0^{17}$ donnes. Le point délicat est le mot « distincts » : donner la main $M$ au premier joueur et la main $M^{'}$ au second est une autre donne que l'inverse. Si les paquets n'avaient pas de nom, il faudrait diviser — c'est l'objet de l'exercice suivant.

b) Le coefficient multinomial. Même méthode : on remplit la boîte $1$ avec $n_{1}$ objets parmi $n$ , puis la boîte $2$ avec $n_{2}$ objets parmi les $n - n_{1}$ restants, et ainsi de suite. En notant $s_{i} = n_{1} + \dots + n_{i}$ (et $s_{0} = 0$ ), le $i$ -ème choix se fait de $(n _{i} n - s _{i - 1}) = \frac{( n - s _{i - 1} )!}{n _{i} ! ( n - s _{i} )!}$ façons ; dans le produit, chaque $(n - s_{i})!$ du dénominateur se simplifie avec le numérateur suivant, et il reste, puisque $s_{k} = n$ et $0! = 1$ , $\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !} .$ ANANAS. Les objets sont les $6$ positions, les boîtes sont les lettres $A$ , $N$ , $S$ , de tailles $3$ , $2$ , $1$ : une anagramme, c'est le choix des positions de chaque lettre. D'où $\frac{6 !}{3 ! 2 ! 1 !} = \frac{720}{12} = 60$ anagrammes. On le retrouve en étiquetant les lettres répétées : $720$ mots, et chaque anagramme en provient exactement $3! \times 2! = 12$ fois. Distribuer des cartes et écrire des anagrammes sont le même problème.

c) Le multinôme. Développons $(x + y + z)^{n}$ , produit de $n$ facteurs, sans rien regrouper : chaque terme s'obtient en choisissant, dans chacun des $n$ facteurs, $x$ , $y$ ou $z$ . Le monôme $x^{i} y^{j} z^{ℓ}$ apparaît autant de fois qu'il y a de façons de répartir les $n$ facteurs, qui sont distincts, dans trois boîtes étiquetées « $x$ », « $y$ », « $z$ » de tailles $i$ , $j$ , $ℓ$ : par le b), $\frac{n !}{i ! j ! ℓ !}$ fois. D'où la formule. Pour $x^{2} y^{2} z$ dans $(x + y + z)^{5}$ : $\frac{5 !}{2 ! 2 ! 1 !} = \frac{120}{4} = 30$ .

Deux contrôles. Avec $x = y = z = 1$ , la somme des coefficients vaut $3^{n}$ , le nombre de mots de longueur $n$ sur trois lettres : $243$ pour $n = 5$ . Et deux applications du binôme redonnent la formule : $(x + (y + z))^{n} = \sum_{i} (i n) x^{i} (y + z)^{n - i}$ , puis $(y + z)^{n - i} = \sum_{j} (j n - i) y^{j} z^{n - i - j}$ , et $(i n) (j n - i) = \frac{n !}{i ! j ! ( n - i - j )!}$ .

Ce que l'exercice installe. Choisir successivement les places : le coefficient multinomial compte les répartitions de $n$ objets distincts dans des boîtes étiquetées de tailles imposées — mains de cartes, anagrammes, termes d'un développement. Et le développement d'une puissance se lit comme un dénombrement, exactement comme le cours lit la formule du binôme. Le même nombre compte les façons de répartir des molécules discernables entre plusieurs compartiments : l'exercice 9 en traite deux.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.