Mathématiques discrètes Version préliminaire

On imagine \(5\) billes distinctes que l’on veut placer dans trois urnes tout aussi différentes. Voici quelques-unes des configuarations possibles.

Un exemple concret d’une telle situation pourrait être la distribution de tâches à accomplir par les membres d’une équipe. Chaque tâche doit être affectée à exactement une personne. Un exemple plus mathématique équivalent est celui des fonction d’un ensemble \(A\) (les billes ou encore les tâches) vers un ensemble \(B\) (les urnes ou encore les membres de l’équipe).

Une deuxième situation est celle où l’on ne distingue pas les billes, seulement les urnes. Toujours en gardant les cinq billes à distribuer à trois personnes, on peut voir que les situations 4.3.1 et 4.3.2 sont maintenant équivalentes dans ce scénario. Concrètement, on peut imaginer devoir distribuer cinq morceaux d’une tablette de chocolat à trois enfants. Les morceaux sont identiques, mais pas les personnes qui les reçoivent. Mathématiquement, ce problème est équivalent à celui de trouver le nombre de solutions à l’équation \(x_1+x_2+x_3=5\text{.}\)

Si au contraire les billes sont différentes, mais pas les urnes. Dans ce cas-ci, se sont maintenant les situations 4.3.1 et 4.3.6 qui sont équivalentes. Concrètement, on peut imaginer vouloir distribuer des personnes dans des équipes lors d’un cours d’éducation physique. Il n’y a pas de différence entre la « première » équipe, la « deuxième » équipe et ainsi de suite, seuls les membres de l’équipe sont importants. Mathématiquement, ce problème revient à compter le nombre de manières de placer les éléments d’un ensemble (les élèves de la classe) dans des sous-ensembles (les équipes) de sorte que chaque élément apparaissent exactement une fois.

Finalement, la dernière situation correspond au cas où les billes et les urnes sont identiques. On peut imaginer la confection de trois sacs d’Halloween à partir de cinq bonbons identiques. On pourrait tout placer les bonbons dans un seul sac (ce qui ne serait pas très apprécié du côté de deux des receveurs), en placer \(4\) dans un sac et \(1\) dans un autre et ainsi de suite. Mathématiquement, dans le problème \(x_1+x_2+x_3=5\text{,}\) on distingue la solution \(x_1=1,x_2=2,x_3=2\) de la solution \(x_1=2,x_2=1,x_3=2\text{.}\) Et si on ne voulait pas faire cette distinction? C’est à cette question que correspond la situation des billes identiques et des urnes identiques.

En plus de chacune de ces situations, on peut ajouter des conditions supplémentaires, en imposant que chaque contenant contienne au moins une bille ou encore au plus une bille. Ceci mène au douze cas possible, résumés dans la table ci-dessous.

Voici une série d’exemples que l’on cherche à classer dans la table 4.3.7.

Les nombres utilisés dans l’exemple précédent sont suffisament petits pour qu’il soit possible de considérer énumérer tous les cas possibles. On tente le coup avant d’essayer de trouver des formules générales pour chacun des douze cas.

Pour certaines des situations de la table 4.3.7, il est simple de déterminer une formule générale. Pour d’autre situations, il faudra y réfléchir plus longuement. Pour terminer cette section, on présente une discussion des cas plus simples à traiter. Pour tous les cas, on suppose que l’on a \(b\) billes et \(u\) urnes.

Le premier cas à considérer est celui des billes différentes et des urnes différentes, sans restrictions. Comme chaque bille peut être placée dans n’importe quelle des \(u\) urnes, il suit du principe du produit qu’il y a \(u^b\) possibilités. À noter que ce cas correspond au nombres de fonctions que l’on peut créer de l’ensemble des billes \(B\) vers l’ensemble des urnes \(U\text{.}\) La proposition 4.1.7 offrait le même résultat. D’ailleurs, la seconde partie de cette propostion compte le nombre de fonctions injectives, qui correspond à l’entrée suivante de la table.

Le prochain cas que l’on considère est celui des billes identiques et des urnes différentes, avec la restrictions d’au plus une bille par urnes. Comme les billes sont identiques, si \(b\leq u\text{,}\) alors cela revient à choisir quelles urnes auront une billes. Ceci peut se faire de \(C_b^u=\frac{u!}{b!(u-b)!}\) manières.

On considère ensuite le cas sans restrictions de cette rangée, soit les billes identiques dans les urnes différentes. Comme on l’a expliqué dans l’introduction, cela revient à trouver le nombre de solutions à l’équation \(x_1+x_2+\cdots +x_u=b\text{.}\) Selon la proposition 4.2.24, ce nombre est égal à \(C_{b}^{b+u-1}\text{.}\)

Le cas où toutes les urnes doivent contenir au moins une bille dans cette ligne n’est pas si différent. Si l’on a assez de billes, comme celles-ci sont identiques, il suffit d’en placer une dans chaque urne et de placer le reste comme s’il n’y avait pas de restrictions. Donc, pour \(b\geq n\text{,}\) il y aura \(C_{b-u}^{b-u+u-1}=C_{b-u}^{b-1}=C_{u-1}^{b-1}\text{.}\)

On regarde ensuite le cas au plus une bille par urne des deux dernières rangées. Dans ces deux cas, les urnes sont indiscernables. Comme on veut que toutes les billes soient placées, deux choses peuvent se produire. Soit \(b\leq u\text{,}\) auquel cas on peut placer une bille par urne (les urnes étant identiques il n’y a qu’une possibilité), soit \(b\ge u\text{,}\) auquel cas on ne peut pas effectuer le placement.

Les quatre autres cas, en plus de la dernière entrée de la première ligne, vont demander un peu plus de réflexion.