Combinaisons avec répétitions modifiées — Les-mathematiques.net The most powerful custom community solution in the world

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

Réponses

  • J'ai déjà indiqué ce résultat :

    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}.$$
  • Merci ! Ca se montre comment ?
  • C'(est une simple application du principe d'inclusion-exclusion (ou formule du crible de Poincaré) où $A_i$ est l'ensemble des solutions avec $x_i>k$, pour compter le nombre de solutions qui ne sont pas dans $\bigcup_{i=1}^p A_i$.
  • Oui, exact, et plus généralement :

    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$.
  • Bon, ça c'est trivial en réécrivant l'équation sous la forme
    $$\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é.
  • Ce n'est pas à mon premier résultat, mais bien à tes ensembles $A_i$ que je faisais référence.
  • Modifié (13 Feb)
    Bonsoir,
    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}.$$
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!