Exercices corrigés : Dénombrement

Voici des exercices corrigés détaillés sur le dénombrement.
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

Nombre de points fixes de permutation

Soit σ une permutation de Sn. 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

Dénombrement de parties

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 2k 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 3k 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 4n triplets (A,B,C) tels que A inclus dans B lui-même inclus dans C.

Exercice 894

Lemme des tiroirs

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 ?

Total
0
Shares
4 commentaires
  1. Bonjour, merci pour ces exercices très intéressants.
    Un point cependant m’intrigue sur l’exercice 239, j’ai quand même l’impression qu’il n’y a pas indépendance entre les différentes probabilités puisque le fait que l’événement sigma k = k est dépendant de l’événement sigma k’ = k

    1. Bonjour Benjamin,
      Et merci pour le compliment ! Je pense que ce n’est pas grave. Le point important est que si tu prends une permutation au hasard, la probabilité que sigma(k) = k est de 1/n. Et du coup, en moyenne, tu as sigma(k) = k est un point fixe une fois sur n. Ensuite, on peut sommer (ça se comporte comme une espérance donc pas d’hypothèse d’indépendance)

      1. Bonjour Valentin,
        Merci pour ta réponse, c’est effectivement très efficace comme approche.
        Je reste un peu frustré de ne pas m’en être sorti directement par dénombrement. Je me retrouve bloqué avec une somme impliquant les dérangements que je j’arrive pas à simplifier

      2. Salut,
        Je ne sais pas trop comment on peut faire avec les dérangements. Des gens quand je l’avais proposé sur Twitter avaient essayé et étaient bloqués. Je peux leur redemander s’ils ont trouvé mais ça n’était pas évident yep

Laisser un commentaire

Articles similaires
Des idées de cadeaux pour Noël ? Vous voulez profiter du Black Friday ? Voici nos propositions de livres et objets mathématiques !
Découvrez nos idées