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 :
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 :
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 :
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 :
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 :
{\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 :
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 :
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 :
{\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 :
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 :
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 :
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 :
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 :