Dénombrement d'ensemble

Kcg

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.

Chaurien

D'abord tu mets un «s» à « nombre de suites », merci.
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.

Chaurien

Ou bien : évaluer d'abord de même $Y(n,p)$, le nombre de suites à $n$ termes de $\mathbb N$ dont la somme est égale à $p$. En fait il y a plusieurs méthodes.

Kcg

Merci pour ces méthodes, la conjecture marche, et même la deuxième méthode, mais j'aimerais avoir un raisonnement utilisant directement le dénombrement si possible.

Chaurien

Conjecture, pas conjoncture.

Chaurien

Que trouves-tu pour $ X(n,p)$, nombre de suites à $n$ termes de $\mathbb N$ dont la somme est inférieure ou égale à $p$ ?

Kcg

Je trouve $C_{n+p}^p$

marsup

Les deux ensembles suivant ont le même cardinal :
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

jandri

A toute suite $(x_1,...,x_n)$ d'entiers naturels de somme inférieure ou égale à $p$ on peut associer la suite formée de $n$ fois $0$ et de $p$ fois $1$, construite en écrivant $x_1$ fois le $1$, puis un $0$, puis $x_2$ fois le $1$, puis un $0$, ..., puis $x_n$ fois le $1$, puis un $0$, et enfin $p-\sum(x_i)$ fois le $1$.
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.

Kcg

Merci pour ces deux méthodes.