5.2 Application du principe du produit (4 cas)

Autre que les cas triviaux que nous avons considérés dans la section précédente, les cas les plus simples sont ceux qui peuvent être traités directement par une application du principe du produit. Ils sont au nombre de 4\displaystyle 4. Comme le principe du produit génère automatiquement un ordre, il sera possible de l’utiliser uniquement dans des cas où les boules sont différentes.

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 peuvent contenir un nombre quelconque de boules et l’ordre des boules dans les urnes n’est pas importante ?

Comme les boules sont toutes différentes, on peut parler de la première, la seconde, la troisième, etc. De la même façon, comme les urnes sont distinctes, pour chacune des k\displaystyle k boules, nous avons n\displaystyle n choix. Par le principe du produit, nous avons donc:

n×n×…×n⏟k⁢fois=nk\displaystyle\underbrace{n\times n\times...\times n}_{k\leavevmode\nobreak\ % \textrm{fois}}=n^{k}

Le problème peut être réinterprété de deux autres façons intéressantes. La première consiste à déterminer combien de façons il y a de choisir k\displaystyle k objets parmi n\displaystyle n avec ordre et avec remise. Dans ce cas, on peut considérer les boules comme étant numérotées de 1\displaystyle 1 à k\displaystyle k et considérer les urnes comme étant les n\displaystyle n objets. En plaçant les boules dans les urnes, cela revient donc à choisir le premier objet, le second, et ainsi de suite.

Une autre interprétation concerne le nombre de fonctions entre un ensemble de k\displaystyle k éléments et un ensemble de n\displaystyle n éléments. Dans ce cas, il s’agit de considérer les éléments du premier ensemble comme des boules et les éléments du second comme des urnes. Le fait de placer une boule dans une urne peut alors être vu comme équivalent à placer une connexion entre un élément du premier ensemble et un élément du second.

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 contenir plus d’un objet ?

Ici, l’idée est très semblable au problème précédent, à la différence que, comme les urnes ne peuvent pas contenir plus d’un objet, le nombre de choix que nous avons diminuera à chaque fois qu’une boule sera placée. On a donc:

n×(n−1)×(n−2)×…×(n−k+1)=nk¯\displaystyle n\times(n-1)\times(n-2)\times...\times(n-k+1)=n^{\underline{k}}

Remarquez qu’il peut être tentant de traiter le problème en deux cas, car si k>n\displaystyle k>n, alors il n’y aura pas suffisamment d’urnes pour placer toutes les boules ; en conséquence, il n’y a aucune possibilité. Ceci n’est cependant pas nécessaire en raison de l’utilisation des factorielles descendantes. En effet, si k>n\displaystyle k>n, alors l’un des membres du produit sera nécessairement 0\displaystyle 0, et donc nk¯=0\displaystyle n^{\underline{k}}=0. Par contre, si l’on écrit la solution en termes de factorielle, il devient alors nécessaire de mentionner explicitement les deux cas. La solution du problème peut donc s’écrire alternativement comme:

{n!(n−k)! si ⁢k≤n0 autrement\displaystyle\left\{\begin{array}[]{ll}\frac{n!}{(n-k)!}\nobreak\leavevmode% \nobreak\leavevmode\nobreak\leavevmode&\textrm{ si }k\leq n\\[8.5359pt] 0&\textrm{ autrement}\end{array}\right.

Comme pour le problème précédent, on peut réinterpréter ce problème en termes de choix d’objets ou en termes de fonction. Combien de façons y a-t-il de choisir k\displaystyle k objets parmi n\displaystyle n avec ordre et sans remise ? À nouveau, il s’agit de traiter les boules comme étant numérotées de 1\displaystyle 1 à k\displaystyle k pour indiquer l’ordre dans lequel on choisit les objets, puis les urnes comme étant les objets. Comme il n’est pas permis de placer plus d’une boule dans une urne, cela revient à dire qu’on ne peut pas choisir un objet plus d’une fois (i.e. sans remise).

Alternativement, on peut aussi considérer le nombre de fonctions injectives entre un ensemble de k\displaystyle k éléments et un ensemble de n\displaystyle n éléments. Dans ce cas, il suffit de considérer les éléments du premier ensemble comme des boules et les éléments du second comme des urnes. Une connexion entre un élément du premier ensemble et le second est alors représentée par le fait de placer une boule dans une urne. Comme les urnes ne peuvent pas contenir plus d’une boule, il n’y aura jamais plus d’une connexion pointant vers un élément du second ensemble. C’est à dire que la fonction sera injective.

Combien y a-t-il de façons de placer k\displaystyle k boules différentes dans n\displaystyle n urnes différentes si chaque urne doit contenir exactement un objet ?

Pour que cela soit possible, il est essentiel d’avoir autant de boules que d’urnes ; sinon, il n’y a aucune possibilité. Si n=k\displaystyle n=k, le problème devient alors équivalent au précédent, ce qui nous donne:

n!(n−n)!=n!0!=n!\displaystyle\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!

La solution du problème est donc:

{n!⁢ ou ⁢k! si ⁢k≤n0 autrement\displaystyle\left\{\begin{array}[]{ll}n!\textrm{ ou }k!\nobreak\leavevmode% \nobreak\leavevmode\nobreak\leavevmode&\textrm{ si }k\leq n\\[8.5359pt] 0&\textrm{ autrement}\end{array}\right.

À noter que ce problème est équivalent à compter le nombre de fonctions bijectives entre deux ensembles.

Combien y a-t-il de façons de placer k\displaystyle k boules différentes dans des urnes différentes si chaque urne doit contenir exactement un objet ?

Bien que le nombre d’urnes ne soit pas explicitement mentionné dans le problème, la contrainte selon laquelle chaque urne doit contenir exactement une boule implique automatiquement qu’il y aura autant de boules que d’urnes. Il s’agit d’un cas particulier du problème précédent qui suppose que le nombre d’urnes est égal au nombre de boules. La solution du problème sera donc toujours k!\displaystyle k!.