Problème — Distribution d'objets dans des boîtes (Partitions et Étoiles et barres)

Application directe du cours · niveau 3 (difficile) · mathématiques (terminale), chapitre 7 — Combinatoire et Dénombrement

Énoncé

Problème — Distribution d'objets dans des boîtes (Partitions et Étoiles et barres).

On souhaite étudier la distribution de $n$ objets dans $k$ boîtes distinctes (numérotées de 1 à $k$ ).

On suppose d'abord que les $n$ objets sont distincts (par exemple, des lettres différentes à poster). Justifier que le nombre total de répartitions possibles est $k^{n}$ .

On suppose désormais que les $n$ objets sont identiques (par exemple, des bonbons identiques). On cherche à déterminer le nombre de répartitions.

Dans le cas $n = 4$ et $k = 3$ , on note $(x_{1}, x_{2}, x_{3})$ la répartition où $x_{i}$ est le nombre d'objets dans la boîte $i$ ( $x_{i} \in N$ et $x_{1} + x_{2} + x_{3} = 4$ ). Lister toutes les répartitions possibles (les triplets) et en donner le nombre.

De façon générale, on représente une répartition en plaçant les $n$ objets sous la forme de ronds $∙$ séparés par $k - 1$ barres verticales $∣$ qui délimitent les $k$ boîtes. Par exemple, pour $n = 4, k = 3$ , la répartition $(2, 0, 2)$ est représentée par :

$∙ ∙ ∣∣ ∙ ∙$

Justifier que le nombre total de symboles (ronds et barres) dans cette représentation est $n + k - 1$ .

Expliquer pourquoi dénombrer les répartitions possibles revient à choisir les positions des $n$ ronds parmi les $n + k - 1$ emplacements possibles. En déduire que le nombre de répartitions est égal à :

$(n n + k - 1)$

Pour distribuer $n$ objets distincts dans $k$ boîtes distinctes, chaque objet peut être placé dans n'importe laquelle des $k$ boîtes. Il y a donc $k$ choix pour le premier objet, $k$ choix pour le second, ..., et $k$ choix pour le $n$ -ième. Par le principe multiplicatif, le nombre de répartitions possibles est :

$n fois k \times k \times \dots \times k = k^{n}$

Les répartitions possibles pour $n = 4$ objets dans $k = 3$ boîtes sont les triplets d'entiers naturels $(x_{1}, x_{2}, x_{3})$ vérifiant $x_{1} + x_{2} + x_{3} = 4$ :

les permutations de $(4, 0, 0)$ : $(4, 0, 0)$ , $(0, 4, 0)$ , $(0, 0, 4)$ (3 triplets) ;
les permutations de $(3, 1, 0)$ : $(3, 1, 0)$ , $(3, 0, 1)$ , $(1, 3, 0)$ , $(1, 0, 3)$ , $(0, 3, 1)$ , $(0, 1, 3)$ (6 triplets) ;
les permutations de $(2, 2, 0)$ : $(2, 2, 0)$ , $(2, 0, 2)$ , $(0, 2, 2)$ (3 triplets) ;
les permutations de $(2, 1, 1)$ : $(2, 1, 1)$ , $(1, 2, 1)$ , $(1, 1, 2)$ (3 triplets).

Le nombre total de répartitions possibles est de $3 + 6 + 3 + 3 = 15$ .

Pour délimiter $k$ boîtes distinctes, il suffit d'utiliser $k - 1$ séparateurs (les barres $∣$ ). La répartition est modélisée par une suite contenant $n$ symboles $∙$ (pour les objets) et $k - 1$ symboles $∣$ (pour les séparateurs). Le nombre total de symboles est donc la somme :

$n + (k - 1) = n + k - 1$

Dégager une configuration unique de répartition revient à spécifier où se trouvent les $n$ symboles $∙$ parmi les $n + k - 1$ emplacements de la suite (les emplacements non choisis contenant nécessairement des barres $∣$ ). Le nombre de choix est donné par le nombre de combinaisons de $n$ éléments parmi $n + k - 1$ , soit :

$(n n + k - 1)$

Pour $n = 4, k = 3$ , cela donne $(4 4 + 3 - 1) = (4 6) = (2 6) = 15$ , ce qui corrobore le résultat de la question (a).

Distribuer 10 bonbons identiques ( $n = 10$ ) à 3 enfants ( $k = 3$ , assimilés à 3 boîtes distinctes) correspond au nombre de répartitions :

$(10 10 + 3 - 1) = (10 12) = (2 12) = \frac{12 \times 11}{2 \times 1} = 66$

Il y a 66 répartitions possibles.

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