Soient $n$ et $k$ des entiers naturels tels que $2\leq k\leq n-1$ .

Soit $E$ un ensemble à $n$ éléments et $a$ un élément fixé de $E$ .

Il y a $P_n^k$ partitions de $E$ en $k$ classes. Parmi ces partitions, il y a celles dans lesquelles $a$ est dans un singleton. Elles s’identifient aux partitions en $k-1$ classes de $E\setminus\{a\}$ et sont au nombre de $P_{n-1}^{k-1}$ . Il y a ensuite les partitions dans lesquelles $a$ est élément d’une partie de cardinal au moins $2$ . Une telle partition est obtenue en partitionnant $E\setminus\{a\}$ en $k$ classes puis en adjoignant à l’une de ces $k$ classes au choix l’élément $a$ . Il y a $kP_{n-1}{k}$ telles partitions. Au total, $P_n^k=P_{n-1}^{k-1}+kP_{n-1}^k$ .

Valeurs de $P_n^k$ pour $1\leq k,n\leq 5$ .

$\begin{array}{|c|c|c|c|c|c|} \hline n\;/\;k&1&2&3&4&5\\ \hline 1&1&0&0&0&0\\ \hline 2&1&1&0&0&0\\ \hline 3&1&3&1&0&0\\ \hline 4&1&7&6&1&0\\ \hline 5&1&15&25&10&1\\ \hline \end{array}$ Exprimons maintenant en fonction des $P_n^k$ , le nombre de surjections d’un ensemble à $n$ éléments dans un ensemble à $p$ éléments.

Si $p>n$ , il n’y a pas de surjections de $E_n$ dans $E_p$ (où $E_n$ et $E_p$ désignent des ensembles à $n$ et $p$ éléments respectivement).

On suppose dorénavant $p\leq n$ . La donnée d’une surjection $f$ de $E_n$ sur $E_p$ équivaut à la donnée d’une partition de l’ensemble $E_n$ en $p$ classes (chaque élément d’une même classe ayant même image par $f$ ) puis d’une bijection de l’ensemble des parties de la partition vers $E_p$ .

Au total, il y a donc $p!P_n^k$ surjections d’un ensemble à $n$ éléments dans un ensemble à $p$ éléments pour $1\leq p\leq n$ .

exo7 5290