4.5 Sans ordre / Avec remise

Le dernier des 4 problèmes consiste à trouver le nombre de façon de choisir $\displaystyle k$ objets parmi $\displaystyle n$ sans ordre et avec remise. Il s’agit du plus difficile des 4 problèmes. Nous allons dénoté la solution du problème par $\displaystyle\left\langle n\atop k\right\rangle$ et étudier les différentes propriétés de ce coefficient.

Une formule explicite

Pour trouver une formule explicite pour le coefficient $\displaystyle\left\langle n\atop k\right\rangle$ , nous allons commencer par regarder un cas particulier, puis revenir à la solution générale par la suite. Supposons qu’on veut choisir 10 objets parmi 5 types différent, avec remise et sans ordre. C’est à dire nous voulons calculer la valeur de $\displaystyle\left\langle 5\atop 10\right\rangle$ . La première étape de la résolution consiste à réaliser que le problème est en fait équivalent à celui de placer 10 étoiles dans 5 cases différentes. En effet, chaque case correspond à un type d’objet, et les étoiles consiste à choisir un objet de ce type. Voici un exemple de l’une des configurations possible.

Ensuite, il s’agit de remarquer que la configuration ci-dessus peut être réécrite de manière symbolique sous la forme:

\displaystyle***||**|*****|

Ou chaque $\displaystyle*$ représente une étoile, et les barres verticales $\displaystyle|$ représentent la délimitation entre chacune des cases. Notez qu’il est inutile de placer une barre verticale au tout début et à la toute fin, car celle-ci serait fixe pour chacune des configuration possible. Donc seule les délimitations entre deux cases sont notés. Le problème est donc équivalent à trouver combien il y a de façon d’arranger 10 étoiles et 4 barres verticales. C’est ici le point le plus intéressant. Ce dernier problème est en fait équivalent à sélectionner 10 emplacement pour nos étoiles, sur une possibilité de 14 emplacement au total. Notre configuration qui nous a servi d’exemple peut donc être illustré comme suit:

Il s’agit donc de choisir 10 cases parmi 14, sans ordre et sans remise, ce que nous savons déjà faire. Le nombre de possibilité est donc:

\displaystyle\binom{14}{10}=\frac{14!}{10!\leavevmode\nobreak\ 4!}

Maintenant, pour le problème général de choisir $\displaystyle k$ objets parmi $\displaystyle n$ sans ordre et avec remise, la solution est très semblable. Il faudra donc trouvé combien il y a de façon d’arranger $\displaystyle k$ étoiles et $\displaystyle n-1$ barres verticales. Le $\displaystyle n-1$ venant du fait que si nous avons $\displaystyle n$ cases, alors il doit y avoir $\displaystyle n-1$ délimitations entre les cases. Ensuite, on réalise que le problème revient donc à placer $\displaystyle k$ étoiles dans $\displaystyle k+n-1$ emplacement, sans ordre et sans remise. Par le principe de la bijection, la solution générale doit donc être:

\displaystyle\left\langle n\atop k\right\rangle=\frac{(k+n-1)!}{k!(n-1)!}

Exemple 4.5.1.

Au Canada, les billets de banques viennent en dénomination de 5$, 10$, 20$, 50$ et 100$. Combien y a-t-il de façon de choisir 4 billets de banques (pas nécessairement différent) ? Comme il est tout à fait acceptable de choisir plusieurs fois la même dénomination, le problème est avec remise. Par contre, l’ordre dans lequel les billets sont choisir n’a pas d’importance, le problème est donc sans ordre. On peut donc appliquer la formule que nous venons de développer. On a donc:

\displaystyle\frac{(4+5-1)!}{4!(5-1)!}=\frac{8!}{4!\leavevmode\nobreak\ 4!}=% \frac{5\times 6\times 7\times 8}{2\times 3\times 4}=\frac{1680}{24}=70% \leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Exemple 4.5.2.

Une usine produit des crayons de $\displaystyle 10$ couleurs différentes. Chacune de ces couleurs sont disponible en très grande quantité. De combien de façon un client peut-il choisir $\displaystyle 7$ crayons de sorte qu’au moins deux d’entre eux soient de la même couleur ? On remarque ici qu’il est plus facile de compter le complément plutôt que de répondre directement à la question. il est facile de voir que le problème se fait sans ordre. Nous allons donc commencer par compter le nombre de façon de choisir $\displaystyle 7$ couleurs parmi $\displaystyle 10$ avec remise, et soustraire le nombre de façon de choisir $\displaystyle 7$ couleurs parmi $\displaystyle 10$ sans remise. On a donc:

\displaystyle\left\langle 10\atop 7\right\rangle-\binom{10}{7}=\frac{(10+7-1)!% }{7!(10-1)!}-\frac{10!}{7!(10-7)!}=\frac{16!}{7!\cdot 9!}-\frac{10!}{7!\cdot 3% !}=11\leavevmode\nobreak\ 440-120=11\leavevmode\nobreak\ 320

Il y a donc $\displaystyle 11\leavevmode\nobreak\ 320$ façon différente de choisir $\displaystyle 7$ crayons de sorte qu’au moins deux d’entre eux soient de la même couleur.

Exemple 4.5.3.

Combien de mots de $\displaystyle 8$ lettres ne contiennent pas la combinaison $\displaystyle AB$ ?

Première méthode: Pour répondre à la question, commençons par considérez tout les mots de $\displaystyle 8$ lettres. Ceci est facile à calculer, il s’agit de $\displaystyle 26^{8}$ . Maintenant, nous allons soustraire tout les mots qui contiennent la séquence $\displaystyle AB$ . Pour ce faire, on doit premièrement choisir les $\displaystyle 6$ lettres manquantes, ce qui peut être fait de $\displaystyle 26^{6}$ façon, puis pour chacune des lettres choisir si elles vont avant ou après le $\displaystyle AB$ , ce qui peut peut être fait de $\displaystyle\left\langle 2\atop 6\right\rangle$ façons. On remarque maintenant que les mots contenant deux fois la suite $\displaystyle AB$ ont été soustrait deux fois, il nous faut donc les ajouter à nouveau. En suivant la même idée, on choisit les $\displaystyle 4$ lettres manquantes, ce qui peut être fait de $\displaystyle 26^{4}$ façons, puis on choisit à quel endroit les placer, soit avant, entre ou après les deux $\displaystyle AB$ , ce qui peut être fait de $\displaystyle\left\langle 3\atop 4\right\rangle$ façons. En continuant de la même façon, on obtient finalement:

\displaystyle 26^{8}-26^{6}\left\langle 2\atop 6\right\rangle+26^{4}\left% \langle 3\atop 4\right\rangle-26^{2}\left\langle 4\atop 2\right\rangle+26^{0}% \left\langle 5\atop 0\right\rangle

Deuxième méthode: On peut aussi résoudre le problème à l’aide d’une récurrence. Dénotons par $\displaystyle a_{n}$ le nombre de mots de $\displaystyle n$ lettre qui ne contiennent pas la suite $\displaystyle AB$ . On remarque premièrement que pour tout les mots de longueur $\displaystyle n-1$ , on peut toujours ajouter une lettre quelconque, sauf dans le cas ou le mot se terminerais par $\displaystyle AB$ . On a donc la récurrence suivante:

\displaystyle\left\{\begin{array}[]{l}a_{n}=26a_{n-1}-a_{n-2},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3\\ a_{1}=26\\ a_{2}=26^{2}-1=675\end{array}\right.

Exemple 4.5.4.

Combien de mots de $\displaystyle 8$ lettres ne contiennent pas la combinaison $\displaystyle AA$ ? Dans ce cas, bien que le problème puisse à première vu sembler très semblable à l’exemple ci-dessus, la solution reste très différente. Le fait que les deux lettres soient identiques veut dire qu’il est possible que la suite AA apparaisse deux fois dans le même mot de manière disjointe, par exemple $\displaystyle AABCAADE$ ou sous la forme d’une suite $\displaystyle AAA$ . Le truc ici est d’utiliser une récurrence. L’idée est très semblable à la récurrence que nous avons obtenu pour les chaines binaires au chapitre précédent. On a donc:

\displaystyle\left\{\begin{array}[]{l}a_{n}=25a_{n-1}+25a_{n-2},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3\\ a_{1}=26\\ a_{2}=26^{2}-1=675\end{array}\right.

Lien avec les factorielles montantes

Le coefficient pour compter des objets avec remise et sans ordre possède plusieurs similarité avec le coefficient binomial. Nous avons déjà rencontrer une formule pour le calculer en terme du coefficient binomial, mais les similarités ne s’arrête pas là.

	$\displaystyle\displaystyle\left\langle n\atop k\right\rangle$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\binom{n+k-1}{k}=\frac{(n+k-1)!}{k!(n-1)!}=\frac{(n+% k-1)(n+k-2)(n+k-3)...3\cdot 2\cdot 1}{k!(n-1)(n-2)(n-3)...3\cdot 2\cdot 1}$
		$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\frac{(n+k-1)(n+k-2)(n+k-3)...(n+1)n}{k!}=\frac{n(n+% 1)(n+2)(n+3)...(n+k-1)}{k!}=\frac{n^{\overline{k}}}{k!}$

Remarquer que cette dernière formule peut être évalué pour tout nombre réel $\displaystyle n$ et va donc nous servir de définition. On a donc les deux formules très similaire suivante:

\displaystyle\binom{n}{k}=\frac{n^{\underline{k}}}{k!}\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \textrm{ et }\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \left\langle n\atop k% \right\rangle=\frac{n^{\overline{k}}}{k!}

Une relation de récurrence

Nous allons maintenant nous intéresser à trouver une relation de récurrence pour les coefficients $\displaystyle\left\langle n\atop k\right\rangle$ . Pour ce faire, commençons par trouver des valeurs initiales. Il est facile de voir qu’il y a $\displaystyle n$ façon de choisir $\displaystyle 1$ objets parmi $\displaystyle n$ . Dans ce cas l’idée de avec ou sans remise, ainsi qu’avec ordre ou sans ordre n’a pas d’importance. De plus, il n’y a qu’une seule façon de choisir $\displaystyle k$ objets parmi $\displaystyle 1$ . Ceci nous donne donc les valeurs initiales suivantes:

\displaystyle\left\langle n\atop 1\right\rangle=n\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{ et }\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \left\langle 1\atop k\right\rangle=1

Maintenant pour la récurrence, nous allons utiliser la méthode de l’élément distingué. Parmi les $\displaystyle n$ éléments, fixons un élément $\displaystyle x$ . En choisissant les $\displaystyle k$ éléments parmi $\displaystyle n$ , l’élément $\displaystyle x$ peut faire parti ou ne pas faire parti de notre choix. Si $\displaystyle x$ ne fait pas partie de notre sélection, alors les $\displaystyle k$ éléments ont été choisi parmi $\displaystyle n-1$ ce qui nous donne $\displaystyle\left\langle n-1\atop k\right\rangle$ possibilité. Maintenant, si l’élément $\displaystyle x$ fait parti de notre sélection, il ne nous reste plus que $\displaystyle k-1$ éléments à choisir, qui peuvent être choisis parmi les $\displaystyle n$ éléments car il y a remise. Nous avons donc dans ce cas $\displaystyle\left\langle n\atop k-1\right\rangle$ possibilité. En applicant le principe de la somme, on obtient donc:

\displaystyle\left\langle n\atop k\right\rangle=\left\langle n-1\atop k\right% \rangle+\left\langle n\atop k-1\right\rangle

La fonction génératrice

Pour trouver la fonction génératrice de la distribution $\displaystyle\left\langle n\atop k\right\rangle$ , l’idée est de commencer par la série géométrique, puis de la dériver.

\displaystyle\begin{array}[]{l}\sum_{k=0}^{\infty}x^{k}=\frac{1}{1-x}\\ \frac{d}{dx}\sum_{k=0}^{\infty}x^{k}=\frac{d}{dx}\frac{1}{1-x}\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{k=1}^{\infty}kx^{k-1% }=\sum_{k=0}^{\infty}(k+1)x^{k}=\frac{1}{(1-x)^{2}}\\ \frac{d}{dx}\sum_{k=0}^{\infty}(k+1)x^{k}=\frac{d}{dx}\frac{1}{(1-x)^{2}}% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{k=1}^{% \infty}k(k+1)x^{k-1}=\sum_{k=0}^{\infty}(k+1)(k+2)x^{k}=\frac{2}{(1-x)^{3}}\\ \frac{d}{dx}\sum_{k=0}^{\infty}(k+1)(k+2)x^{k}=\frac{d}{dx}\frac{2}{(1-x)^{3}}% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{k=1}^{% \infty}k(k+1)(k+2)x^{k-1}=\sum_{k=0}^{\infty}(k+1)(k+2)(k+3)x^{k}=\frac{3!}{(1% -x)^{4}}\\ \end{array}

Ceci nous amène à faire l’hypothèse suivante:

\displaystyle\frac{d^{n-1}}{dx^{n-1}}\sum_{k=0}^{\infty}x^{k}=\sum_{k=0}^{% \infty}\frac{(k+n-1)!}{k!}x^{k}=\frac{(n-1)!}{(1-x)^{n}}=\frac{d^{n-1}}{dx^{n-% 1}}\frac{1}{(1-x)}

Cette dernière égalité peut être démontré facilement à l’aide du principe d’induction. En réarrageant les termes on obtient donc:

\displaystyle\sum_{k=0}^{\infty}\left\langle n\atop k\right\rangle x^{k}=\sum_% {k=0}^{\infty}\frac{(k+n-1)!}{k!(n-1)!}x^{k}=\frac{1}{(1-x)^{n}}

qui est la fonction génératrice que nous cherchions.