Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
244 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Combinaison avec répétitions

Envoyé par jeffreyzi 
Combinaison avec répétitions
il y a cinq mois
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
Re: Combinaison avec répétitions
il y a cinq mois
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.
Re: Combinaison avec répétitions
il y a cinq mois
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!$.
Re: Combinaison avec répétitions
il y a cinq mois
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.



Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par PetitLutinMalicieux.
Re: Combinaison avec répétitions
il y a cinq mois
Je vous remercie tous les trois. Je savais que c'était faux mais je ne voyais pas pourquoi. Maintenant je pense avoir compris !
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 605, Messages: 1 497 701, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page