Dénombrement
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
Merci de votre aide
Réponses
-
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}}$. -
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$).
-
Merci pour l'aide !
Toutefois, je ne vois pas comment déterminer que $\mathcal B$ est de cardinal $\binom{n-1}{p-1}$. -
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 ;-)). -
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 !
-
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. -
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.
-
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 ? -
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$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres