Bonjour, je voudrais montrer que le nombre de combinaison avec répétition de k éléments parmi n est égale au nombre de combinaison sans répétition de k éléments parmi n+k-1, mais je n'ai aucune idée par ou commencer. Quelqu'un pourrait-il m'aider svp.
Edit : j'ai dit de la mouise
bonjour
Je connais une démo indirecte, c'est un peu long à expliquer mais je me lance quand même
Combien de solutions l'équation (E) en entiers naturels x1 + x2 + ... + xn = k a t-elle ?
- 1ere méthode:
A une solution de (E) correspond une combinaison à k éléments avec répétition de l'ensemble (x1, x2, ..., xn) et réciproquement.
Par exemple avec (2, 0, 3, 4) solution de x1+x2+x3+x4=9, la combinaison avec répétition est (x1,x1,x3,x3,x3,x4,x4,x4,x4)
le nombre de solution de (E) est donc
- 2 ème méthode
On imagine n+k-1 cases, 9+4-1 = 12 dans l'exemple
on y place n-1 séparateurs "/", 4-1=3 dans l'exemple
-/---/----/-
puis on mets des "1" dans les cases vides
1/111/1111/1
on somme les "1" entre deux séparateurs
1/3/4/1
ce qui nous donne une solution (1, 3, 4, 1) à l'équation x1+x2+x3+x4=9
Il y afaçons de placer les séparateurs
Il y a donc
donc
Dernière modification par joel_5632 ; 16/10/2014 à 18h49.
Merci pour votre réponse, mais je n'arrive pas à bien comprendre ces méthodes, n'y a t-il pas une autre qui soit plus intuitive ???
Bonjour, voici une méthode visuelle.
Je prend une combinaison de 5 éléments avec répétition parmi l'ensemble {1,2,3,...,9}. Par exemple C=[1,1,4,4,8].
Je prend ensuite 9+5-1=13 boules blanches que j'ordonne (il y a une première boule, une deuxième, etc...).
Ensuite je vais peindre certaines de ces boules en noir de la manière suivante:
Le premier terme de C est un 1, donc je laisse la première boule blanche.
Le deuxième terme est encore un 1, donc je laisse la deuxième boule blanche.
Le troisième terme n'est pas un 1, donc je peint la troisième boule en noir.
Je reste alors sur ce troisième terme. Est-se un 2 ? Non, donc je peint la quatrième boule en noir.
Est-se un 3 ? Non, donc je peint la cinquième boule en noir.
Est-se un 4 ? Oui ! donc je laisse la sixième boule en blanc.
Le terme suivant est-il encore un 4 ? Oui. Donc je laisse la septième boule en blanc.
Le terme suivant n'est plus un 4, donc je peint la huitième boule en noir... Et je continue comme ça. A la fin j'aurais un truc du genre
1100011000010
où les "1" représentent les boules blanches, et les 0 les boules noires.
Reste à prouver que cette manoeuvre est bien bijective, mais je te laisse voir !
