4.3 Avec ordre / Sans remise

Comme pour le cas précédent, choisir $\displaystyle k$ objets parmi $\displaystyle n$ avec ordre et sans remise est une simple application du principe du produit. On a donc $\displaystyle n$ options pour le premier objet ET $\displaystyle(n-1)$ options pour le deuxième objet ET $\displaystyle(n-2)$ option pour le troisième objet ET ….. ET $\displaystyle(n-k+1)$ options pour le k-ième objet, ce qui nous fait un total de $\displaystyle\frac{n!}{(n-k)!}$ façons de choisir $\displaystyle k$ objets.

\displaystyle n\times(n-1)\times(n-2)\times(n-3)\times...\times(n-k+1)=\frac{n% \times(n-1)\times(n-2)\times...\times 2\times 1}{(n-k)\times(n-k-1)\times(n-k-% 2)\times...\times 2\times 1}=\frac{n!}{(n-k)!}

Exemple 4.3.1.

Aux olympiques, $\displaystyle 8$ coureurs participent à la final du $\displaystyle 100$ mètre. De combien de façons différentes les médaille d’or, d’argent et de bronze peuvent elle être distribué ? Dans ce cas, on remarque que le problème se fait avec ordre et sans remise, ce qui nous permet d’affirmer qu’il y a $\displaystyle\frac{8!}{(8-3)!}=\frac{8!}{5!}=6\cdot 7\cdot 8=336$ façons de distribuer les médailles.

Les factorielles tombantes et montantes

Nous allons maintenant introduire une notation $\displaystyle n^{\underline{k}}$ pour représenter $\displaystyle\frac{n!}{(n-k)!}$ . Cette notation est motivé du à de nombreuse similarité avec la fonction $\displaystyle x^{k}$ . Cette notation porte le nom de factorielle tombante et peut être définit sans faire appelle à la notion de factorielle, ce qui nous permet d’étendre la notation à des valeurs de $\displaystyle n$ qui ne sont pas nécessairement entière.

Définition 4.3.1.

Si $\displaystyle x\in\mathbb{R}$ et $\displaystyle k\in\mathbb{N}$ , alors on définit la factorielle tombante comme étant:

\displaystyle x^{\underline{k}}=\left\{\begin{array}[]{l}x(x-1)(x-2)(x-3)...(x% -k+1)=\prod_{i=0}^{k-1}(x-i)\textrm{ si }k>0\\ 1\textrm{ si }k=0\end{array}\right.

De la même façon, on définit la factorielle montante comme étant:

\displaystyle x^{\overline{k}}=\left\{\begin{array}[]{l}x(x+1)(x+2)(x+3)...(x+% k-1)=\prod_{i=0}^{k-1}(x+i)\textrm{ si }k>0\\ 1\textrm{ si }k=0\end{array}\right.

Les différences finies

Nous voulons maintenant motivé la notation utilisé pour les factorielles tombantes en illustrant un lien important avec le calcul différentielle. Pour ce faire, rappellons que la dérivé d’une fonction $\displaystyle f(x)$ est définie comme étant:

\displaystyle\lim_{h\rightarrow 0}\frac{f(x+h)-f(x)}{h}

Dans le contexte des mathématiques discrètes, il n’est pas vraiment intéressant de considérer des valeurs de $\displaystyle h$ qui tendent vers $\displaystyle 0$ . Après tout, nous travaillons la majorité du temps avec des entiers. Nous allons donc fixer $\displaystyle h$ comme étant le plus petit entier positif différent de $\displaystyle 0$ , c’est à dire $\displaystyle 1$ . Ceci nous amène à la définition suivante:

\displaystyle\Delta f(x)=f(x+1)-f(x)

Cet opération porte le nom de différence finie. En appliquant cet opérateur à nos factorielles tombantes, nous obtenons donc dans le cas où $\displaystyle x$ est un nombre réel et $\displaystyle k$ un entier positif:

$\displaystyle\displaystyle\Delta x^{\underline{k}}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle(x+1)^{\underline{k}}-x^{\underline{k}}=\prod_{i=0}^% {k-1}(x+1-i)-\prod_{i=0}^{k-1}(x-i)=(x+1)\prod_{i=1}^{k-1}(x-(i-1))-\prod_{i=0% }^{k-1}(x-i)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle(x+1)\prod_{i=0}^{k-2}(x-i)-(x-(k-1))\prod_{i=0}^{k-% 2}(x-i)=\left[(x+1)-(x-(k-1))\right]\prod_{i=0}^{k-2}(x-i)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle k\prod_{i=0}^{k-2}(x-i)=kx^{\underline{k-1}}$

Comme vous devriez pouvoir le remarquer relativement facilement, la formule ainsi obtenue ressemble étrangement à la formule pour calculer la dérivée de la fonction $\displaystyle x^{k}$ . C’est cette analogie, et de nombreuses autres similaires, qui ont motivé la notation.

Solution à l’aide des fonctions génératrices et des récurrences

Plutôt que d’utiliser les principes de base comme nous l’avons fait, il est bien entendu possible de résoudre le problème à l’aide des fonctions génératrices. Comme pour le problème précédent, comme l’ordre est important, il nous faut utiliser une fonction génératrice exponentielle. Pour ce faire, il suffit de remarquer que pour chacun des $\displaystyle n$ objets, on peut soit le choisir, soit ne pas le choisir. Pour chacun des $\displaystyle n$ objets, la fonction génératrice exponentielle est donc $\displaystyle(1+x)$ . En appliquant le principe du produit pour tenir compte des $\displaystyle n$ objets, la fonction génératrice exponentielle est donc:

\displaystyle\sum_{i=0}^{\infty}n^{\underline{i}}\frac{x^{i}}{i!}=(1+x)^{n}

où $\displaystyle n^{\underline{k}}$ dénote la solution du problème.

Pour résoudre le problème à l’aide d’une récurrence, il s’agit de remarquer que, pour choisir $\displaystyle k$ objets, il faut d’abord en choisir $\displaystyle k-1$ , puis choisir le dernier. Pour le dernier élément, nous aurons alors $\displaystyle n-(k-1)$ objets possibles, car il n’y a pas de remise. On obtient donc la récurrence suivante:

\displaystyle\left\{\begin{array}[]{l}x_{k}=(n-k+1)x_{k-1},\leavevmode\nobreak% \ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall k\geq 2\\ x_{1}=n\end{array}\right.

Cette récurrence est en fait plus intéressante lorsqu’on l’écrit en termes de factorielle tombantes. Dans ce cas, nous avons:

\displaystyle\left\{\begin{array}[]{l}n^{\underline{k}}=(n-k+1)n^{\underline{k% -1}},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall k% \geq 2\\ n^{\underline{1}}=n\end{array}\right.