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çon 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)=k\prod_{i=0}^{k-2}(% x-i)=kx^{\underline{k-1}}$

Comme vous devriez pouvoir le remarquer relativement facilement, la formule ainsi obtenu ressemble étrangement à la formule pour calculer la dérivé de la fonction $\displaystyle x^{k}$ . C’est cette anologie, et de nombreuse autre similaire, qui ont motivé la notation.