Combinatoire/Exercices/Combinaisons

Exercice 4-1

Soient $m,n,r\in \mathbb {N}$. Montrer les propriétés suivantes de deux façons : par le calcul et par un raisonnement combinatoire.

a)   $n{\binom {n-1}{m-1}}=m{\binom {n}{m}}$ ;

b)   ${\binom {2n}{n}}=\sum {\binom {n}{k}}^{2}$ et plus généralement, ${\binom {n+m}{r}}=\sum {\binom {n}{k}}{\binom {m}{r-k}}$ (identité de Vandermonde) ;

c)   ${\binom {n}{r}}{\binom {n-r}{m-r}}={\binom {n}{m}}{\binom {m}{r}}$ puis $\sum {\binom {n}{k}}{\binom {n-k}{m-k}}=2^{m}{\binom {n}{m}}$ ;

d)   $\sum _{k\leq m}{\binom {k}{n}}={\binom {m+1}{n+1}}$ ;

e)   si $n>0$, $\sum {\binom {n}{2k}}=\sum {\binom {n}{2k+1}}=2^{n-1}$.

Solution

a)   Par le calcul : si $m\leq 0$ ou $m>n$, les deux membres sont nuls. Si $1\leq m\leq n$ alors $n{\binom {n-1}{m-1}}={\frac {n!}{(m-1)!(n-m)!}}=m{\binom {n}{m}}$.

Par un raisonnement combinatoire : ces deux expressions correspondent à deux façons de dénombrer les couples $(A,a)$, où $A$ est une partie à $m$ éléments d'un ensemble fixé de cardinal $n$, et $a\in A$.

b)   La première égalité est le cas $m=r=n$ de la seconde. Démontrons cette dernière.

Par le calcul : si $r<0$ ou $r>m+n$, les deux membres sont nuls. Si $0\leq r\leq m+n$, utiliser la formule du binôme pour développer l'identité polynomiale $(1+X)^{m+n}=(1+X)^{m}(1+X)^{n}$ puis identifier le coefficient de $X^{r}$ (cf. Sommation/Exercices/Formule du binôme#Exercice 5-4).

Par un raisonnement combinatoire : ces deux expressions correspondent à deux façons de dénombrer les parties à r éléments de E ∪ F, où E et F sont deux ensembles disjoints fixés, de cardinaux respectifs m et n, cf. Sommation/Définition et premiers calculs#Établissement des formules à l'aide des dénombrements.

c)   Par le calcul : si $m>n$ ou $m<r$, les deux membres sont nuls. Si $r\leq m\leq n$, cf. Sommation/Exercices/Formule du binôme#Exercice 5-1.

Par un raisonnement combinatoire : ${\binom {n}{r}}{\binom {n-r}{m-r}}$ est le nombre de couples $(A,B)$ tels que $A\subset \{1,\dots ,n\}$, $|A|=r$, $B\subset \{1,\dots ,n\}\setminus A$ et $|B|=m-r$.
${\binom {n}{m}}{\binom {m}{r}}$ est le nombre de couples $(C,D)$ tels que $C\subset \{1,\dots ,n\}$, $|C|=m$, $D\subset C$ et $|D|=r$.
Ces deux ensembles de couples sont en bijection, par $(A,B)\mapsto (A\cup B,A)$, de réciproque $(C,D)\mapsto (C,C\setminus D)$.
Ceci démontre la première égalité. La seconde s'en déduit en sommant sur $r$, ce qui revient à dénombrer de deux façons les couples $(A,C)$, où $A\subset C\subset \{1,\dots ,n\}$ et $|C|=m$ (cf. Sommation/Exercices/Calculs élémentaires#Exercice 2-8).

d)   Par le calcul : si $m<n$, les deux membres sont nuls. Pour $m\geq n$, on peut montrer la formule de deux façons :

• par récurrence sur $m$, pour $n$ fixé : l'initialisation (cas $m=n$) est immédiate et l'hérédité se déduit de la formule de Pascal : Sommation/Exercices/Sommation de combinaisons#Exercice 6-3.
• par identification des coefficients du polynôme $\sum _{n=0}^{m}\left(\sum _{k=n}^{m}{\binom {k}{n}}\right)X^{n}=\sum _{k=0}^{m}\left(\sum _{n=0}^{k}{\binom {k}{n}}X^{n}\right)=\sum _{k=0}^{m}\left(1+X\right)^{k}={\frac {\left(1+X\right)^{m+1}-1}{(1+X)-1}}=\sum _{n=0}^{m}{\binom {m+1}{n+1}}X^{n}$.

Par un raisonnement combinatoire : pour choisir une partie à $n+1$ éléments dans l'ensemble $\{1,\dots ,m+1\}$, on peut choisir d'abord dans $\{1,\dots ,m+1\}$ le plus grand élément $\ell$ de cette partie, puis une partie à $n$ éléments dans l'ensemble $\{1,\dots ,\ell -1\}$. Autrement dit, en notant $k=\ell -1$ : on choisit un entier $k\leq m$ puis une partie à $n$ éléments dans $\{1,\dots ,k\}$.

e)   Soient $P=\sum {\binom {n}{2k}}$ et $I=\sum {\binom {n}{2k+1}}$. Il suffit de montrer que $P=I$ et $P+I=2^{n}$

• Par le calcul : d'après la formule du binôme, $P-I=\left(1-1\right)^{n}=0$ et $P+I=\left(1+1\right)^{n}=2^{n}$.
• Par un raisonnement combinatoire : soient $X$ un ensemble de cardinal $n$ et ${\mathcal {P}}_{p}(X)$ (resp. ${\mathcal {P}}_{i}(X)$) l'ensemble des parties de $X$ de cardinal pair (resp. impair). Alors, $P+I=\left|{\mathcal {P}}_{p}(X)\right|+\left|{\mathcal {P}}_{i}(X)\right|=\left|{\mathcal {P}}(X)\right|=2^{n}$. D'autre part, $P=I$ car si $a$ est un élément fixé de $X$, l'involution de ${\mathcal {P}}(X)$ qui, à toute partie $A\subset X$, associe $A\setminus \{a\}$ si $a\in A$ et $A\cup \{a\}$ si $a\notin A$, se restreint en une bijection entre ${\mathcal {P}}_{p}(X)$ et ${\mathcal {P}}_{i}(X)$.

 

Déduire de l'égalité d) ci-dessus que $\sum _{i=0}^{n}{\binom {m-i}{n}}={\binom {m+1}{n+1}}-{\binom {m-n}{n+1}}$, pour tout $m$ entier ou même complexe.

Solution

D'après d), $\sum _{m-n\leq k\leq m}{\binom {k}{n}}={\binom {m+1}{n+1}}-{\binom {m-n}{n+1}}$ d'où, par changement d'indice : $\sum _{i=0}^{n}{\binom {m-i}{n}}={\binom {m+1}{n+1}}-{\binom {m-n}{n+1}}$. Pour $n$ fixé, on obtient ainsi que deux polynômes en $m$ coïncident en une infinité de points. Ils sont donc égaux.

 

Exercice 4-2

Grâce à la question a) de l'exercice précédent, calculer :

$\sum _{k}k{\binom {n}{k}},\quad \sum _{k}(-1)^{k}k{\binom {n}{k}},\quad \sum _{k\neq -1}{\frac {1}{k+1}}{\binom {n}{k}},\quad \sum _{k\neq -1}{\frac {(-1)^{k}}{k+1}}{\binom {n}{k}}$.

Solution

$\sum _{k}k{\binom {n}{k}}=n\sum _{k}{\binom {n-1}{k-1}}=n\sum _{j}{\binom {n-1}{j}}=n(1+1)^{n-1}=n2^{n-1}$ (si $n=0$, même résultat par calcul direct) ;

$\sum _{k}(-1)^{k}k{\binom {n}{k}}=n\sum _{k}(-1)^{k}{\binom {n-1}{k-1}}=-n\sum _{j}(-1)^{j}{\binom {n-1}{j}}=-n(1-1)^{n-1}=0$ (cas particuliers $n=0$ ou $1$ : $\sum _{k}(-1)^{k}k{\binom {0}{k}}=0$ mais $\sum _{k}(-1)^{k}k{\binom {1}{k}}=-1$) ;

$\sum _{k\neq -1}{\frac {1}{k+1}}{\binom {n}{k}}={\frac {1}{n+1}}\sum _{k\neq -1}{\binom {n+1}{k+1}}={\frac {1}{n+1}}\sum _{j\neq 0}{\binom {n+1}{j}}={\frac {2^{n+1}-1}{n+1}}$ ;

$\sum _{k\neq -1}{\frac {(-1)^{k}}{k+1}}{\binom {n}{k}}={\frac {1}{n+1}}\sum _{k\neq -1}(-1)^{k}{\binom {n+1}{k+1}}=-{\frac {1}{n+1}}\sum _{j\neq 0}(-1)^{j}{\binom {n+1}{j}}=-{\frac {0^{n+1}-1}{n+1}}={\frac {1}{n+1}}$.

 

Exercice 4-3

De combien de manières peut-on distribuer $n$ pièces de 1 euro :

1. à $k$ enfants de sorte que chaque enfant ait au moins un euro ?
2. à $j$ enfants ? (à présent, un enfant peut ne rien recevoir).
3. à $k$ filles et $j$ garçons de sorte que chaque fille ait au moins un euro ?
4. à $k$ filles et $j$ garçons de sorte que chaque fille ait au moins $r$ euros et chaque garçon au moins $s$ euros ?
5. à $k$ filles et $j$ garçons de sorte que chaque fille ait exactement $r$ euros ?

(Dans chaque cas, on suppose qu'il y a au moins un enfant.)

Solution

1. C'est le nombre de $k$-uplets (avec $k\geq 1$ par hypothèse) d'entiers strictement positifs de somme $n$, c'est-à-dire (cf. chapitre « Combinaisons avec répétition ») ${\binom {n-1}{k-1}}$.
2. C'est le nombre de $j$-uplets (avec $j\geq 1$ par hypothèse) d'entiers positifs ou nuls de somme $n$, c'est-à-dire (cf. chapitre « Combinaisons avec répétition ») ${\binom {j+n-1}{n}}$.
3. C'est le nombre de ($k+j$)-uplets (avec $k+j\geq 1$ par hypothèse) d'entiers de somme $n$, tels que les $k$ premiers soient strictement positifs et les $j$ suivants soient positifs ou nuls, ou encore, en ajoutant 1 aux $j$ derniers : le nombre de ($k+j$)-uplets d'entiers strictement positifs de somme $n+j$, c'est-à-dire (d'après la question 1) : ${\binom {n+j-1}{k+j-1}}={\binom {n+j-1}{n-k}}$.

   Remarque : la question 1 est le cas particulier $j=0$ et la question 2 est le cas particulier $k=0$.

4. C'est le nombre de ($k+j$)-uplets d'entiers de somme $n$, tels que les $k$ premiers soient supérieurs ou égaux à $r$ et les $j$ suivants soient supérieurs ou égaux à $s$, ou encore, en retranchant $r-1$ aux $k$ premiers et $s-1$ aux $j$ suivants : le nombre de ($k+j$)-uplets d'entiers strictement positifs de somme $n-(r-1)k-(s-1)j$, c'est-à-dire (d'après la question 1) ${\binom {n-k(r-1)-j(s-1)-1}{k+j-1}}={\binom {n-kr-js+k+j-1}{n-kr-js}}$.

   Remarques :

   • ce nombre est non nul si et seulement si $n\geq kr+js$ ;
   • la question 3 est le cas particulier $r=1,s=0$.

5. C'est le nombre de $j$-uplets d'entiers positifs ou nuls de somme $n-rk$, c'est-à-dire (d'après la question 2) ${\binom {j+n-rk-1}{n-rk}}={\binom {j+n-rk-1}{j-1}}$.

 

Exercice 4-4

1. Une urne contient $n$ boules distinctes et l'on veut sélectionner $k$ boules. Cette sélection peut se faire de quatre manières différentes (avec ou sans remise de la boule qui vient d'être tirée, en tenant compte ou non de l'ordre dans lequel les $k$ boules ont été sélectionnées). Compléter le tableau suivant en indiquant dans chaque cas le nombre de sélections possibles.

   ${\begin{array}{c|c|c|}&{\text{avec ordre}}&{\text{sans ordre}}\\\hline {\text{avec remise}}&&\\\hline {\text{sans remise}}&&\\\hline \end{array}}$

2. Soient $X=\{1,2,\dots ,k\}$ et $Y=\{1,2,\dots ,n\}$. On considère les ensembles :

   $U=\{f\in Y^{X}\mid f{\text{ est injective}}\}$ ;

   $V=\{f\in Y^{X}\mid f{\text{ est croissante (au sens large)}}\}$ ;

   $W=\{f\in Y^{X}\mid f{\text{ est strictement croissante}}\}$.

   Vérifier que $\left|Y^{X}\right|$, $|U|$, $|V|$ et $|W|$ remplissent les cases du tableau de la question 1.

Solution

${\begin{array}{c|c|c|}&{\text{avec ordre}}&{\text{sans ordre}}\\\hline {\text{avec remise}}&\left|Y^{X}\right|=n^{k}&|V|={\binom {n+k-1}{k}}\\\hline {\text{sans remise}}&|U|=A_{n}^{k}&|W|={\binom {n}{k}}\\\hline \end{array}}$

 

Exercice 4-5

Soient $k,n,r\in \mathbb {N}$. Combien existe-t-il de $k$-uplets $\left(x_{1},\dots ,x_{k}\right)\in \{1,\dots ,n\}^{k}$ tels que $x_{2}-x_{1},x_{3}-x_{2},\dots ,x_{k}-x_{k-1}\geq r$ ?

Solution

Ces $k$-uplets $\left(x_{1},\dots ,x_{k}\right)$ sont en bijection avec les $k$-uplets $\left(y_{1},\dots ,y_{k}\right)$ d'entiers tels que $1\leq y_{1}<y_{2}<\dots <y_{k-1}<y_{k}\leq n-\left(k-1\right)\left(r-1\right)$, par l'application qui à $(x_{1},\dots ,x_{k})$ associe $\left(x_{1},x_{2}-\left(r-1\right),x_{3}-2\left(r-1\right),\dots ,x_{k}-\left(k-1\right)\left(r-1\right)\right)$.

Il y en a donc ${\binom {n-\left(k-1\right)\left(r-1\right)}{k}}$.

 

Exercice 4-6

Soient $k,n,r_{1},\dots ,r_{k}\in \mathbb {N}$. Combien existe-t-il de $k$-uplets $\left(x_{1},\dots ,x_{k}\right)\in \mathbb {N} ^{k}$ de somme $n$ tels que $x_{1}\geq r_{1},\dots ,x_{k}\geq r_{k}$ ?

Solution

Ces $k$-uplets sont en bijection avec les $k$-uplets $\left(y_{1},\dots ,y_{k}\right)$ d'entiers tels que $1\leq y_{1}<y_{2}<\dots <y_{k-1}<y_{k}=n+k-\sum r_{i}$, par l'application qui à $(x_{1},\dots ,x_{k})$ associe $\left(x_{1}+1-r_{1},x_{1}+x_{2}+2-r_{1}-r_{2},\dots ,\sum _{i<k}x_{i}+k-1-\sum _{i<k}r_{i},n+k-\sum r_{i}\right)$.

Il y en a donc ${\binom {n+k-1-\sum r_{i}}{k-1}}$.

 

Exercice 4-7

Pour $p,q\in \mathbb {N}$, on note $S_{p,q}$ le nombre de surjections de $\{1,2,\dots ,p\}$ dans $\{1,2,\dots ,q\}$.

1. Démontrer que $S_{p+1,q}=q\left(S_{p,q}+S_{p,q-1}\right)$.
2. En déduire que $S_{p,q}=\sum _{0\leq k\leq q}(-1)^{q-k}{\binom {q}{k}}k^{p}$.

Solution

1. Choisir une surjection $f:\{1,2,\dots ,p+1\}\to \{1,2,\dots ,q\}$ revient à choisir $f(p+1)\in \{1,2,\dots ,q\}$ puis la restriction de $f$ à $\{1,2,\dots ,p\}$, qui doit être une surjection de $\{1,2,\dots ,p\}$ dans $\{1,2,\dots ,q\}$ ou dans $\{1,2,\dots ,q\}\setminus \{f(p+1)\}$.
2. Récurrence sur $p$.
   • Initialisation : $S_{0,q}={\begin{cases}1&{\text{si }}q=0\\0&{\text{sinon}}\end{cases}}=(-1)^{0}{\binom {0}{0}}0^{q}$.
   • Hérédité : soit $p\geq 1$. Supposons que $\forall q\in \mathbb {N} \quad S_{p-1,q}=\sum _{0\leq k\leq q}(-1)^{q-k}{\binom {q}{k}}k^{p-1}$.
     Alors, d'après la question précédente :

   ${\begin{aligned}S_{p,q}&=q\left(\sum _{0\leq k\leq q}(-1)^{q-k}{\binom {q}{k}}k^{p-1}+\sum _{0\leq k<q}(-1)^{q-1-k}{\binom {q-1}{k}}k^{p-1}\right)\\&=q^{p}+q\sum _{0\leq k<q}(-1)^{q-k}\left({\binom {q}{k}}-{\binom {q-1}{k}}\right)k^{p-1}\\&=q^{p}+\sum _{1\leq k<q}(-1)^{q-k}q{\binom {q-1}{k-1}}k^{p-1}\\&=q^{p}+\sum _{1\leq k<q}(-1)^{q-k}{\binom {q}{k}}k^{p}\\&=\sum _{0\leq k\leq q}(-1)^{q-k}{\binom {q}{k}}k^{p}.\end{aligned}}$

Voir aussi Formule du crible/Dénombrement des surjections et Formule d'inversion de Pascal/Application au dénombrement des surjections.

 

Exercice 4-8

On note $S(p,q)$ le nombre de Stirling de seconde espèce, égal au nombre de partitions de $\{1,2,\dots ,p\}$ en $q$ parties.

1. Démontrer que $S(p,q)$ est lié au nombre $S_{p,q}$ de surjections de l'exercice précédent par : $S_{p,q}=q!\,S(p,q)$.
2. En déduire une formule explicite pour $S(p,q)$, ainsi qu'une relation de récurrence.
3. Redémontrer directement cette relation de récurrence.
4. En utilisant cette relation, démontrer que
   $\forall n\in \mathbb {N} \quad X^{n}=\sum _{k=0}^{n}S(n,k)(X)_{k}$,
   où $(X)_{k}$ désigne le polynôme « factorielle décroissante » : $(X)_{k}:=X(X-1)\dots (X-k+1)$.

Solution

1. Choisir une surjection de $\{1,2,\dots ,p\}$ dans $\{1,2,\dots ,q\}$ revient à choisir une partition de $\{1,2,\dots ,p\}$ en $q$ parties, puis une bijection qui associe à chacune de ces parties un élément de $\{1,2,\dots ,q\}$.
2. $S(p,q)={\frac {1}{q!}}\sum _{0\leq k\leq q}(-1)^{q-k}{\binom {q}{k}}k^{p}$ et $S(p+1,q)=S(p,q-1)+qS(p,q)$.
3. Dans l'ensemble des partitions de $\{1,2,\dots ,p+1\}$ en $q$ parties, notons ${\mathcal {A}}$ le sous-ensemble des partitions dont l'une des parties est le singleton $\{p+1\}$, et ${\mathcal {B}}$ le sous-ensemble complémentaire. Ainsi, $S(p+1,q)=|A|+|B|$.
   Notons également ${\mathcal {A}}'$, resp. ${\mathcal {B}}'$, l'ensemble des partitions de $\{1,2,\dots ,p\}$ en $q-1$ parties, resp. $q$ parties.
   L'application de ${\mathcal {A}}$ dans ${\mathcal {A}}'$ qui, à chaque $A\in {\mathcal {A}}$ associe la partition constituée des mêmes parties que $A$ sauf le singleton $\{p+1\}$, est bijective, donc $|{\mathcal {A}}|=|{\mathcal {A}}'|=S(p,q-1)$.
   L'application de ${\mathcal {B}}$ dans ${\mathcal {B}}'$ qui, à chaque $B\in {\mathcal {B}}$, associe la partition déduite de $B$ en « gommant » $p+1$ du « bloc » qui le contient, est telle que chaque partition $B'\in {\mathcal {B}}'$ a exactement $q$ antécédents dans ${\mathcal {B}}$, formés en « recollant » $p+1$ à l'un des $q$ « blocs » de $B'$. Donc $|{\mathcal {B}}|=q|{\mathcal {B}}'|=qS(p,q)$.
4. Récurrons. $\sum _{k=0}^{0}S(0,k)(X)_{k}=S(0,0)(X)_{0}=1=X^{0}$ et si $X^{n}=\sum _{k=0}^{n}S(n,k)(X)_{k}$ alors

   ${\begin{aligned}X^{n+1}&=\sum _{k=0}^{n}S(n,k)(X)_{k}(X-k+k)\\&=\sum _{k=0}^{n}\left[S(n,k)(X)_{k+1}+kS(n,k)(X)_{k}\right]\\&=0S(n,0)(X)_{0}+S(n,n)(X)_{n+1}+\sum _{k=1}^{n}\left[S(n,k-1)+kS(n,k)\right](X)_{k}\\&=0+(X)_{n+1}+\sum _{k=1}^{n}S(n+1,k)(X)_{k}\\&=\sum _{k=0}^{n+1}S(n+1,k)(X)_{k}.\end{aligned}}$

 

Exercice 4-9

On avance sur la droite réelle, dans le sens positif, en partant de $0$. Pour tout entier $n\geq 1$, on note $T_{n}$ le nombre de façons d'effectuer un trajet de longueur $n-1$ en faisant uniquement des pas de longueur $1$ ou $2$. Les deux questions suivantes sont indépendantes.

1. Démontrer que $T_{n}$ est égal au $n$-ième nombre de Fibonacci $F_{n}$, défini par

   $F_{1}=F_{2}=1\quad {\text{et}}\quad \forall n\in \mathbb {N} ^{*}\quad F_{n+2}=F_{n+1}+F_{n}$.

2. Exprimer $T_{n}$ comme une somme de coefficients binomiaux, en comptant le nombre $S_{n,k}$ de façons d'effectuer un trajet de longueur $n-1$ avec k pas de longueur $2$ (et les autres de longueur $1$).

Solution

1. Récurrence d'ordre 2.
   • Initialisation : $T_{1}=1$ (il n'y a qu'une façon de faire un trajet de longueur $0$ : en restant sur place) et $T_{2}=1$ (on ne peut faire un trajet de longueur $1$ que par un pas de longueur 1) donc $T_{1}=F_{1}$ et $T_{2}=F_{2}$.
   • Hérédité : pour tout $n\geq 2$, $T_{n+1}=T_{n}+T_{n-1}$, en partitionnant les trajets de longueur $n$ en ceux finissant par un pas de longueur $1$ (donc précédés d'un trajet de longueur $n-1$) et ceux finissant par un pas de longueur $2$ (donc précédés d'un trajet de longueur $n-2$). On en déduit que si (hypothèse de récurrence) $T_{n-1}=F_{n-1}$ et $T_{n}=F_{n}$, alors $T_{n+1}=F_{n+1}$.
2. Sur un trajet de longueur $n-1$, si l'on fait $k$ pas de longueur $2$, on en fait $n-1-2k$ de longueur $1$, soit au total $n-1-k$ pas. Le nombre $S_{n,k}$ de façon de choisir, parmi ces $n-1-k$ pas, lesquels seront les $k$ pas de longueur $2$, est égal à ${\binom {n-1-k}{k}}$ (qui n'est non nul que si $0\leq k\leq n-1-k$, c'est-à-dire $0\leq k\leq {\frac {n-1}{2}}$), et $T_{n}=\sum _{k\in \mathbb {Z} }{\binom {n-1-k}{k}}=\sum _{k=0}^{\left\lfloor {\frac {n-1}{2}}\right\rfloor }{\binom {n-1-k}{k}}$.