Dénombrement

Gauss_wh

Bonsoir, étant donné $(n,p)\in (\mathbb N^{*})^2$, comment peut-on dénombrer les $p$-listes $(k_1,\dots,k_p)$ d'entiers strictement positifs tels que $k_1+\dots +k_p=n$ ?

Merci de votre aide

LOU16

Bonjour,

On peut voir les choses de la manière suivante:
$\mathcal A =\{(k_1,k_2,...k_p) \in (\N^*)^p \mid \displaystyle{\sum_{i=1}^p k_i = n}\}$
$\mathcal B $ désigne l'ensemble des suites à $p-1$ éléments de $ \{1,2,...n-1\}$ , strictement croissantes :
$\mathcal B =\left \{(x_1,x_2,...x_{p-1}) \in \{1,2,...n-1\}^{p-1}\mid \forall i \in \{1,2,,...p-2\}\:\: x_i < x_{i+1}\right\}$
Alors: $(k_1,k_2 ...k_p) \longmapsto (k_1, k_1+k_2,....,k_1+k_2+...+k_{p-1})$ réalise une bijection de $\mathcal A$ sur $\mathcal B$.
Ainsi: $\text{Card } \mathcal A = \text{Card} \mathcal B=\displaystyle{ \binom {n-1}{p-1}}$.

pascalortiz

Quand tu dis comment peut-on dénombrer tu te réfères à un algorithme ? Ce genre de recherche se fait par programmation dynamique ou par backtracking. Sinon, concernant le nombre de $p$-uplets, outre ce qu'a expliqué LOU16, il s'obtient en utilisant des combinaisons avec répétitions (sauf que toi tu souhaites que $x_i>0$).

Gauss_wh

Merci pour l'aide !

Toutefois, je ne vois pas comment déterminer que $\mathcal B$ est de cardinal $\binom{n-1}{p-1}$.

GaBuZoMeu

Ne verrais-tu pas une bijection entre l'ensemble des suites strictement croissantes à $p-1$ termes dans $\{1,\ldots,n-1\}$ et l'ensemble des parties de $\{1,\ldots,n-1\}$ à $p-1$ éléments ?
(Indice : ranger les éléments du sous-ensemble dans l'ordre ;-)).

Gauss_wh

Si, il s'agit de $f:x=(x_1,\dots,x_{p-1})\in\mathcal B\mapsto \{x_1,\ldots,x_{p-1}\}\in\mathcal P_{p-1}(n-1)$ qui est l'ensemble des parties de $\{1,\dots,n-1\}$ à $p-1$ éléments. Merci !

Gauss_wh

Et pour l'ensemble des $p$-listes $(k_1,\dots,k_p)$ d'entiers positifs tels que $k_1+\dots +k_p=n$ ? (rappel : $(n,p)\in (\mathbb N^{*})^2$)

Informellement, j'ai envie de dire que pour $k_1$ on a $n$ choix, mais après pour $k_2$ ça dépend si on a précédemment pris $k_1=n$ ou pas... J'ai du mal avec ce genre de question et je ne vois pas comment adapter avec la même méthode que précédemment.

GaBuZoMeu

Se ramener au problème précédent. Indication : $k$ est un entier positif ou nul si et seulement si $k+1$ est un entier strictement positif.

Gauss_wh

Bien vu !
Du coup, $\mathcal A=\{(k_1,\dots,k_p)\in \mathbb N^p, k_1+\dots k_p=n\}$ est équipotent à $\mathcal B=\{(x_1,\dots,x_p)\in (\mathbb N^{*})^p, x_1+\dots x_p=n-p\}$ qui est donc de cardinal $\binom{n-p-1}{p-1}$ d'après ce qui précède. Correct ?

pascalortiz

Il me semble.

En ce qui me concerne c'est sous cette forme que les combinaisons avec répétitions me sont le plus intuitives : chaque solution de l'équation $x_1+\cdots +x_p=N$ avec les $x_i\in\mathbb N$ se visualise par $N$ bulles séparées par $p-1$ signes $+$ ou encore par $N+p-1$ bulles dont on choisit d'écraser $p-1$ par un séparateur représentant un signe + :

pour $N=6$ et $p=4$.