Dénombrement
Bonjour
J'ai une liste d'entiers naturels de taille n.
La seule contrainte:
soit m =max(liste)
pour tout i tel que 1 =< i =< m il existe j tel que liste[j]=i.
Combien il y a-t-il de listes possibles ?
Merci d'avance pour votre aide.
J'ai une liste d'entiers naturels de taille n.
La seule contrainte:
soit m =max(liste)
pour tout i tel que 1 =< i =< m il existe j tel que liste[j]=i.
Combien il y a-t-il de listes possibles ?
Merci d'avance pour votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Le nombre $L_{n,m}$ de tes listes, c'est-à-dire de surjections d'un ensemble à $n$ éléments sur un ensemble à $m$ éléments est lié aux nombres de Stirling de deuxième espèce. On a la formule explicite suivante :
\[L_{n,m}=\sum_{j=0}^m(-1)^{m-j}\binom{m}{j}j^n.\]