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}.
Montrer que : {\forall\;k,n\in \mathbb{N}^*}, {k>n\Rightarrow r(n,k)=0}.
Question I.2
Montrer que : {\forall\;n\in \mathbb{N}^*}, {r(n)=\displaystyle\sum_{k=1}^{n}r(n,k)}.
Montrer que : {\forall\;n\in \mathbb{N}^*}, {r(n)=\displaystyle\sum_{k=1}^{n}r(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)}.
Montrer que : {\forall\;n\in\mathbb{N}, r(n+1)=\displaystyle\sum_{k=0}^n\dbinom{n}{k}r(k)}.
Question I.4
Calculer {r(n)} pour {n\in\{1,2,3,4,5,6\}}.
Calculer {r(n)} pour {n\in\{1,2,3,4,5,6\}}.
Question I.5
Montrer que : {\forall\;n\geq 5,\;r(n)\geq 2^n}
Montrer que : {\forall\;n\geq 5,\;r(n)\geq 2^n}
Question I.6
Montrer que : {\forall \;n\in\mathbb{N}^*,\;r(n)\leq n^n}.
Montrer que : {\forall \;n\in\mathbb{N}^*,\;r(n)\leq n^n}.
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)}
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)}
{\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}.
Donner {a_1,a_2,a_3}. Par convention, {a_0=1}.
Question II.2
Montrer que : {\forall \;m\in \mathbb{N}^*}, {a_m=(2m-1)a_{m-1}}.
Montrer que : {\forall \;m\in \mathbb{N}^*}, {a_m=(2m-1)a_{m-1}}.
Question II.(3)
En déduire {a_{m}=\dfrac{(2m)!}{2^{m}m!}}.
En déduire {a_{m}=\dfrac{(2m)!}{2^{m}m!}}.
{\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}.
Déterminer {b_1,b_2,b_3,b_4}.
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.
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.
Question III.3
Montrer que : {\forall \;n\geq 3}, {b_n=b_{n-1}+(n-1)b_{n-2}}.
Montrer que : {\forall \;n\geq 3}, {b_n=b_{n-1}+(n-1)b_{n-2}}.
Question III.4
Calculer {b_n}, pour {1\leq n\leq10}.
Calculer {b_n}, pour {1\leq n\leq10}.
Question III.5
Calculer le nombre d’applications involutives dans un ensemble à 10 éléments.
Calculer le nombre d’applications involutives dans un ensemble à 10 éléments.