5.6 L’ordre dans les urnes et les nombres de Lah (6 cas)

Les $\displaystyle 6$ cas qu’il nous reste à traiter concernent les problèmes où l’ordre des boules dans les urnes est important. Lorsque l’on parle de boule proprement dite, ceci ne fait bien entendu pas beaucoup de sens, mais on doit se rappeler qu’il ne s’agit que d’un modèle et que les boules peuvent représenter en réalité n’importe quel type d’objet, par exemple des livres que l’on empile dans des boites. L’un des points clés de cette section est les nombres de Lah que l’on définit comme suit:

Définition 5.6.1.

On définit les nombres de Lah $\displaystyle\left\lfloor k\atop n\right\rfloor$ comme étant le nombre de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques, si les urnes ne peuvent pas être vides et l’ordre des boules dans les urnes est important. ²² 2 Les nombres de Lah sont parfois qualifiés de nombres de Stirling de troisième espèce en raison de plusieurs connexions entre ces nombres et les nombres de Stirling de première et deuxième espèce.

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes différentes si l’ordre des boules dans les urnes est importante?

Pour résoudre ce problème, l’idée consiste premièrement à ordonner les boules, ce qui peut être accompli de $\displaystyle k!$ façons. Une fois que les objets sont ordonnés, nous allons chercher à déterminer lesquels se retrouvent dans quelles urnes. Pour ce faire, imaginons les objets comme la liste suivante:

\displaystyle 1\leavevmode\nobreak\ \leavevmode\nobreak\ 2\leavevmode\nobreak% \ \leavevmode\nobreak\ 3\leavevmode\nobreak\ \leavevmode\nobreak\ 4\leavevmode% \nobreak\ \leavevmode\nobreak\ 5\leavevmode\nobreak\ \leavevmode\nobreak\ ...% \leavevmode\nobreak\ \leavevmode\nobreak\ k

Pour déterminer lesquels sont dans quelles urnes, il s’agit de faire des coupures dans notre liste, c’est à dire placer des barres verticales. Comme les urnes peuvent possiblement être vides, nous avons $\displaystyle k+1$ endroits ou nous pouvons couper et le processus se fait avec remise. Maintenant, pour déterminer les $\displaystyle n$ urnes, on remarque que nous devons faire $\displaystyle n-1$ coupures. L’ordre des coupures n’est cependant pas important. Le nombre de façons de placer nos objets dans les urnes est donc:

\displaystyle k!\left\langle k+1\atop n-1\right\rangle=k!\frac{(k+1+n-1-1)!}{(% n-1)!\leavevmode\nobreak\ k!}=\frac{(k+n-1)!}{(n-1)!}=(k+n-1)^{\underline{k}}=% (k+n-1)(k+n-2)...(n+1)(n)=n^{\overline{k}}

Remarquez qu’il s’agit de la première fois que nous obtenons directement les factorielles montantes comme solution d’un problème de combinatoire. Nous leur avons donc trouvé une interprétation combinatoire. La factorielle montante $\displaystyle n^{\overline{k}}$ représente le nombre de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes différentes si l’ordre des boules dans chaque urne est important.

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans des urnes différentes si les urnes ne peuvent pas être vide et l’ordre des boules dans les urnes est importante?

Comme pour le problème précédent, la première étape consiste à ordonner les $\displaystyle k$ boules, ce qui peut être accompli de $\displaystyle k!$ façons. Ensuite, il s’agit de faire des coupures pour déterminer dans quel urne se retrouvera chacune des boules. Comme les urnes ne peuvent pas être vides, il n’y a que $\displaystyle k-1$ endroits où nous pouvons effectuer une coupure. De plus, comme le nombre d’urnes n’est pas déterminé, pour chaque espace, nous pouvons faire une coupure ou non. Donc, pour chaque espace, nous avons deux choix. En appliquant le principe du produit, on obtient donc la solution suivante:

\displaystyle 2^{k-1}k!

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes différentes si les urnes ne peuvent pas être vide et l’ordre des boules dans les urnes est importante?

À nouveau, pour résoudre ce problème, on commence par ordonner toutes les boules, ce qui peut être accompli de $\displaystyle k!$ façons. Puis, on fait des coupures pour séparer les différentes urnes. Comme les urnes ne peuvent pas être vides, il y a $\displaystyle k-1$ emplacements possibles pour les coupures. De plus, le choix des $\displaystyle n-1$ coupures est sans remise, à nouveau dû au fait que les urnes ne peuvent pas être vides. On obtient donc la solution suivante:

\displaystyle k!\binom{k-1}{n-1}

Alternativement, on peut aussi résoudre le problème en faisant usage des nombres de Lah. On peut commencer par placer les $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques de sorte que les urnes ne soient pas vides et que l’ordre des boules dans les urnes soit important, ce qui peut être fait de $\displaystyle\left\lfloor k\atop n\right\rfloor$ façons. Une fois les urnes remplies, elles sont maintenant distinguables, il devient donc possible de les ordonner, ce qui peut être effectué de $\displaystyle n!$ façons. La solution du problème peut donc aussi être écrite sous la forme:

\displaystyle n!\left\lfloor k\atop n\right\rfloor

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques si les urnes ne peuvent pas être vide et l’ordre des boules dans les urnes est importante?

Par définition, la solution de ce problème est donné par les nombres de Lah. La solution est donc:

\displaystyle\left\lfloor k\atop n\right\rfloor

Par contre, en utilisant la solution du problème précédent, il nous est maintenant possible de trouver facilement une formule explicite pour les nombres de Lah. En effet, dans le problème précédent, nous avons obtenu l’égalité suivante:

\displaystyle n!\left\lfloor k\atop n\right\rfloor=k!\binom{k-1}{n-1}

Ce qui nous permet d’affirmer immédiatement que:

\displaystyle\left\lfloor k\atop n\right\rfloor=\frac{k!}{n!}\binom{k-1}{n-1}

Une formule de récurrence pour les nombres de Lah

Pour trouver une relation de récurrence pour les nombres de Lah, l’idée est semblable à ce que nous avons fait pour les nombres de Stirling de deuxième espèce. On utilise la méthode de l’élément distingué en fixant premièrement un objet $\displaystyle x$ parmi les $\displaystyle k$ boules. On peut placer les $\displaystyle k-1$ objets restants dans $\displaystyle n-1$ urnes, ce qui signifie que l’élément $\displaystyle x$ doit se trouver seul dans une urne (la seule urne qui est vide), car les urnes ne peuvent pas être vides par hypothèse. Ceci peut être accompli de $\displaystyle\left\lfloor k-1\atop n-1\right\rfloor$ façons. Autrement, on peut placer les $\displaystyle k-1$ objets restants dans les $\displaystyle n$ urnes, ce qui peut être fait de $\displaystyle\left\lfloor k-1\atop n\right\rfloor$ façons, et dans ce cas nous avons $\displaystyle k+n-1$ endroit où nous pouvons placer notre élément $\displaystyle x$ , ce qui nous donne la récurrence suivante:

\displaystyle\left\lfloor k\atop n\right\rfloor=\left\lfloor k-1\atop n-1% \right\rfloor+(k+n-1)\left\lfloor k-1\atop n\right\rfloor

Le facteur $\displaystyle k+n-1$ mérite d’être justifié. L’idée pour placer les $\displaystyle k-1$ objets dans $\displaystyle n$ urnes est de commencer par ordonner les objets, puis de faire $\displaystyle n-1$ une coupure, ce qui permet de déterminer quel objet ira dans chacune des $\displaystyle n$ urnes. Lorsque vient le temps de placer notre élément $\displaystyle x$ , nous devons déterminer le nombre d’espaces où nous pouvons l’insérer. Chacune des $\displaystyle k-2$ espaces (en bleu) entre les $\displaystyle k-1$ éléments est un emplacement possible. À ceci, il faut ajouter une possibilité pour chacune des $\displaystyle n$ urnes (en rouge) signifiant qu’on peut insérer notre élément au dessus d’une pile. Finalement, il faut ajouter une dernière possibilité (en vert) à la fin de la dernière urne. En additionnant le tout, on obtient donc:

\displaystyle(k-2)+(n)+(1)=k+n-1

\displaystyle\Rightarrow

À notre récurrence, il faut bien entendu ajouter les valeurs initiales suivantes :

\displaystyle\left\lfloor k\atop 1\right\rfloor=k!,\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \left\lfloor k\atop k\right\rfloor=1\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \textrm{ et }\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \left\lfloor k\atop n\right\rfloor=0% \textrm{ si }n>k

Ces valeurs sont justifié car si nous plaçons $\displaystyle k$ objets dans une seule urne, il n’y a $\displaystyle k!$ façons de les ordonner. Ensuite, si nous voulons placer $\displaystyle k$ objets dans $\displaystyle k$ urnes, alors chaque urne doit contenir un seul élément. Comme les urnes sont identiques, il n’y a qu’une seule façon de le faire. Finalement, si nous avons plus d’urnes que d’objets, alors par le principe des nids de pigeons, il est impossible de placer tous les objets dans les urnes de sorte qu’aucune urne ne soit vide, ce qui justifie la valeur de $\displaystyle 0$ .

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques si l’ordre des boules dans les urnes est importante?

Pour résoudre ce problème, il suffit de remarquer que le problème est équivalent à placer les boules dans une urne non vide, OU deux urnes non vides, OU trois urnes non vides, etc… jusqu’à un maximum de $\displaystyle n$ urnes non vides. La solution est donc:

\displaystyle\sum_{i=1}^{n}\left\lfloor k\atop i\right\rfloor

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans des urnes identiques si les urnes ne peuvent pas être vide et l’ordre des boules dans les urnes est importante?

Ce problème est en fait presque identique au précédent, à la différence que nous ne sommes pas limités dans le nombre d’urnes, sauf que les urnes ne peuvent pas être vides. Il peut donc y avoir un maximum de $\displaystyle k$ urnes. La solution du problème est donc:

\displaystyle\sum_{i=1}^{k}\left\lfloor k\atop i\right\rfloor

5.6 L’ordre dans les urnes et les nombres de Lah (6 cas)

Définition 5.6.1.

Combien y a-t-il de façons de placer k\displaystyle k boules différentes dans n\displaystyle n urnes différentes si l’ordre des boules dans les urnes est importante?

Combien y a-t-il de façons de placer k\displaystyle k boules différentes dans des urnes différentes si les urnes ne peuvent pas être vide et l’ordre des boules dans les urnes est importante?

Combien y a-t-il de façons de placer k\displaystyle k boules différentes dans n\displaystyle n urnes différentes si les urnes ne peuvent pas être vide et l’ordre des boules dans les urnes est importante?

Combien y a-t-il de façons de placer k\displaystyle k boules différentes dans n\displaystyle n urnes identiques si les urnes ne peuvent pas être vide et l’ordre des boules dans les urnes est importante?