4.4 Sans ordre / Sans remise

En applicant la méthode de l’élément distingué au problème de choisir des objets sans ordre et sans remise, il nous est possible d’obtenir une formule de récurrence particulièrement utile. L’idée est la suivante: Supposons que nous devons choisir $\displaystyle k$ objets parmi $\displaystyle n$ sans ordre et sans remise. Fixons un élément $\displaystyle x$ quelconque parmi les $\displaystyle n$. Alors $\displaystyle x$ peut faire parti de $\displaystyle k$ éléments choisi ou non. S’il fait parti des $\displaystyle k$ éléments, alors il nous en reste $\displaystyle k-1$ à choisir, ce qui peut être fait de $\displaystyle\binom{n-1}{k-1}$ façon. D’un autre côté, si $\displaystyle x$ ne fait pas parti des $\displaystyle k$ objets choisi, alors il y a $\displaystyle\binom{n-1}{k}$ façons de choisir les $\displaystyle k$ objets. En combinant ces deux valeurs, on obtient:

Cette formule est bien entendu valide si $\displaystyle n\geq 2$ et $\displaystyle 1<k<n$. Il nous faut donc chercher les valeurs au limite. Pour ce faire, il est facile de remarquer que:

Cette relation de récurrence nous permet de calculer facilement les petites valeurs du coefficient binomial. Ceci est accompli à l’aide du triangle de Pascal.

La triangle est obtenu en plaçant premièrement un $\displaystyle 1$ sur la première ligne, et toutes les autres lignes sont obtenues en commençant et terminant par un $\displaystyle 1$, et les autres valeurs sont la somme des deux valeurs qui se trouve immédiatement au dessus. Le triangle de Pascal n’est en fait qu’une manière visuelle de représenter la formule de récurrence. Si on souhaite trouver la valeur de $\displaystyle\binom{4}{2}$, on regardera dans la ligne identifié $\displaystyle n=4$, puis on prendra le $\displaystyle 3^{e}$ élément. Attention, il ne s’agit pas d’un typo. Le premier élément de chaque ligne est l’élément $\displaystyle i=0$. On aura donc:

Ce qui correspond à la valeur que vous auriez obtenu en calculant les factoriels (vous devriez le vérifier !!!).

Combien y a-t-il de sous-ensembles de $\displaystyle A$ si $\displaystyle A$ est un ensemble de $\displaystyle n$ éléments ? Pour trouver la réponse, nous allons appliquer deux approches différentes, ce qui nous permettra par la même occasion d’obtenir une formule intéressante pour les coefficients binomiaux.

Comme première méthode pour compter le nombre de sous-ensemble, nous allons appliquer le principe du produit. Pour ce faire, remarquer que pour former un sous-ensemble de $\displaystyle A$, il suffit de déterminer pour chacun des $\displaystyle n$ éléments s’il fait parti du sous-ensemble ou non. On a donc $\displaystyle 2$ options pour chacun des $\displaystyle n$ éléments de $\displaystyle A$, ce qui nous donne $\displaystyle 2^{n}$ possibilités.

Comme deuxième approche, remarquons qu’en comptant le nombre de façon de choisir $\displaystyle k$ éléments parmi les $\displaystyle n$ éléments de l’ensemble $\displaystyle A$, nous avons en fait déterminer le nombre de sous-ensemble de $\displaystyle A$ contenant exactement $\displaystyle k$ éléments. Maintenant, comme un sous-ensemble peut avoir un nombre d’éléments allant de $\displaystyle 0$ jusqu’à $\displaystyle n$, il suffit d’appliquer le principe de la somme pour obtenir $\displaystyle\sum_{i=0}^{n}\binom{n}{i}$ sous-ensemble de $\displaystyle A$.

Comme nous avons compter deux fois exactement le même chose, on note que ces deux valeurs doivent être égale. On obtient donc l’égalité suivante:

De plus, au chapitre $\displaystyle 1$ nous avons démontré en utilisant le principe de la bijection qu’il y a autant de sous-ensemble de $\displaystyle A$ contenant $\displaystyle k$ éléments que de sous-ensemble de $\displaystyle A$ contenant $\displaystyle n-k$ éléments. Ceci nous donne donc la formule:

Nous voulons maintenant trouver une fonction génératrice pour les coefficients binomiaux. Cette dernière est particulièrement facile à trouver moyennant une petite observation. Considérons le polynôme $\displaystyle(1+x)^{n}$. On a donc un produit de $\displaystyle n$ facteurs:

De combien de façon peut ton choisir un terme de chacun des facteurs pour obtenir $\displaystyle x^{k}$ ? Il s’agit de remarquer que pour obtenir $\displaystyle x^{k}$ il faut choisir exactement $\displaystyle k$ fois un $\displaystyle x$, et $\displaystyle n-k$ fois un $\displaystyle 1$. Comme l’ordre n’est pas important, et qu’il n’est pas possible de choisir plusieurs fois le même $\displaystyle x$, la solution est donné par le coefficient binomial $\displaystyle\binom{n}{k}$. En effectuant le produit on obtiendra donc $\displaystyle\binom{n}{k}$ fois un $\displaystyle x^{k}$, ce qui sera donc le coefficient de $\displaystyle x^{k}$ après avoir effectué le produit. Ceci nous permet donc d’obtenir la formule suivante:

Maintenant en se rappelant que le coefficient binomial devient $\displaystyle 0$ si $\displaystyle k>n$, on peut étendre notre somme jusqu’à l’infinie pour obtenir la fonction génératrice.