Solutions entières de $x_1+x_2+\cdots+x_p=n$
Bonjour,
j'ai consulté cette vidéo du site @netprof concernant le dénombrement des solutions entières de la somme $x_1+x_2+x_3+\cdots+x_p=n$
https://www.youtube.com/watch?v=r8Rl7GPQoBk&list=PLGYKyocXgHJJyduCc-cbEPIwiyda4sGIK&index=91
La personne réalisant la correction de cet exercice affirme qu'il existe une bijection entre les p-uplets de solutions et leur écriture à l'aide des symboles "+" et "1".
Par exemple, si on cherche le nombre de triplets de solutions de l'équation $x_1+x_2+x_3=10$, il donne l'exemple suivant : il décompose et donne cette somme sous la forme 1+11+1111111 (il doit y avoir 10 fois le chiffre 1 dans cette écriture et le signe "+" y apparaît deux fois).
Il s'intéresse donc aux mots de 12 lettres que l'on peut former à l'aide de l'alphabet {+ , 1}. Et il les dénombre.
Le mieux est de visionner la vidéo, elle est courte.
Cependant, cette correspondance n'est pas bijective il me semble.
Car par exemple, le mot +111+11111111 n'a pas de sens en termes de somme de nombres entiers. Les mots ne peuvent ni commencer ni terminer par un "+".
Et les mots qui contiennent deux symboles "+" consécutifs ne conviennent pas non plus.
Sa méthode fonctionne si l'on cherchait tous les mots de 12 lettres que l'on puisse former dans cet alphabet. Or certains n'ont aucun sens.
Quelle est donc la bonne façon ou méthode pour dénombrer tous les cas possibles ?
Merci.
j'ai consulté cette vidéo du site @netprof concernant le dénombrement des solutions entières de la somme $x_1+x_2+x_3+\cdots+x_p=n$
https://www.youtube.com/watch?v=r8Rl7GPQoBk&list=PLGYKyocXgHJJyduCc-cbEPIwiyda4sGIK&index=91
La personne réalisant la correction de cet exercice affirme qu'il existe une bijection entre les p-uplets de solutions et leur écriture à l'aide des symboles "+" et "1".
Par exemple, si on cherche le nombre de triplets de solutions de l'équation $x_1+x_2+x_3=10$, il donne l'exemple suivant : il décompose et donne cette somme sous la forme 1+11+1111111 (il doit y avoir 10 fois le chiffre 1 dans cette écriture et le signe "+" y apparaît deux fois).
Il s'intéresse donc aux mots de 12 lettres que l'on peut former à l'aide de l'alphabet {+ , 1}. Et il les dénombre.
Le mieux est de visionner la vidéo, elle est courte.
Cependant, cette correspondance n'est pas bijective il me semble.
Car par exemple, le mot +111+11111111 n'a pas de sens en termes de somme de nombres entiers. Les mots ne peuvent ni commencer ni terminer par un "+".
Et les mots qui contiennent deux symboles "+" consécutifs ne conviennent pas non plus.
Sa méthode fonctionne si l'on cherchait tous les mots de 12 lettres que l'on puisse former dans cet alphabet. Or certains n'ont aucun sens.
Quelle est donc la bonne façon ou méthode pour dénombrer tous les cas possibles ?
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
L’écriture commençant par un $+$ est une solution qui commence par $0+...$.
De même, le $0$ peut intervenir entre deux $+$ ou à la fin, derrière un $+$ qui termine le mot.
Enfin, il faut que le nombre de $1$ soit égal à dix.
De manière savante ça revient à écrire les termes en base « un », sauf les zéros qui sont, comme décrit plus haut, représentés par l’absence de symbole.
J’espère n’avoir rien oublié.
A moins que je n'aie pas compris l'énoncé. Je suis parti du fait qu'il fallait trouver toutes les combinaisons non triviales permettant d'obtenir la somme n.
Dans ce cas en effet il faut « cadrer » les sommes et les obliger de commencer et finir par $1$.
Interdire aussi les $++$.
Edit, je n'ai pas vu les autres posts.
Je n'arrive pas à faire le lien avec le problème proposé.
Et s’interdire les mots commençant par $0$, finissant par $0$, contenant $00$ et enfin n’autoriser que les mots qui contiennent deux $0$ (et dix $1$, bien entendu).
On peut alors simplifier : puisque l’on a un $1$ en début et en fin, on les « oublie » et on cherche des mots contenant huit $1$ et deux $0$ non consécutifs.
a) dénombrement des applications strictement croissantes de [1, p] dans [1, n] :
ces applications sont en correspondance bijective avec leur image. Il y en a donc autant que de parties de [1, n] à p éléments, soit
Cnp = n!/(p!(n-p)!)
b) dénombrement des applications croissantes de [1, p] dans [1, n] :
une telle application f est en correspondance bijective avec l'application strictement croissante g de [1, p] dans [1, n+p-1] définie par g(i) = f(i)+i-1.
Il y en a donc Cpn+p-1
c) dénombrement des combinaisons sans répétition de n objets pris p à p :
ce sont les suites de p termes distincts d'éléments de [1, n] sans tenir compte de l'ordre, autrement dit les classes d'équivalence de A / ~, où A est l'ensemble des injections de [1, p] dans [1, n] et f ~ g la relation d'équivalence sur A définie par im f = im g. Ces classes s'identifient aux parties à p éléments de [1, n] et sont donc au nombre de
Cnp.
d) dénombrement des combinaisons avec répétition de n objets pris p à p :
ce sont les suites de p termes d'éléments de [1, n] sans tenir compte de l'ordre, autrement dit les classes d'équivalence de F / ~, où F est l'ensemble des applications de [1, p] dans [1, n] et f ~ g la relation d'équivalence sur F définie par $\varphi$(f) = $\varphi$(g), avec $\varphi$(f) = ( card f -1(i) ) i pour i de 1 à n.
On voit donc que ces classes s'identifient aux n-uples (x1, x2, .. xn) solutions en entiers naturels de l'équation x1+ .. +xn = p.
On remarque aussi que chaque classe contient une unique application de F qui soit croissante, que l'on peut donc prendre comme représentant de la classe. Ainsi, il y a autant de combinaisons avec répétition de n objets pris p à p (et de solutions de l'équation précédente) que d'applications croissantes de [1, p] dans [1,n], soit
Knp = Cpn+p-1
Par exemple, la solution
2 + 0 + 2 + 2 +1 = 7 (x1 à x5)
correspond à la combinaison avec répétition des chiffres 1 à 5 :
1133445
Concernant l'équation, on peut aussi définir y1 = x1+1, y2 = x1 + x2+1, ... yn = p+1.
Les x1, x2, .. xn sont en correspondance bijective avec les y1, y2, ... yn-1 croissants dans [1, p+1], et les solutions sont au nombre de
Kp+1n-1
et l'on retrouve bien le même nombre puisque
Kp+1n-1 = Cn-1n+p-1 = Knp
Finalement, on peut aussi choisir n-1 séparateurs parmi p+n-1 cases, et prendre comme valeurs des xi le nombre de cases entre deux séparateurs contigus et l'on obtient directement Cn-1p+n-1
\sum_{a \in A} x^a \times \sum_{b \in B} x^b = \sum_{k=0}^{+\infty} c_kx^k.
$$ Alors, on a : $$
f(x) := \sum_{n = 0}^{+\infty} N(p,n) x^n = \left( \sum_{k=0}^{+\infty} x^k \right)^p = \frac{1}{(1-x)^p}
$$ et un calcul facile permet alors de déterminer $\frac{f^{(n)}(0)}{n!}$, ce qui donne le résultat.