Math sup : dénombrement

Ce genre d'exercices se traite très facilement en utilisant un tableau à double entrée dans lequel on inscrit les informations à notre disposition : On complète alors le tableau de proche en proche de sorte d'obtenir les bons totaux sur chaque ligne et chaque colonne. Par exemple, sur la première ligne de la colonne "Chimie", on peut facilement inscrire le chiffre 9. On obtient donc

Un triangle est déterminé par 3 droites (ses côtés). Il y a autant de triangles que de possibilités de choisir 3 droites parmi $n$, c'est-à-dire $\binom n3$.

Une anagramme correspond à une permutation des lettres d'un mot. Mais si on permute deux lettres identiques, on trouve le même mot! On doit donc diviser le nombre total de permutations par le nombres de permutations entre lettres identiques. On trouve donc :

• MATHS : 5!
• RIRE : 4!/2!
• ANANAS : 6!/(2!3!)

Pour compter les anagrammes d'ANANAS, on peut aussi :

• choisir la position des 3 lettres $A$ : il y a $\binom 63$ choix possibles;
• choisir la position des 2 lettres $N$ : il y a $\binom 32$ choix possibles (il reste 3 places une fois qu'on a placé les $A$);
• le $S$ est alors placé.

Le nombre d'anagrammes d'ANANAS est donc $$\binom 63\times \binom 32=\frac{6!}{2!\cdot 3!}.$$

Les $p$ tours doivent être sur des lignes différentes. On commence par choisir les $p$ lignes où sont les tours. Il y a $\binom np$ choix possibles. Une fois ces lignes choisies, on choisit les colonnes où sont les tours. Pour la tour située sur la première ligne, on a $n$ choix, pour la tour située sur la deuxième ligne, on a $n-1$ choix, et ainsi de suite jusqu'à la $p$-ième ligne où on a $n-p+1$ choix. On obtient $n(n-1)\dots(n-p+1)$ choix. Finalement, le nombre total de façons différentes dont l'on peut placer les tours sans qu'elles puissent se prendre est égal à $\binom np\times n(n-1)\dots(n-p+1)$.

On va s'inspirer de la démonstration de la formule du triangle de Pascal. Soit $E$ un ensemble ayant $m$ éléments, et $F$ une partie de $E$ ayant $q$ éléments. On cherche le nombre de parties de $E$ ayant exactement $p$ éléments.

• Une telle partie peut ne contenir aucun élément de $F$. Il y a exactement $\binom{m-q}p$ telles parties.
• Une telle partie peut contenir exactement un élément de $F$. On a $\binom q1$ choix pour cet élément, et $\binom{m-q}{p-1}$ choix pour les autres.
• Plus généralement on compte le nombre de parties à $p$ éléments de $E$ contenant exactement $k$ éléments de $F$. Il y a $\binom q k$ possibilités pour choisir ces éléments de $F$, et $\binom{m-q}{p-k}$ possibilités pour choisir les autres éléments (ils sont $p-k$, à choisir parmi $m-q$). Le nombre de parties recherché dans ce cas est donc $\binom qk\times\binom {m-q}{p-k}$.

Faisant la somme pour $k$ de $0$ à $q$, on trouve la formule souhaitée. Remarquons que ce dénombrement fonctionne même si $p>m-q$, à condition d'utiliser la convention $\binom nk=0$ pour $k>n$.

$\left(\begin{array}{c}2n\\n\end{array}\right)$ est le nombre de parties à $n$ éléments dans un ensemble à $2n$ éléments. Pour compter ce nombre de parties, on peut aussi diviser l'ensemble en deux sous-ensembles contenant chacun $n$ éléments. Pour obtenir $n$ éléments, on peut en prendre $k$ dans le premier, ie $\left(\begin{array}{c}n\\k\end{array}\right)$ choix, et $n-k$ dans le deuxième, soit $\left(\begin{array}{c}n\\n-k\end{array}\right)$ choix. On a donc : $$\left(\begin{array}{c}2n\\n\end{array}\right)=\sum_{k=0}^n \left(\begin{array}{c}n\\k\end{array}\right)\times \left(\begin{array}{c}n\\n-k\end{array}\right)=\sum_{k=0}^n \left(\begin{array}{c}n\\k\end{array}\right)^2$$ puisque $\left(\begin{array}{c}n\\n-k\end{array}\right)=\left(\begin{array}{c}n\\k\end{array}\right)$.
On peut aussi démontrer ce résultat sans dénombrement en remarquant que $\left(\begin{array}{c}2n\\n\end{array}\right)$ est le coefficient devant $X^n$ du polynôme $(X+1)^{2n}$. On retrouve l'autre valeur en écrivant $(X+1)^{2n}=(X+1)^n (X+1)^n$ et en identifiant.

Le coefficient binomial $\dbinom{n+1}{p+1}$ désigne le nombre de parties à $p+1$ éléments dans l'ensemble $\{0,\dots,n\}$ qui a $n+1$ éléments. Soit $E$ une telle partie, et $k$ le plus grand entier qu'elle contient. Puisque la partie contient $p+1$ éléments, on a $k\geq p$. De plus, cet élément choisi, il reste $p$ éléments à choisir dans l'ensemble $\{0,\dots,k-1\}$ qui contient $k$ éléments, c'est-à-dire qu'il reste $\dbinom{k}{p}$ choix.
Une autre méthode pour démontrer cette propriété est de procéder par récurrence sur $n$. La formule est clairement vraie pour $n=0$ (ce qui implique $p=0$). Supposons la propriété vraie au rang $n$, c'est-à-dire que pour tout $p\leq n$, la formule donnée est vérifiée. Prouvons-la au rang $n+1$. Pour cela, prenons $p\leq n+1$. Si $p\leq n$, alors on a \begin{eqnarray*} \sum_{k=p}^{n+1}\dbinom{k}{p}&=&\sum_{k=p}^n \dbinom{k}{p}+\dbinom{n+1}{p}\\ &=&\dbinom{n+1}{p+1}+\dbinom{n+1}{p}\textrm{ (hypothèse de récurrence)}\\ &=&\dbinom{n+2}{p+1}\textrm{ (formule du triangle de Pascal)}. \end{eqnarray*} Si $p=n+1$, la formule est aussi vérifiée. La propriété est donc aussi vraie au rang $n+1$.
On peut aussi démontrer la formule par "télescopage" en remarquant que, pour $k>p$, on a $$\binom kp =\binom{k+1}{p+1}-\binom{k}{p+1}$$ et donc que \begin{align*} \sum_{k=p}^{n}\binom k p&=\binom p p+\sum_{k=p+1}^{n}\left(\binom{k+1}{p+1}-\binom{k}{p+1}\right)\\ &=1+\binom{n+1}{p+1}-\binom{p+1}{p+1}\\ &=\binom{n+1}{p+1}. \end{align*}

On commence par remarquer que, si on a prouvé que le nombre de parties de cardinal pair d'un ensemble à $n$ élément est $2^{n-1}$, alors le nombre de parties du même ensemble qui sont de cardinal impair vaut également $2^{n-1}$. En effet, le nombre total de parties, qui vaut $2^n$, est la somme du nombre de parties de cardinal pair et du nombre de parties de cardinal impair.
Démontrons maintenant le résultat. On procède par récurrence sur $n$. Si $n=1$, la seule partie de $E$ de cardinal pair est $\varnothing$. On a bien $1=2^0$. Supposons maintenant le résultat démontré au rang $n$, et prouvons-le au rang $n+1$. Soit donc $E$ de cardinal $n+1$, et écrivons $E=\{a\}\cup F$ où $F$ est de cardinal $n$. Alors une partie de $E$ de cardinal pair

• ou bien contient $a$, et on doit alors la compléter avec une partie de cardinal impair de $F$. Il y a $2^{n-1}$ telles parties.
• ou bien ne contient pas $a$, et c'est également une partie de cardinal pair de $F$. Il y a là aussi exactement $2^{n-1}$ telles parties.

Finalement, on trouve que le nombre de parties de $E$ de cardinal pair vaut $2^{n-1}+2^{n-1}=2^n=2^{(n+1)-1}$. L'hypothèse de récurrence est donc prouvée au rang $n+1$.

Pour fabriquer une telle partition, on peut partir d'une liste ordonnée des $np$ éléments, et les grouper ensuite $p$ par $p$. Il y a $(np)!$ façons d'écrire ces listes ordonnées, mais plusieurs listes peuvent donner la même partition. D'abord, sur chaque groupe de $p$ éléments qu'on a choisi, on peut opérer une permutation qui ne changera par la partition obtenue. Pour chaque groupe, il y a $p!$ telles permutations, et comme il y a $n$ groupes de $p$ éléments, on obtient finalement $(p!)^n$ telles permutations. Ensuite, on peut également permuter tous ces groupes les uns avec les autres. Il y a $n!$ telles permutations de ces groupes. Finalement, on trouve que le nombre de partitions d'un ensemble de cardinal $np$ en $n$ parties de cardinal $p$ est $\displaystyle \frac{(np)!}{(p!)^n n!}$.