5.3 Les compositions (4 cas)

Les 4\displaystyle 4 problèmes suivants sont liés aux problèmes de composition d’un entier. Une composition d’un entier n\displaystyle n est une suite (ordonnée) de termes ≥0\displaystyle\geq 0 pour lesquels la somme est n\displaystyle n. Par exemple, on peut considérer la composition suivante:

3+1+2=6\displaystyle 3+1+2=6

Les compositions d’un entier donnent lieu à de nombreux problèmes en considérant qu’on peut mettre des conditions sur le nombre de termes, ou bien en imposant des contraintes sur les termes eux-mêmes, par exemple en supposant qu’ils peuvent être 0\displaystyle 0 ou non. Les problèmes de composition peuvent être vus comme des problèmes d’occupation en représentant les entiers de la somme par des étoiles séparées par des barres verticales. Par exemple, la composition du nombre 6\displaystyle 6 que nous avons mentionnée plus haut peut être représentée sous la forme suivante:

∗∗∗|∗|∗∗\displaystyle***|*|**

Les étoiles représentent alors les boules, et les barres verticales séparent les différentes urnes. Comme les termes sont ordonnés, mais que les étoiles sont identiques, nous sommes amenés à considérer des problèmes où les boules sont identiques et les urnes différentes. Nous allons dès maintenant examiner chacun des 4\displaystyle 4 cas individuellement.

Combien y a-t-il de façons de placer k\displaystyle k boules identiques dans n\displaystyle n urnes différentes ?

Pour résoudre ce problème, on commence par représenter chacune des k\displaystyle k boules par des étoiles:

∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗\displaystyle**************

Puis, on place des barres verticales pour séparer les différentes urnes. Comme nous avons n\displaystyle n urnes, il nous faudra placer n−1\displaystyle n-1 barres verticales. Comme les urnes peuvent être vides, il est permis de placer une barre verticale entre n’importe quelle étoile, mais aussi avant la première ou après la dernière. C’est à dire que nous avons k+1\displaystyle k+1 emplacement possible pour les barres. De plus, il nous est permis de placer plus d’une barre au même emplacement.

||∗∗∗∗|∗∗∗∗||∗∗∗∗|∗∗\displaystyle||****|****||****|**

Le problème est donc équivalent à choisir n−1\displaystyle n-1 espaces parmi k+1\displaystyle k+1 options sans ordre et avec remise. En nous basant sur ce que nous avons trouvé dans le chapitre précédent, la solution est donc:

⟨k+1n−1⟩=(k+1+n−1−1)!(n−1)!⁢(k+1−1)!=(k+n−1)!(n−1)!⁢k!=(n+k−1)!k!⁢(n−1)!=⟨nk⟩\displaystyle\left\langle k+1\atop n-1\right\rangle=\frac{(k+1+n-1-1)!}{(n-1)!% (k+1-1)!}=\frac{(k+n-1)!}{(n-1)!k!}=\frac{(n+k-1)!}{k!(n-1)!}=\left\langle n% \atop k\right\rangle

À noter que ce problème est équivalent à demander de combien de façons on peut écrire le nombre k\displaystyle k comme une somme ordonnée de n\displaystyle n termes plus grands ou égaux à 0\displaystyle 0

Combien y a-t-il de façons de placer k\displaystyle k boules identiques dans n\displaystyle n urnes différentes si chaque urne doit contenir au moins une boule ?

Comme pour le problème précédent, il s’agit d’imaginer les boules comme étant des étoiles.

∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗\displaystyle**************

On choisit ensuite n−1\displaystyle n-1 espaces dans lesquels placer des barres verticales. La différence avec le problème précédent est que cette fois, il n’est pas permis de placer une barre avant la première étoile ou après la dernière, car cela impliquerait qu’une urne serait vide. De plus, pour la même raison, il n’est pas permis de placer plus d’une barre verticale dans le même espace. Il y a donc seulement k−1\displaystyle k-1 emplacements possibles pour les barres verticales.

∗∗∗∗∗|∗∗|∗∗∗∗|∗|∗∗\displaystyle*****|**|****|*|**

Le problème revient donc à choisir n−1\displaystyle n-1 emplacements parmi k−1\displaystyle k-1 possibilités sans ordre et sans remise. La solution du problème est donc donnée par le coefficient binomial:

(k−1n−1)\displaystyle\binom{k-1}{n-1}

À noter que ce problème est équivalent à demander de combien de façons on peut écrire le nombre k\displaystyle k comme une somme ordonnée de n\displaystyle n termes strictement positifs (i.e. >0\displaystyle>0).

Combien y a-t-il de façons de placer k\displaystyle k boules identiques dans n\displaystyle n urnes différentes si chaque urne peut contenir au plus une boule ?

Comme les urnes peuvent contenir un maximum d’une seule boule, cela signifie que chaque urne contiendra soit aucune, soit une boule. Comme nous avons un total de k\displaystyle k boules à placer, il suffit de choisir k\displaystyle k urnes parmi les n\displaystyle n qui contiendront une boule. Comme toutes les boules sont identiques, cela se fait sans ordre. De plus, comme les urnes ne peuvent contenir plus d’une boule, le choix doit être fait sans remise. La solution du problème est donc:

(nk)\displaystyle\binom{n}{k}

En termes de composition, ce problème est équivalent à demander de combien de façons peut-on écrire le nombre k\displaystyle k comme une somme ordonnée de n\displaystyle n termes qui peuvent être des 0\displaystyle 0 ou des 1\displaystyle 1.

Combien y a-t-il de façons de placer k\displaystyle k boules identiques dans des urnes différentes si chaque urne doit contenir au moins une boule ?

Le dernier problème de composition que nous allons examiner pour le moment est celui où le nombre d’urnes n’est pas précisé. Dans ce cas, il devient bien entendu nécessaire d’imposer que chaque urne doit contenir au moins un élément pour éviter d’avoir trivialement une infinité de possibilités. Dans ce cas, deux approches sont possibles. Premièrement, on peut représenter à nouveau les k\displaystyle k boules comme étant des étoiles.

∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗⁣∗\displaystyle**************

Comme les urnes ne peuvent pas être vides, les seuls endroits où l’on peut placer nos barres verticales sont dans les k−1\displaystyle k-1 espaces entre deux boules. Comme le nombre d’urnes n’est pas déterminé, il suffit alors, pour chaque emplacement, de choisir si oui ou non l’on place une barre verticale. On a donc deux options pour chacun des k−1\displaystyle k-1 espaces. Par le principe du produit, la solution du problème est donc:

2k−1\displaystyle 2^{k-1}

Bien que la solution que nous venons de fournir soit de loin la plus simple, on peut aussi aborder le problème d’une manière différente. Il s’agit de remarquer qu’on peut placer les k\displaystyle k boules soit dans une urne OU dans deux urnes OU dans trois urnes, etc… jusqu’à un maximum de k\displaystyle k urnes, car chaque urne doit contenir au moins une boule. Par le principe de la somme, on a donc que la solution est:

(k−10)+(k−11)+(k−12)+…+(k−1k−1)=∑i=0k−1(k−1i)\displaystyle\binom{k-1}{0}+\binom{k-1}{1}+\binom{k-1}{2}+...+\binom{k-1}{k-1}% =\sum_{i=0}^{k-1}\binom{k-1}{i}

Bien que nos deux solutions puissent paraître à première vue différentes, comme nous avons compté deux fois exactement la même chose (double counting), nos deux solutions doivent donc être égales. On obtient donc immédiatement, sans aucun calcul additionnel, l’égalité suivante:

∑i=0k−1(k−1i)=2k−1\displaystyle\sum_{i=0}^{k-1}\binom{k-1}{i}=2^{k-1}

Cette égalité peut être facilement justifiée à l’aide de la fonction génératrice du coefficient binomial que nous avons rencontrée dans le chapitre précédent. En effet, nous avons vu que:

∑i=0n(ni)⁢xi=(1+x)n\displaystyle\sum_{i=0}^{n}\binom{n}{i}x^{i}=(1+x)^{n}

En remplaçant n\displaystyle n par k−1\displaystyle k-1, puis en prenant x=1\displaystyle x=1, on obtient alors directement:

∑i=0k−1(k−1i)⁢(1)i=(1+1)k−1=2k−1\displaystyle\sum_{i=0}^{k-1}\binom{k-1}{i}(1)^{i}=(1+1)^{k-1}=2^{k-1}

Finalement, remarquons que ce problème est en fait équivalent à demander de combien de façons peut-on écrire un entier k\displaystyle k comme une somme ordonnée de termes strictement plus grands que 0\displaystyle 0.