Combinaison avec répétitions

jeffreyzi · October 2020

Bonsoir à tous,
Je m'interroge sur le nombre de $k$-combinaisons avec répétitions d'un ensemble à $n$ éléments. Il me semblait logique, jusqu'ici, qu'il y en ait $\frac{n^k}{k!}$. En effet, on dénombre d'abord le nombre de $k$-listes d'un tel ensemble (il y en a $n^k$). En regroupant ces $k$-listes par parquets de listes égales à l'ordre prêt, il me semble que l'on devrait obtenir $\frac{n^k}{k!}$ paquets de $k!$ listes égales à permutation prêt. Ce nombre de paquets me semblait donner le nombre de $k$-combinaisons avec répétitions.

En me documentant, je trouve un résultat bien différent de cela : $\binom{n+k-1}{k}$.

Il me semble pourtant que c'est le principe que j'explique ci-dessus qui permet de déduire du nombre de $k$-arrangements le nombre de $k$-combinaisons (sans répétitions) (on divise le nombre d'arrangements par $k!$ pour ne plus tenir compte de l'ordre...).

Force est de constater que mon raisonnement est faux mais je ne vois pas en quoi. Si quelqu'un à la gentillesse de m'aider à voir mon erreur, j'en serai très heureux.

Merci d'avance

gerard0 · October 2020

Bonjour.

C'est un peu embêtant, pour n=10 et k=3, $\frac{n^k}{k!} =\frac{500}3$ !!

Tu es sûr que tous les arrangements avec répétition de 3 chiffres donnent par permutation 3!=6 suites différentes ?

Cordialement.

gai requin · October 2020

Le raisonnement qui permet de passer du nombre d'arrangements au nombre de combinaisons ne s'applique pas ici.
Par exemple, il n'y a qu'une seule (et pas $2!$) $2$-liste contenant les mêmes éléments que $(1,1)$.

Remarque : Ta formule est mise en défaut par de simples considérations arithmétiques.
Soit $p$ un nombre premier ne divisant pas $n$.
Alors $n^p$ n'est pas divisible par $p!$.

PetitLutinMalicieux · October 2020

Bonjour

Pour chaque combinaison de p objets parmi n, on peut fixer un ordre, car on est sûr que chaque objet est unique puisqu'il n'y a pas de répétition. On peut donc passer de la combinaison à l'arrangement ou de l'arrangement à la combinaison en multipliant ou divisant par $p!$.

Quand tu fais de la répétition, ce n'est pas aussi simple. (3,4) et (4,3) sont deux couples avec 2 ordres. (7,7) est un couple qui n'admet qu'un seul ordre. Car même en permutant les éléments du couple, tu auras toujours (7,7).
Donc multiplier ou diviser par une constante, sans savoir ce qui a été répété est faux.