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
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.
-
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.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 804 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres