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