Combinaisons avec répétitions modifiées
Bonjour
On fixe $n\in \N$ et $p\in \N^*$. On sait que le nombre de solutions de l'équation $$
u_1+u_2+\dots +u_p=n ,
$$ où $(u_1,\, u_2,\,\dots,\, u_p)\in \N^p$ est $\ {n+p-1 \choose p-1}$.
Qu'en-est il si on impose de plus la condition $u_i\leqslant k$ pour tout $i$ lorsque $k$ est un entier fixé ?
Merci d'avance pour vos réponses.
Michal
On fixe $n\in \N$ et $p\in \N^*$. On sait que le nombre de solutions de l'équation $$
u_1+u_2+\dots +u_p=n ,
$$ où $(u_1,\, u_2,\,\dots,\, u_p)\in \N^p$ est $\ {n+p-1 \choose p-1}$.
Qu'en-est il si on impose de plus la condition $u_i\leqslant k$ pour tout $i$ lorsque $k$ est un entier fixé ?
Merci d'avance pour vos réponses.
Michal
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Le nombre de solutions entières de l'équation $x_1 + \dotsb + x_p = n$ telles que $1 \leqslant x_1, \dotsc,x_p \leqslant k$ est
$$\sum_{h=0}^{\left \lfloor (n-p)/k \right \rfloor} (-1)^h {p \choose h} {n - hk - 1 \choose p-1}.$$
Soient $c_1, \dotsc, c_p$ des entiers naturels. Le nombre de solutions entières de l'équation $x_1 + \dotsb + x_p = n$ telles que $x_1 > c_1, \ x_2 > c_2, \dotsc, \ x_p > c_p$ est égal à
$${n - s_p - 1 \choose p-1}$$
où $s_p := c_1 + \dotsb + c_p$.
$$\sum_{i=1}^p (x_i-c_i)=n-\sum_{i=1}^pc_i\;$$
et je ne comprends pas en quoi c'est plus général que le premier résultat que tu as cité.
Pour ceux qui apprécient les excursions dans Z[X], il y a, outre l'itinéraire combinatoire indiqué par GaBuZoMeu, celui-ci, plus algébrique:
$ \:\:\displaystyle a_n : =\text{Card} \{ (x_1,x_2, \dots x_p) \in \![\![1;k]\!] ^p \mid \sum_{i=1} ^p x_i =n \} \: $ est le coefficient de $X^n$ du polynôme $\:\:P(X) = (X+X^2+\dots X^k) ^p .$
$\displaystyle P(X) = X^p(1-X^k)^p (1-X)^{-p}= X^p \sum _{i\geqslant 0} (-1)^{i} \binom pi X^{ki} \sum_{j\geqslant 0}\binom {p+j-1}{p-1} X^j =\sum _{n \geqslant 0}\left (\sum _{0\leqslant i\leqslant (n-p)/k} (-1)^{i} \binom pi \binom {n-ki-1}{p-1}\right) X^n.$
$$ a_n = \sum _{0\leqslant i\leqslant (n-p)/k} (-1)^{i} \binom pi \binom {n-ki-1}{p-1}.$$