Dénombrement des termes d'une somme

Deura

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 ;-)

Math Coss

Tu peux calculer quelques termes de plus pour aller chercher ici : http://oeis.org/search?q=3,10,35,126,462,1716.

Deura

Oh merci beaucoup. Je ne connaissais pas ce site et il me parait des plus pratiques !
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

jandri

C'est un résultat bien connu : le nombre de solutions dans $\N$ de l'équation $x_1+\dots+x_n=k$ est égal à $\displaystyle {n+k-1\choose k}$.

Il existe une démonstration très courte sans calculs.

noix de totos

On peut même généraliser le résultat de Jandri en donnant des contraintes aux $x_i$ de la forme $x_i > c_i$, par exemple.

PetitLutinMalicieux

Bonjour

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)!}$