Dénombrement des termes d'une somme
Bonjour chère communauté !
Allons droit au but, quels sont les vecteurs ayant k composantes entières, dont la somme vaut k ?
J'ai fait mon petit programme et je vous propose ici (pour faire joli) la liste des vecteurs vérifiant cette condition, pour k = 3.
[0, 0, 3] [0, 1, 2] [0, 2, 1] [0, 3, 0] [1, 0, 2] [1, 1, 1] [1, 2, 0] [2, 0, 1] [2, 1, 0] [3, 0, 0]
On remarque qu'il y en a 10.
Ci-joint le nombre de vecteurs trouvés par mon programme selon k :
2 : 3
3 : 10
4 : 35
5 : 126
6 : 462
7 : 1716
Votre mission, si vous l'acceptez, est la suivante : déterminer la formule permettant de trouver le nombre de vecteur vérifiant cette condition pour n'importe quel k ;-)
Je me doute bien qu'il y a une histoire de combinaison. Mais en me penchant sur le problème je n'ai pas trouvé de porte de sortie.
J'espère que vous passerez un bon moment à résoudre cette petite énigme et je vous souhaite une excellente journée ;-)
Allons droit au but, quels sont les vecteurs ayant k composantes entières, dont la somme vaut k ?
J'ai fait mon petit programme et je vous propose ici (pour faire joli) la liste des vecteurs vérifiant cette condition, pour k = 3.
[0, 0, 3] [0, 1, 2] [0, 2, 1] [0, 3, 0] [1, 0, 2] [1, 1, 1] [1, 2, 0] [2, 0, 1] [2, 1, 0] [3, 0, 0]
On remarque qu'il y en a 10.
Ci-joint le nombre de vecteurs trouvés par mon programme selon k :
2 : 3
3 : 10
4 : 35
5 : 126
6 : 462
7 : 1716
Votre mission, si vous l'acceptez, est la suivante : déterminer la formule permettant de trouver le nombre de vecteur vérifiant cette condition pour n'importe quel k ;-)
Je me doute bien qu'il y a une histoire de combinaison. Mais en me penchant sur le problème je n'ai pas trouvé de porte de sortie.
J'espère que vous passerez un bon moment à résoudre cette petite énigme et je vous souhaite une excellente journée ;-)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Cependant, une explication du pourquoi du comment m'intéresse également. Quel est le rapport entre le sujet que j'évoque et la loi binomiale de (2*k+1,k+1) :-S
Il existe une démonstration très courte sans calculs.
Une autre façon de dire ce que tu as déjà :
On cherche à placer des frontières entre les unités qui composeront ton vecteur final. Dans chaque groupe entre 2 frontières, la somme des unités sera la composante de ton vecteur.
Exemples :
O O O
-> | O | O O
-> (0;1;2)
O O O
-> O O || O
-> (2;0;1)
O O O
-> O O O||
-> (3;0;0)
On tire donc k-1 frontières parmi k+1 positions, indépendamment de l'ordre (2 frontières sont échangeables) et avec répétition (deux frontières peuvent choisir la même position). C'est donc une combinaison avec répétition.
$\Gamma^{k-1}_{k+1}=C^{k-1}_{k+1+k-1-1}=C^{k-1}_{2k-1}=\frac{(2k-1)!}{k!(k-1)!}$