Une question de dénombrement
Bonjour
J'ai un ensemble fini $E$ à $n$ éléments et $k$ un entier quelconque. Je cherche à dénombrer le nombre $L_{n,k}$ de listes de $k$ éléments de $E$ où je m'autorise les répétitions mais où l'ordre ne compte pas c'est-à-dire :
- la liste $(a,a,b,b,c)$ est dans $L_{n,5}$
- les listes $(a,a,b,b,c)$ et $(b,a,a,c,b)$ comptent pour un seul et même élément de $L_{n,5}$.
Après recherche, j'ai vu dans un livre que le résultat serait $\frac{(n+k-1)!}{(n-1)!k!}$ mais je ne vois pas du tout comment prouver ce résultat.
Quelqu'un pourrait m'aider ?
D'avance merci.
J'ai un ensemble fini $E$ à $n$ éléments et $k$ un entier quelconque. Je cherche à dénombrer le nombre $L_{n,k}$ de listes de $k$ éléments de $E$ où je m'autorise les répétitions mais où l'ordre ne compte pas c'est-à-dire :
- la liste $(a,a,b,b,c)$ est dans $L_{n,5}$
- les listes $(a,a,b,b,c)$ et $(b,a,a,c,b)$ comptent pour un seul et même élément de $L_{n,5}$.
Après recherche, j'ai vu dans un livre que le résultat serait $\frac{(n+k-1)!}{(n-1)!k!}$ mais je ne vois pas du tout comment prouver ce résultat.
Quelqu'un pourrait m'aider ?
D'avance merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Tu cherches à dénombrer les fonctions croissantes de \( \{1,\ldots,n\}\) vers \( \{1,\ldots,k\}\), n'est-ce pas ?
Amicalement,
e.v.
Bonne après-midi.
Fr. Ch.
En effet Chaurien, cela correspond aux fonctions croissantes de $\{1,\dots, k\}$ dans $\{1, \dots, n\}$.
Et effectivement, de là, on peut se ramener à un dénombrement de fonctions strictement croissantes et le tour est joué.
J'imagine que cette manière d'aborder le problème est classique, mais je ne crois pas l'avoir déjà vue.
Merci à vous, Chaurien et ev, ainsi qu'à la personne qui m'a répondu en MP. J'aurais probablement séché longtemps avant de penser à envisager le problème sous cet angle !
Ainsi, notre nombre $L_{n,k}$ apparaît comme le nombre de suites $(m_1,m_2,...,m_k,m_{k+1})$ d'entiers naturels de somme $n-1$.
$\bullet$ Pour calculer $L_{n,k}$ ainsi défini, on peut appliquer la méthode des séries génératrices.
Soit $\displaystyle (\underset{m=0}{\overset{+\infty }{\sum }}X^{m})^{k+1}=(\underset{m_{1}=0}{%
\overset{+\infty }{\sum }}X^{m_{1}})(\underset{m_{2}=0}{\overset{+\infty }{%
\sum }}X^{m_{2}})...(\underset{m_{k}=0}{\overset{+\infty }{\sum }}X^{m_{k}})(%
\underset{m_{k+1}=0}{\overset{+\infty }{\sum }}X^{m_{k+1}})=\underset{n=0}{%
\overset{+\infty }{\sum }}a_{k,n}X^{n}$.
D'après le produit des séries entières, $a_{k,n}$ est le nombre de suites $(m_1,m_2,...,m_k,m_{k+1})$ d'entiers naturels de somme $n$, d'où $L_{n,k}=a_{k,n-1}$.
Pour calculer $a_{k,n}$, on écrit : $\displaystyle (\underset{m=0}{\overset{+\infty }{\sum }}X^{m})^{k+1}=(\frac{1}{1-X}%
)^{k+1}=(1-X)^{-k-1}=\underset{n=0}{\overset{+\infty }{\sum }}\binom{-k-1}{n}%
(-X)^{n}=\underset{n=0}{\overset{+\infty }{\sum }}\binom{k+n}{n}X^{n}$.
D'où : $L_{n,k}=a_{k,n-1}=\binom{k+n-1}{n-1}=\frac{(n+k-1)!}{k!(n-1)!}$.Bon, c'est un peu compliqué, mais ça permet de se roder pour cette méthode, qui est utile dans d'autres circonstances.
Bonne soirée.
Fr. Ch.
10/09/2021
[small]Adieu Bébel[/small] :-(
Dans les questions suivantes, ils demandent le nombre de fonctions non monotones, d'un ensemble E à p éléments dans un ensemble F à n éléments.
Pour cela on a besoin du nombres de fonctions constantes de E dans F.
J'aurais dit qu'il y en avait n (ça me semble évident) mais dans leur corrigé il est écrit "à l'évidence [le nombre de fonction constante de E dans F] est p"
C'est bien une erreur de leur part ou je suis complètement a côté de la plaque ?
Ex si E={1,2} et F={1,2,3}
il y a 3 applications celle qui à n associe 1 puis celle qui à n associe 2 et enfin celle qui à n associe 3.