Partitions d’un ensemble fini

Soit {E} un ensemble fini non vide.

Pour tout entier {k}, on dit que {\{A_1,\ldots,A_k\}} est une partition de {E} en {k} classes si : {\forall\,i,\,A_i\neq\emptyset,\quad\bigcup_{i=1}^kA_i=E,\quad\forall i\ne j,\,A_i\cap A_j=\emptyset}

{\fbox{Partie I}}

Dans cette partie, on suppose {\text{Card}(E)=n}.

On note {r(n)} le nombre de partitions de {E}.
On note {r(0)=1}.

Pour tout {k\geq 1}, on note {r(n,k)} le nombre de partitions de {E} en {k} classes.

Question I.1
Montrer que : {\forall\;k,n\in \mathbb{N}^*}, {k>n\Rightarrow r(n,k)=0}.
Cliquer ici pour voir (ou cacher) la réponse
Supposons qu’il existe une partition en {k} classes {\{A_1,\ldots,A_k\}}, donc {r(n,k)>0}.

Pour tout {j}, on a : {\text{Card}(A_j)\ge1}).
Alors {n=\text{Card}(E)=\displaystyle\sum_{j=1}^k\text{Card}(A_j)\ge k}

Par conséquent, si {n\lt k}, on a {r(n,k)=0}.

Question I.2
Montrer que : {\forall\;n\in \mathbb{N}^*}, {r(n)=\displaystyle\sum_{k=1}^{n}r(n,k)}.
Cliquer ici pour voir (ou cacher) la réponse
Les partitions de {E} se groupent en :

  • Celle qui n’a qu’une classe (nécessairement {E}).
    Il y en a {r(n,1)=1}.
  • {\cdots}
  • Celles comportent {k} classes : il y en a {r(n,k)}.
  • {\cdots}
  • Celle qui en a {n} (nécessairement les singletons).
    Il y en a {r(n,n)=1}.

On en déduit l’égalité : {r(n)=\displaystyle\sum_{k=1}^nr(n,k)}.

Question I.3
Montrer que : {\forall\;n\in\mathbb{N}, r(n+1)=\displaystyle\sum_{k=0}^n\dbinom{n}{k}r(k)}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question I.4
Calculer {r(n)} pour {n\in\{1,2,3,4,5,6\}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question I.5
Montrer que : {\forall\;n\geq 5,\;r(n)\geq 2^n}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question I.6
Montrer que : {\forall \;n\in\mathbb{N}^*,\;r(n)\leq n^n}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question I.7
On note {S_n^k} le nombre de surjections d’un ensemble à {n} éléments sur un ensemble à {k} éléments.
Montrer que : {\forall \;k,n\in \mathbb{N}^*}, {S_n^k=k!\,r(n,k)}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).

{\fbox{Partie II}}

On suppose que {\text{Card}(E)=2m}, avec {m\geq1}.

On note {a_m} le nombre de partitions de {E} en {m} classes qui sont des paires.

Question II.1
Donner {a_1,a_2,a_3}. Par convention, {a_0=1}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question II.2
Montrer que : {\forall \;m\in \mathbb{N}^*}, {a_m=(2m-1)a_{m-1}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question II.(3)
En déduire {a_{m}=\dfrac{(2m)!}{2^{m}m!}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).

{\fbox{Partie III}}

On suppose que {\text{Card}(E)=n}, avec {n\geq1}.

On note {b_n} le nombre de partitions de {E} en classes qui sont des paires ou des singletons.

Question III.1
Déterminer {b_1,b_2,b_3,b_4}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question III.2
On suppose que {n=2m} ({m\geq 1}).
Montrer que : {b_{2m}=\displaystyle\sum_{k=0}^m\dbinom{2m}{2k}\,a_{m-k}}.
Indication : classer les partitions suivant le nombre de singletons qu’elles contiennent.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question III.3
Montrer que : {\forall \;n\geq 3}, {b_n=b_{n-1}+(n-1)b_{n-2}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question III.4
Calculer {b_n}, pour {1\leq n\leq10}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question III.5
Calculer le nombre d’applications involutives dans un ensemble à 10 éléments.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).