Dénombrement d'ensemble
Bonsoir !!
J'ai un exercice sur le dénombrement où je n'ai pas d'idée. L'exercice est le suivant :
Quel est le nombre de suites à $n$ éléments de |N dont la somme est inférieure ou égale à $p$? Où n et p sont des entiers naturels non nuls.
Besoin d'aide svp.
J'ai un exercice sur le dénombrement où je n'ai pas d'idée. L'exercice est le suivant :
Quel est le nombre de suites à $n$ éléments de |N dont la somme est inférieure ou égale à $p$? Où n et p sont des entiers naturels non nuls.
Besoin d'aide svp.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ensuite, une idée, entre autres : tu peux dénommer par exemple $X(n,p)$ le nombre cherché, tu regardes les résultats pour les premières valeurs de $n$ et $p$, que tu consignes sur un tableau, tu fais une conjecture, et tu la démontres, par récurrence ou autrement.
Bon courage.
Fr. Ch.
L'ensemble des suites à $n$ éléments de $\N$ dont la somme est inférieure ou égale à $p$.
L'ensemble des suites à $n\color{blue}{+1}$ éléments de $\N$ dont la somme est égale à $p$.
Ensuite la réponse est donnée par l'argument des "stars and bars". https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two
On vérifie qu'on a construit une bijection de l'ensemple des suites $(x_1,...,x_n)$ d'entiers naturels de somme inférieure ou égale à $p$ sur l'ensemble des suites formée de $n$ fois $0$ et de $p$ fois $1$.
Le nombre de ces suites est facile à calculer.