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}

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 partie ou ne pas faire partie de notre choix. Si $\displaystyle x$ ne fait pas partie de notre sélection, alors les $\displaystyle k$ éléments ont été choisis parmi $\displaystyle n-1$ , ce qui nous donne $\displaystyle\left\langle n-1\atop k\right\rangle$ possibilités. Maintenant, si l’élément $\displaystyle x$ fait partie 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és. En appliquant 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

Listing 26: Coefficient multiensemble

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              def multiensemble(n,k):


                6
                
                
                
                  if k == 1:


                7
                
                
                
                      return n


                8
                
                
                
                  if n == 1:


                9
                
                
                
                      return 1


                10
                
                
                
                  else:


                11
                
                
                
                      return multiensemble(n-1,k) + multiensemble(n,k-1)


                12
                
                
                
              


                13
                
                
                
              A = []


                14
                
                
                
              for n in range(1,11):


                15
                
                
                
                  ligne = [multiensemble(n,k) for k in range(1,11)]


                16
                
                
                
                  A.append(ligne)


                17
                
                
                
              tableau = DataFrame(A)


                18
                
                
                
              tableau.index = [i for i in range(1,11)]


                19
                
                
                
              tableau.columns = [i for i in range(1,11)]


                20
                
                
                
              tableau

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.