Exercices corrigés - Dénombrements (théoriques)

Soit $n\geq 2$ un entier. Combien y-a-t-il de couples $(x,y)$ dans $\{1,\dots,n\}^2$ tels que

$x+y=n$;
$x<y$;
$|x-y|\leq 1$;

Exercice 2

- Partitions d'un entier [Signaler une erreur] [Ajouter à ma feuille d'exos]

On appelle partition d'un entier naturel $n$ toute suite finie $(\alpha_1,\dots,\alpha_k)\in (\mathbb N^*)^k$ telle que $\alpha_1\geq \cdots\geq\alpha_k$ et $\alpha_1+\cdots+\alpha_k=n$. On note $\Gamma_n$ l'ensemble des partitions de l'entier $n$.

Déterminer $\Gamma_1,\Gamma_2,\Gamma_3,\Gamma_4$.
Pour $j,n\in\mathbb N$, on note $Y_{n,j}$ l'ensemble des partitions de $n$ dont le premier terme est inférieur ou égal à $j$, et on note $y_{n,j}$ le cardinal de $Y_{n,j}$. On convient que $y_{0,0}=1$.
1. Calculer $y_{n,1}$.
2. On se propose de démontrer que, si $2\leq j\leq n$, alors $y_{n,j}=y_{n,j-1}+y_{n-j,\min(j,n-j)}$. Démontrer cette relation pour $j=n$.
3. Pour $2\leq j<n$, vérifier que $y_{n,j}=y_{n,j-1}+y_{n-j,j}$ puis conclure.
Écrire une fonction Python qui prend en argument un entier $n\geq 1$ et qui renvoie le cardinal de $\Gamma_n$.

On a $\Gamma_1=\{(1)\}$, $\Gamma_2=\{(2),(1,1)\}$, $\Gamma_3=\{(3),(2,1),(1,1,1)\}$, $\Gamma_4=\{(4), (3,1), (2,2), (2,1,1), (1,1,1,1)\}$.
1. Il n'y a qu'une seule partition qui commence par un $1$ : celle qui comporte $n$ fois le chiffre $1$. Donc $y_{n,1}=1$.
2. Lorsque $j=n$, on cherche à déterminer toutes les partitions. On les sépare en deux parties disjointes :
  - Les partitions qui commencent par un $n$ : il n'y en a qu'une, la partition $(n)$, et $y_{n-n,0}=y_{0,0}=1$.
  - Les partitions qui commencent par un nombre inférieur ou égal à $n-1$ : il y en a $y_{n,n-1}$.
  D'où $y_{n,n}=y_{n,n-1}+y_{0,0}$ qui est le résultat demandé.
3. De la même façon, on sépare les partitions de $n$ commençant par un nombre inférieur ou égal à $j$ en deux parties disjointes :
  - les partitions commençant par $j$; il reste alors $n-j$ à partager en une partition qui commence par un nombre inférieur ou égal à $j$; il y a donc exactement $y_{n-j,j}$ telles partitions.
  - les partitions commençant par un nombre inférieur ou égal à $j-1$. Il y a exactement $y_{n,j-1}$ telles partitions.
  On a donc prouvé, pour $2\leq j\leq n-1$, la relation $y_{n,j}=y_{n,j-1}+y_{n-j,j}$. Si $j\leq n-j$, c'est exactement la relation demandée. Si $j>n-j$, alors on a $y_{n-j,j}=y_{n-j,n-j}$ (plus généralement, si $q>p$, alors $y_{p,q}=y_{p,p}$ car toute partition de $p$ qui commence par un nombre inférieur ou égal à $q$ commence en réalité par un nombre inférieur ou égal à $p$). Dans tous les cas, on a prouvé le résultat demandé.
En utilisant la formule démontrée à la question précédente, en utilisant un tableau, et en faisant attention aux indices et à l'initialisation (par exemple, $y_{n,0}=0$), voici une fonction possible :

def partitions(n):
    y=[[1]]
    for i in range(1,n+1):
        y.append([0,1])
        for j in range(2,i+1):
            y[i].append(y[i][j-1]+y[i-j][min(j,i-j)])
    return y[n][n]
Par exemple, un appel \verb+partitions(8)+ donne 22.

Exercice 3

- Combinaisons avec répétitions [Signaler une erreur] [Ajouter à ma feuille d'exos]

Pour $n\in\mathbb N^*$ et $p\in\mathbb N$, on note $\Gamma_n^p$ le nombre de $n$-uplets $(x_1,\dots,x_n)\in\mathbb N^n$ tels que $x_1+\dots+x_n=p$.

Déterminer $\Gamma_n^0$, $\Gamma_n^1$, $\Gamma_n^2$, $\Gamma_1^p$ et $\Gamma_2^p$.
Démontrer que, pour tout $n\in\mathbb N^*$, pour tout $p\in\mathbb N$, $$\Gamma_{n+1}^p=\Gamma_n^0+\Gamma_n^1+\dots+\Gamma_n^p.$$
En déduire que, pour tout $n\in\mathbb N^*$ et tout $p\in\mathbb N$, $$\Gamma_n^p=\binom{n+p-1}p.$$

Exercice 4

- Contenant un et un seul élément d'une partie donnée [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $n$ un entier naturel non nul et soit $E$ un ensemble à $n$ éléments. Soit $p$ un entier naturel tel que $1\leq p\leq n$ et soit $A$ une partie de $E$ à $p$ éléments. Quel est le nombre de parties de $E$ qui contiennent exactement un et un seul élément de $A$?

Exercice 5

- Parties disjointes [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $E$ un ensemble à $n$ éléments.

Soit $X$ une partie à $p$ éléments de $E$. Combien y-a-t-il de parties $Y$ de $E$ disjointes de $X$?
Combien y-a-t-il de couples $(X,Y)$ formés de parties disjointes de $E$?

Exercice 6

- Inclusion [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $E$ un ensemble à $n$ éléments; Combien y-a-t-il de couples $(X,Y)$ de parties de $E$ tels que $X\subset Y$?

Exercice 7

- Dénombrer les réunions donnant l'ensemble [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $E$ un ensemble de cardinal $n$ et $i\in\{0,\dots,n\}$.

Déterminer $\textrm{card}(\Omega_i)$, où $$\Omega_i=\{(A,B)\in \mathcal P(E);\ A\cup B=E,\ \textrm{card}(B)=i\}.$$
Combien y-a-t-il de couples de parties $(A,B)$ de $E$ telles que $A\cup B=E$.

Exercice 8

- Parties de cardinal pair [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $E$ un ensemble fini de cardinal $n\geq 1$. Démontrer que le nombre de parties de $E$ de cardinal pair vaut $2^{n-1}$.

Exercice 9

- Partition d'un ensemble [Signaler une erreur] [Ajouter à ma feuille d'exos]

Combien existe-t-il de partitions d'un ensemble de cardinal $np$ en $n$ parties de cardinal $p$?

Exercice 10

- Partie sans entiers consécutifs [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $n\geq 1$ et $p\geq 0$ des entiers. On note $F_n^p$ l'ensemble des parties de $\{1,\dots,n\}$ à $p$ éléments ne contenant aucune paire d'entiers consécutifs. On note $K_n^p$ le cardinal de $F_n^p$.

Déterminer $K_n^p$ quand $p> (n+1)/2$.
Soit $\{a_1,\dots,a_p\}$ un élément de $F_n^p$ écrit de sorte que $a_i<a_{i+1}$. On pose $b_k=a_k+1-k$. Prouver que $1\leq b_1<b_2<\dots<b_p\leq n+1-p$.
Soit $G_n^p$ l'ensemble des parties à $p$ éléments de $\{1,\dots,n+1-p\}$. Construire une bijection de $F_n^p$ sur $G_n^p$.
En déduire la valeur de $K_n^p$.
Application : au loto on tire 6 numéros dans $\{1,\dots,49\}$. Combien de tirages ne contiennent aucune paire d'entiers consécutifs?

Exercice 11

- Nombre de partitions d'un ensemble à $n$ éléments [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $n$ et $k$ deux entiers strictement positifs.

Montrer qu’il n’existe qu’un nombre fini de partitions de l’ensemble $\{1,\dots,n\}$ en $k$ parties. Dans la suite, on notera $S(n,k)$ le nombre de ces partitions. On pose de plus $S(0,0)=1$ et $S(n,0)=S(0,k)=0$.
Que vaut $S(n,k)$ pour $k>n$?
Que vaut $S(n,1)$?
Démontrer que $S(n,k)=S(n-1,k-1)+kS(n-1,k)$.
Rédiger une fonction récursive Python permettant de calculer $S(n,k)$.

Exercice 12

- Nombres de Bell [Signaler une erreur] [Ajouter à ma feuille d'exos]

Pour $n\in\mathbb N$, on note $B_n$ le nombre de partitions d'un ensemble $E$ de cardinal $n$. On pose $B_0=1$.

Calculer $B_1$, $B_2$ et $B_3$.
Établir la formule de récurrence $$B_{n+1}=\sum_{k=0}^n \binom nk B_k.$$

Exercice 13

- Nombre de fonctions (strictement) croissantes [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $n,p\geq 1$ deux entiers.

Combien y-a-t-il de fonctions strictement croissantes de $\{1,\dots,p\}$ dans $\{1,\dots,n\}$?
1. Soit $f:\{1,\dots,p\}\to\{1,\dots,n\}$ une fonction croissante. On pose $\phi(f)$ la fonction définie sur $\{1,\dots,p\}$, à valeurs dans $\{1,\dots,n+p-1\}$, par $\phi(f)(k)=f(k)+k-1$. Démontrer que $\phi(f)$ est strictement croissante.
2. Soit $g:\{1,\dots,p\}\to\{1,\dots,n+p-1\}$ une fonction strictement croissante. On pose $\psi(g)$ la fonction définie sur $\{1,\dots,p\}$, à valeurs dans $\{1,\dots,n\}$, par $\psi(g)(k)=g(k)-k+1$. Démontrer que $\psi(g)$ est croissante.
3. Combien y-a-t-il de fonctions croissantes de $\{1,\dots,p\}$ dans $\{1,\dots,n\}$?

Exercice 14

- Dérangement et problème des rencontres [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $E$ un ensemble à $n$ éléments. On appelle dérangement de $E$ toute permutation de $E$ ne laissant aucun élément invariant. On notera $D_n$ le nombre de dérangements de $E$, avec la convention $D_0=1$.

Si $E$ comporte un seul élément, y-a-t-il des dérangements de $E$? En déduire $D_1$.
Si $E$ comporte deux éléments, combien y-a-t-il de dérangements de $E$? En déduire $D_2$.
On suppose $n$ quelconque, et on écrit $E=\{a_1,\dots,a_n\}$. Soit $f$ une permutation de $E$. On suppose qu'elle laisse $k$ éléments invariants. Combien y-a-t-il de telles permutations? En déduire la formule suivante : $$n!=\sum_{k=0}^n \binom{n}{k} D_k.$$
En déduire $D_3,\ D_4$, $D_5$.
Cinq couples de danseurs se rendent à un bal masqué. A l'arrivée, on sépare les hommes et les femmes , on numérote les femmes de 1 à 5 , et les hommes de 1 à 5. On les fait ensuite s'élancer sur une piste , chaque homme choississant au hasard une femme pour partenaire.
1. A chaque numéro de femme, on associe le numéro de l'homme avec lequel elle danse. Combien y-a-t-il d'associations possibles?
2. Donner la probabilité pour qu'aucun couple légitime ne soit reconstitué.
3. Déterminer la probabilité pour qu'un seul couple légitime soit reconstitué.
4. Déterminer la probabilité pour qu'il y ait plus de couples illégitimes sur la piste de danse que de couples légitimes.

Il n'y a qu'une seule permutation de $E$ qui est l'identité. Ce n'est pas un dérangement, $D_1=0$.
Des deux permutations de $E$, seule celle qui inverse les deux éléments est un dérangement : $D_2=1$.
Il y a $\binom nk$ choix de $k$ éléments invariants parmi $n$. Une fois ces choix fixés, la permutation est un dérangement sur les ${n-k}$ autres éléments. Il y a donc $\binom{n}k D_{n-k}$ telles permutations. La convention $D_0=1$ fait que cette formule reste vraie si $k=n$. On sépare ensuite les permutations de $E$ en fonction de leur nombre de points invariants. Comme les ensembles que l'on obtient sont disjoints, et qu'il y a en tout $n!$ permutations de $E$, on obtient : $$n!=\sum_{k=0}^{n} \binom nk D_{n-k}.$$ Pour obtenir la formule demandée, il faut ensuite faire le changement d'indices $l=n-k$, et utiliser la propriété des coefficients binômiaux : $\binom nk=\binom n{n-k}$.
On applique la relation pour $n=3$. On obtient : $$3!=D_0+3D_1+3D_2+D_3\implies D_3=2.$$ De même, en appliquant la relation pour $n=4$, on trouve $D_4=9$, et pour $n=5$, $D_5=44$.
1. Une telle association correspond à une permutation de $\{1,\dots,5\}$. Il y a $5!=120$ telles permutations.
2. Si aucun couple légitime n'est reconstitué, c'est que la permutation précédente est un dérangement. Il y a $D_5=44$ telles associations, et la probabilité recherchée est $44/120=11/30$.
3. Si un seul couple légitime est reconstitué, il y a 5 choix pour le couple. Pour le reste, il faut un dérangement : il y a donc $5\times D_4=45$ telles possibilités. La probabilité recherchée est $45/120=3/8$.
4. On compte aussi le cas où deux couples légitimes sont reconstitués : il y a $\binom 52=10$ choix de 2 couples parmi 5. Pour les autres, il faut une association qui soit un dérangement : $10\times D_3=20$. Le nombre d'associations où il y a plus de couples illégitimes que de couples légitimes est donc : $20+45+44=109$, ce qui donne une probabilité de 109/120>1/2. Le bal masqué favorise les rencontres!

Exercice 15

- Nombre de surjections [Signaler une erreur] [Ajouter à ma feuille d'exos]

On se propose de calculer le nombre $S(n,p)$ de surjections de $\{1,\dots,n\}$ sur $\{1,\dots,p\}$, où $(n,p)\in(\mathbb N^*)^2$.

Des cas particuliers :
1. Calculer $S(n,p)$ pour $p>n$.
2. Calculer $S(n,n)$.
3. Calculer $S(n,1)$.
4. Calculer $S(n,2)$.
Calculer $S(n+1,n)$.
Démontrer que, pour tout $n>1$ et tout $p>1$, on a la relation $$S(n,p)=p\big(S(n-1,p)+S(n-1,p-1)\big).$$
En déduire un algorithme pour calculer $S(n,p)$.
Démontrer que $S(n,p)=\sum_{k=0}^p (-1)^{p-k}\binom pk k^n.$

1. Si $p>n$, il n'y a pas de surjection de $\{1,\dots,n\}$ sur $\{1,\dots,p\}$. On a donc $S(n,p)=0$.
2. Lorsque $p=n$, les surjections de $\{1,\dots,n\}$ sur $\{1,\dots,n\}$ sont les bijections de $\{1,\dots,n\}$ sur lui-même. Il y en a donc $n!=S(n,n)$.
3. Lorsque $p=1$, toute application de $\{1,\dots,n\}$ dans $\{1\}$ est une surjection. Mais il y a une seule application de $\{1,\dots,n\}$ dans $\{1\}$. On a donc $S(n,1)=1$.
4. Lorsque $p=2$, il y a deux applications qui ne sont pas surjectives : celle qui envoie tous les éléments sur $1$ et celle qui envoie tous les éléments sur 2. De plus, il y a $2^n$ applications de $\{1,\dots,n\}$ dans $\{1,2\}$. On en déduit que $S(n,2)=2^n-2$.
Lorsque l'on étudie les surjections de $\{1,\dots,n+1\}$ dans $\{1,\dots,n\}$, un unique élément de l'ensemble d'arrivée a deux antécédents, et tous les autres en ont un seul. On peut donc caractériser une surjection par le choix de cet élément et de ses deux antécédents, puis par une bijection entre les $n-1$ autres éléments. On a donc $$S(n+1,n)=n\times\binom{n+1}2\times (n-1)!=\frac{n(n+1)!}2.$$
Soit $s$ une surjection de $\{1,\dots,n\}$ sur $\{1,\dots,p\}$. Il y a $p$ façons de choisir la valeur de $s(n)$. Une fois cette valeur choisie, notons $s'$ la restriction de $s$ à $\{1,\dots,n-1\}$. Remarquons que tous les éléments de $\{1,\dots,p\}\backslash\{i\}$ sont atteints par $s'$. On distingue alors deux cas :
- Soit $i$ est atteint par $s'$, et alors $s'$ est une surjection de $\{1,\dots,n-1\}$ sur $\{1,\dots,p\}$. Il y a $S(n-1,p)$ possibilités;
- Soit $i$ n'est pas atteint par $s'$, et $s'$ est une surjection de $\{1,\dots,n-1\}$ sur $\{1,\dots,p\}\backslash\{i\}$. Il y a $S(n-1,p-1)$ possibilités.
Finalement, on obtient que $$S(n,p)=p\big(S(n-1,p)+S(n-1,p-1)\big).$$
On programme la fonction suivante S, d'arguments n et p deux entiers naturels non nuls.
Fonction S(n,p)
Si p>n, retourner 0.
Si p=1, retourner 1.
Sinon, retourner p(S(n-1,p-1)+S(n-1,p))

Seriez-vous capables de prouver que cet algorithme se termine quelles que soient les entrées $n$ et $p$?
On va prouver ce résultat par récurrence sur $n$. Si $n=1$, le résultat est clair si $p=1$; si $p>1$, alors $S(1,p)=0$ qui est bien égal à $$\sum_{k=0}^p (-1)^{p-k}\binom pk k=\sum_{k=1}^{p}(-1)^{p-k}\binom pk k=\sum_{k=1}^p (-1)^{p-k}p\binom{p-1}{k-1}=-p(1-1)^{p-1}=0$$ où on a utilisé $$p\binom {p-1}{k-1}=k\binom pk.$$ Supposons le résultat prouvé au rang $n-1$, et prouvons-le au rang $n$. Si $p=1$, à nouveau l'égalité est évidente. On peut donc supposer $p>1$ et on écrit \begin{eqnarray*} S(n,p)&=&p\big(S(n-1,p)+S(n-1,p-1)\big)\\ &=&p\left(\sum_{k=0}^{p-1}(-1)^{p-1-k}\binom{p-1}kk^{n-1}+\sum_{k=0}^{p}(-1)^{p-k}\binom pk k^{n-1}\right)\\ &=&p\left(\sum_{k=0}^{p-1}(-1)^{p-k}k^{n-1}\left(\binom pk-\binom{p-1}{k}\right)+k^{n-1}\right)\\ \end{eqnarray*} On utilise maintenant la formule du triangle de Pascal et il vient : \begin{eqnarray*} S(n,p)&=&p\left(\sum_{k=0}^{p-1}(-1)^{p-k}k^{n-1}\binom {p-1}{k-1}+k^{n-1}\right) &=&\sum_{k=0}^{p}(-1)^{p-k}p\binom {p-1}{k-1}k^{n-1}. \end{eqnarray*} On obtient le résultat voulu en remarquant à nouveau que $$p\binom {p-1}{k-1}=k\binom pk.$$

Exercice 16

- Permutations alternantes montantes [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $n$ un entier supérieur ou égal à $2$, et $A$ un ensemble de $n$ entiers naturels. On dit qu'une liste $(x_1,\dots,x_n)$ des $n$ éléments de $A$ (ces éléments doivent donc être distincts), est une permutation alternante montante si, pour tout $i=2,\dots,n$, $(-1)^i(x_i-x_{i-1})>0$. On dit que c'est une permutation alternante descendante si, pour tout $i=2,\dots,n$, $(-1)^i (x_i-x_{i-1})<0$. Autrement dit, la liste $(x_1,\dots,x_n)$ est alternante montante si elle vérifie les inégalités $x_1<x_2>x_3<x_4>\cdots$, et elle est alternante descendante si elle vérifie les inégalités inverses.

Déterminer les permutations alternantes montantes de $\{1,\dots,n\}$ pour $n=2$, $n=3$, $n=4$.
Démontrer que le nombre de permutations alternantes montantes de $\{1,\dots,n\}$ est le même que le nombre de permutations alternantes descendantes de $\{1,\dots,n\}$. Pour $n\geq 2$, on note $\beta_n$ le nombre de permutations alternantes montantes de $\{1,\dots,n\}$ et on convient que $\beta_0=\beta_1=1$.
Soit $A$ un ensemble à $n$ éléments. Démontrer que le nombre de permutations alternantes montantes de $A$ est égal au nombre de permutations alternantes montantes de $\{1,\dots,n\}$.
Démontrer que, pour tout $n\geq 1$, $2\beta_{n+1}=\sum_{k=0}^n \binom nk \beta_k\beta_{n-k}$.