Exercices corrigés : Dénombrement

Voici des énoncés d’exercices sur le dénombrement en mathématiques. Si vous souhaitez voir des énoncés, allez plutôt voir nos exercices de dénombrement.

Ces exercices sont faisables en MPSI. Voici les énoncés :

Exercice 239

Soit σ une permutation de S_n. Soit k un entier de {1, .., n}. Il existe k’ tel que

\sigma (k)=k'

k’ peut prendre n valeur différentes, toutes avec la même probabilité. On a donc pour chaque entier k une probabilité

\frac{1}{n}

que k’ = k. Donc chaque point est un point fixe avec cette probabilité là. On a donc

n \times \frac{1}{n} = 1 

point fixe en moyenne.

Exercice 633

Question 1

Soit B une partie de E. Notons k son cardinal.
Soit A une partie de E vérifiant

A \subset B

A est un donc un sous-ensemble d’un ensemble B de cardinal k. On a donc 2^k sous-ensembles possibles.

Maintenant, on a

\binom{n}{k}

ensembles B de cardinal k.
On va maintenant faire une somme et utiliser le binôme de Newton pour compter le nombre d’ensembles en faisant varier k le cardinal de B :

\begin{array}{ll}
&\displaystyle \sum_{A \subset B}  1\\
=&\displaystyle \sum_{k=0}^n\sum_{A \subset B, |B|=k}  1\\
=&\displaystyle \sum_{k=0}^n 2^k \binom{n}{k}\\
=&\displaystyle \sum_{k=0}^n 2^k 1^{n-k}\binom{n}{k}\\
=&(2+1)^n \\
=&3^n
\end{array}

Question 2

On va appliquer le même principe mais avec une itération supplémentaire :

\begin{array}{ll}
&\displaystyle \sum_{A \subset B \subset C}  1\\
=&\displaystyle \sum_{k=0}^n\sum_{A \subset B \subset C, |C|=k}  1\\

\end{array}

On utilise la question 1) pour dire qu’à cardinal fixé pour C de valeur k, on a 3^k ensembles tels que A inclus dans B. Maintenant, on a

\binom{n}{k}

façons de choisir C. On a donc :

\begin{array}{ll}
&\displaystyle \sum_{k=0}^n\sum_{A \subset B \subset C, |C|=k}  1\\
=& \displaystyle \sum_{k=0}^n 3^k \binom{n}{k} \\
=& \displaystyle \sum_{k=0}^n 3^k 1^{n-k} \binom{n}{k} \\
=& (3+1)^n\\
=&4^n
\end{array}

On a donc 4ⁿ triplets (A,B,C) tels que A inclus dans B lui-même inclus dans C.

Exercice 894

Nous allons démontrer le résultat par récurrence :

n = 2
Prenons une personne. Soit elle connait l’autre et dans ce cas là l’autre la connait aussi. Soit elle ne connait pas l’autre et dans ce cas l’autre ne la connait pas. Dans les deux cas, ces deux personnes conaissent le même nombre de personnes.

Hérédité
Suppsons la propriété vraie à un rang n fixé et montrons qu’elle est vraie au rang n+1.

Soit un groupe de n+1 personnes.

• S’il existe une personne qui ne connait personne d’autre, alors on peut faire comme si cette personne n’était pas dans le groupe et se ramener au cas de n personnes. Dans ce cas, par hypothèse de récurrence, on peut trouver deux personnes qui connaissent le même nombre de personnes
• Dans le cas contraire, chacune des n+1 personnes connait entre 1 et n personnes. On peut donc utiliser le lemme des tiroirs pour en déduire qu’il existe aux moins 2 personnes connaissant le même groupe de personnes.

On a donc démontré le résultat par récurrence, ce qui conclut notre exercice.

Ces exercices vous ont plu ?