# 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}$.
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.
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}}$.
    $\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 :
* à $k$ enfants de sorte que chaque enfant ait au moins un euro ?
* à $j$ enfants ? (à présent, un enfant peut ne rien recevoir).
* à $k$ filles et $j$ garçons de sorte que chaque fille ait au moins un euro ?
* à $k$ filles et $j$ garçons de sorte que chaque fille ait au moins $r$ euros et chaque garçon au moins $s$ euros ?
* à $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.)
* 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}}$.
* 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}}$.
* 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$.
* 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$.
* 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

* 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}}$
* 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.
${\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$ ?
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}$ ?
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\}$.
* Démontrer que $S_{p+1,q}=q\left(S_{p,q}+S_{p,q-1}\right)$.
* En déduire que $S_{p,q}=\sum _{0\leq k\leq q}(-1)^{q-k}{\binom {q}{k}}k^{p}$.
* 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)\}$.
* 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.
* 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)$.
* En déduire une formule explicite pour $S(p,q)$, ainsi qu'une relation de récurrence.
* Redémontrer directement cette relation de récurrence.
* 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)$.
* 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\}$.
* $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)$.
* 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)$.
* 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.
* 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}$.
* 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$).
* 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}$.
* 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}}$.
| Permutations | Sommaire |