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(\genfrac{}{}{0ex}{}{n-1}{m-1})=m(\genfrac{}{}{0ex}{}{n}{m})$ ;

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

c)   $(\genfrac{}{}{0ex}{}{n}{r})(\genfrac{}{}{0ex}{}{n-r}{m-r})=(\genfrac{}{}{0ex}{}{n}{m})(\genfrac{}{}{0ex}{}{m}{r})$ puis $\sum (\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n-k}{m-k})=2^m(\genfrac{}{}{0ex}{}{n}{m})$ ;

d)   $\sum _{k\le m}(\genfrac{}{}{0ex}{}{k}{n})=(\genfrac{}{}{0ex}{}{m+1}{n+1})$ ;

e)   si $n>0$, $\sum (\genfrac{}{}{0ex}{}{n}{2k})=\sum (\genfrac{}{}{0ex}{}{n}{2k+1})=2^{n-1}$. Modèle:Solution

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

Exercice 4-2

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

$\sum _{k}k(\genfrac{}{}{0ex}{}{n}{k}),\sum _k(-1{)}^{k}k(\genfrac{}{}{0ex}{}{n}{k}),\sum _{k\ne -1}\frac{1}{k+1}(\genfrac{}{}{0ex}{}{n}{k}),\sum _{k\ne -1}\frac{(-1{)}^k}{k+1}(\genfrac{}{}{0ex}{}{n}{k})$.

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.) Modèle:Solution

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}{ccc}& \text{avec ordre}& \text{sans ordre}\\ \text{avec remise}& & \\ \text{sans remise}& & \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.

Exercice 4-5

Soient $k,n,r\in \mathbb{N}$. Combien existe-t-il de $k$-uplets $(x_1,\dots ,x_k)\in \{1,\dots ,n{\}}^k$ tels que $x_2-x_1,x_3-x_2,\dots ,x_k-x_{k-1}\ge r$ ? Modèle:Solution

Exercice 4-6

Soient $k,n,r_1,\dots ,r_k\in \mathbb{N}$. Combien existe-t-il de $k$-uplets $(x_1,\dots ,x_k)\in {\mathbb{N}}^k$ de somme $n$ tels que $x_1\ge r_1,\dots ,x_k\ge r_k$ ? Modèle:Solution

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(S_{p,q}+S_{p,q-1})$.
2. En déduire que $S_{p,q}=\sum _{0\le k\le q}(-1{)}^{q-k}(\genfrac{}{}{0ex}{}{q}{k})k^p$.

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
   $\mathrm{\forall }n\in \mathbb{N}{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)$.

Exercice 4-9

On avance sur la droite réelle, dans le sens positif, en partant de $0$. Pour tout entier $n\ge 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\text{et}\mathrm{\forall }n\in {\mathbb{N}}^{*}{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$).