4.2 Avec ordre / Avec remise

Le plus simple des quatre problèmes consiste à choisir k\displaystyle k objets parmi n\displaystyle n avec ordre et avec remise. Dans ce cas, il s’agit d’une simple application du principe du produit. On a donc n\displaystyle n options pour le premier objet ET n\displaystyle n options pour le deuxième objet ET n\displaystyle n options pour le troisième objet ET ….. ET n\displaystyle n options pour le k-ième objet, ce qui nous fait un total de nk\displaystyle n^{k} façons de choisir k\displaystyle k objets.

Alternativement, on peut aussi trouver la même solution avec les fonctions génératrices. Comme l’ordre des objets est important, il nous faudra utiliser une fonction génératrice exponentielle (FGE). Dans ce cas, il suffit de remarquer que, pour chacun des n\displaystyle n objets, il n’y a pas de limite sur le nombre de fois que l’on peut les choisir. Chacun des n\displaystyle n objets aura donc la fonction génératrice exponentielle suivante:

1+x+x22!+x33!+x44!+x55!+…=∑i=0∞xii!\displaystyle 1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\frac{x^{4}}{4!}+\frac{x^{% 5}}{5!}+...=\sum_{i=0}^{\infty}\frac{x^{i}}{i!}

Maintenant, remarquons que le problème revient à choisir un certain nombre de fois le premier objet ET un certain nombre de fois le second ET un certain nombre de fois le troisième, etc. Le fait d’utiliser une fonction génératrice exponentielle viendra ensuite tenir compte du fait que l’ordre des éléments est important. La fonction génératrice exponentielle décrivant le problème sera donc:

(∑i=0∞xii!)n=(ex)n=en⁢x=∑i=0∞(n⁢x)ii!=∑i=0∞ni⁢xii!\displaystyle\left(\sum_{i=0}^{\infty}\frac{x^{i}}{i!}\right)^{n}=(e^{x})^{n}=% e^{nx}=\sum_{i=0}^{\infty}\frac{(nx)^{i}}{i!}=\sum_{i=0}^{\infty}n^{i}\frac{x^% {i}}{i!}

Comme nous voulons choisir k\displaystyle k objets, notre solution est donnée par le coefficient de xkk!\displaystyle\frac{x^{k}}{k!}. On obtient donc à nouveau nk\displaystyle n^{k} options.

Une troisième approche pour résoudre le même problème consiste à utiliser une récurrence. Dans ce cas, il suffit de remarquer que pour choisir k\displaystyle k éléments, il suffit de choisir k−1\displaystyle k-1 élément, puis de choisir le dernier. Nous avons évidemment n\displaystyle n options pour choisir le dernier élément. Si on dénote par xk\displaystyle x_{k} le nombre de façons de choisir les k\displaystyle k objets, on obtient donc la récurrence suivante:

{xk=n⁢xk−1,∀k≥2x1=n\displaystyle\left\{\begin{array}[]{l}x_{k}=nx_{k-1},\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \forall k\geq 2\\ x_{1}=n\end{array}\right.

De cette récurrence, il est relativement facile d’en déduire une formule explicite à l’aide de l’induction. Celle ci est bien entendu xk=nk\displaystyle x_{k}=n^{k}. Remarquez que notre récurrence aurait pu être écrite de manière plus naturelle sous la forme suivante:

{nk=n⁢nk−1,∀k≥2n1=n\displaystyle\left\{\begin{array}[]{l}n^{k}=nn^{k-1},\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \forall k\geq 2\\ n^{1}=n\end{array}\right.

Ce qui n’est en fait rien d’autre qu’un cas particulier de la loi des exposants.

Exemple 4.2.1.

Dans une classe de 2e année à l’élémentaire contenant 30\displaystyle 30 étudiants, chaque matin un étudiant est choisit au hasard pour prendre les présences. De combien de façon différente les élèves peuvent être choisit sur une période d’une semaine (Lundi au vendredi) ? Dans ce cas, on remarque que le problème se fait avec ordre et avec remise, ce qui nous permet d’affirmer qu’il y a 305=24 300 000\displaystyle 30^{5}=24\leavevmode\nobreak\ 300\leavevmode\nobreak\ 000 façons de choisir les étudiants.