Une question de dénombrement — Les-mathematiques.net The most powerful custom community solution in the world

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.

Réponses

  • Bonjour gimax.

    Tu cherches à dénombrer les fonctions croissantes de \( \{1,\ldots,n\}\) vers \( \{1,\ldots,k\}\), n'est-ce pas ?

    Amicalement,

    e.v.
  • Si l'on prend $E=\{1,2,...,n\}$ alors $L_{n,k}$ est le nombre de $k$-listes de $E$ croissantes au sens large, autrement dit (si l'on veut) le nombre d'applications croissantes au sens large de $\{1,2,...,k\}$ dans $E=\{1,2,...,n\}$. On peut les « étirer » en croissantes au sens strict. Pour ce faire, à chaque suite $(x_1,x_2,...,x_k)$ élément de $L_{n,k}$, on associe $(y_1,y_2,...,y_k)$ avec $y_i=x_i+i-1$. C'est une des manières de faire, mais il y en a d'autres.
    Bonne après-midi.
    Fr. Ch.
  • Ci-joint deux pages sur le sujet
  • Merci à vous.

    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 !
  • Merci Médiat ! Désolé, je n'ai vu ton message qu'après avoir posté mon message précédent.
  • Il y a une autre interprétation pour les combinaisons avec répétitions, comme le dit le document de Médiat. En voici une autre preuve.$\bullet$ À chaque suite $(x_1,x_2,...,x_k)$ d’éléments de $E=\{1,2,...,n\}$, croissante au sens large, on peut associer la suite $(m_1,m_2,...,m_k,m_{k+1})$ définie par $m_1=x_1-1$, et $m_i=x_i-x_{i-1}$ pour $i \in \{2,3,...,k\}$, et $m_{k+1}=n-x_k$.
    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] :-(
  • Bonjour, je fais le même exercice avec la solution sous les yeux dans un Monier Haberer de MPSI. (25.10 p401)

    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.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!