Forum de mathématiques - Bibm@th.net

Saitoh

Membre

Inscription : 13-10-2019

Messages : 10

Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

Je bloque sur un dénombrement.

J'aimerais compter le nombre de n-uplets d'entiers naturels (a_1, a_2, a_3, ..., a_n) vérifiant a_1 + a_2 + .... + a_n soit inférieur ou égal à un certain entier d.

Le fait que c'est égal à n parmi n+d est directement admis dans une démonstration.
Je doute donc que ça peut être fait de manière très aisée.
Cependant, je n'arrive pas du tout ni à comprendre intuitivement, ni à démontrer pourquoi ça marche.
Les cas n=1 et n=2 sont faciles à la main, mais ensuite je coince.

Toute aide serait bienvenue,
Cordialement

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

De mémoire ( c'est vieux ) il y a plusieurs moyens à disposition,  si vous avez l'expression pour d-1,  il suffit de rajouter le nombre de ceux exactement de somme d qui se calcule aisément.
Cela se fait bien, en tous cas c'est sans doute une piste qui le prouve en utilisant facilement la relation sommatoire du triangle de Pascal).

A.

Dernière modification par bridgslam (15-03-2022 13:50:35)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Re-bjr,

en détaillant, en appelant $K_d^n$ le nombre de n-uplets d'entiers naturels de somme d, cela donnera d'après votre relation à l'ordre d:

$K_{d+1}^n  = K_d^n + \binom {d+1+n-1}{n-1} = \binom{n+d}{n} +  \binom {d+n}{n-1} $ donne la relation à l'ordre d+1;

Alain

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

Ça revient à compter le nombre de [tex]n+1[/tex]-uplets d'entiers naturels[tex](a_1,\ldots,a_n,a_{n+1})[/tex] tels que [tex]\sum_{i=1}^{n+1} a_i=d[/tex].
Autrement dit, ça revient à compter le nombre de façons qu'on a de ranger [tex]d[/tex] chaussettes indistinguables dans [tex]n+1[/tex] tiroirs.
Un tel rangement peut être symbolisé de la façon suivante. Par exemple, pour 3 chaussettes dans le premier tiroir, 0 dans le deuxième, 1 dans le troisième et 2 dans le quatrième :
x x x | | x | x x
(une croix pour chaque chaussette donc [tex]d[/tex] croix, une barre pour chaque séparation entre tiroirs donc [tex]n[/tex] barres)
On a ainsi décrit une bijection entre l'ensemble des rangements de chaussettes et l'ensemble des suites de [tex]n+d[/tex] symboles dont [tex]n[/tex] sont des barres et [tex]d[/tex] des croix.
Vois-tu maintenant arriver le coefficient binomial ?

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

Sinon un autre moyen, rajouter un n+1 ième élément ficitf au n- uplet ( qui contiendra le déficit entre la somme des n autres et d )

par bijection évidente cela revient donc à dénombre de nombre de tels (n+1)-uplets , cette fois toujours de somme d.

On trouve ainsi directement votre expression ( consistant à placer n séparateurs parmi n + d éléments ).
C'est plus direct encore comme méthode...

Alain

Dernière modification par bridgslam (15-03-2022 15:08:06)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Excuses Michel je l'ai tapé en même temps, c'est bien cela.

A.

Saitoh

Membre

Inscription : 13-10-2019

Messages : 10

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

Ça revient à compter le nombre de [tex]n+1[/tex]-uplets d'entiers naturels[tex](a_1,\ldots,a_n,a_{n+1})[/tex] tels que [tex]\sum_{i=1}^{n+1} a_i=d[/tex].
Autrement dit, ça revient à compter le nombre de façons qu'on a de ranger [tex]d[/tex] chaussettes indistinguables dans [tex]n+1[/tex] tiroirs.
Un tel rangement peut être symbolisé de la façon suivante. Par exemple, pour 3 chaussettes dans le premier tiroir, 0 dans le deuxième, 1 dans le troisième et 2 dans le quatrième :
x x x | | x | x x
(une croix pour chaque chaussette donc [tex]d[/tex] croix, une barre pour chaque séparation entre tiroirs donc [tex]n[/tex] barres)
On a ainsi décrit une bijection entre l'ensemble des rangements de chaussettes et l'ensemble des suites de [tex]n+d[/tex] symboles dont [tex]n[/tex] sont des barres et [tex]d[/tex] des croix.
Vois-tu maintenant arriver le coefficient binomial ?

Bonjour,

Sinon un autre moyen, rajouter un n+1 ième élément ficitf au n- uplet ( qui contiendra le déficit entre la somme des n autres et d )

par bijection évidente cela revient donc à dénombre de nombre de tels (n+1)-uplets , cette fois toujours de somme d.

On trouve ainsi directement votre expression ( consistant à placer n séparateurs parmi n + d éléments ).
C'est plus direct encore comme méthode...

Alain

Un immense merci, c'est très clair!
Le raisonnement des tiroirs et sa représentation m'ont vraiment aidé à comprendre.
Seul un détail me fait douter: si je comprends bien, le n+1ème élément est totalement superflu, dans le sens où sans lui, on a un n-uplet appartenant à l'ensemble cherché ?

Re-bjr,

en détaillant, en appelant $K_d^n$ le nombre de n-uplets d'entiers naturels de somme d, cela donnera d'après votre relation à l'ordre d:

$K_{d+1}^n  = K_d^n + \binom {d+1+n-1}{n-1} = \binom{n+d}{n} +  \binom {d+n}{n-1} $ donne la relation à l'ordre d+1;

Alain

Merci également pour cette méthode.
Malgré tout, j'ai du mal à comprendre comment vous trouvez le nombre de n-uplets de somme exactement d.

Cordialement.

Dernière modification par Saitoh (15-03-2022 18:47:13)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Seul un détail me fait douter: si je comprends bien, le n+1ème élément est totalement superflu, dans le sens où sans lui, on a un n-uplet appartenant à l'ensemble cherché ?

Il est facile de trouver une bijection entre l'ensemble des [tex]n[/tex]-uplets d'entiers naturels de somme [tex]\leq d[/tex] et l'ensemble des [tex]n+1[/tex]-uplets d'entiers naturels de somme égale à [tex]d[/tex]. Je pense que tu en vois bien une.
Et qui dit bijection, dit même nombre d'éléments.

Saitoh

Membre

Inscription : 13-10-2019

Messages : 10

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Seul un détail me fait douter: si je comprends bien, le n+1ème élément est totalement superflu, dans le sens où sans lui, on a un n-uplet appartenant à l'ensemble cherché ?

Il est facile de trouver une bijection entre l'ensemble des [tex]n[/tex]-uplets d'entiers naturels de somme [tex]\leq d[/tex] et l'ensemble des [tex]n+1[/tex]-uplets d'entiers naturels de somme égale à [tex]d[/tex]. Je pense que tu en vois bien une.
Et qui dit bijection, dit même nombre d'éléments.

Bonjour,

Oui, je vois ce que vous voulez dire.
L'élément n+1 sera en quelque sorte le reste non utilisé pour compléter la somme en d.

Un grand merci pour votre réponse!

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

C'est bien cela, ce que j'avais appelé le "déficit" (éventuellement nul) par rapport à d ( "complément" aurait été plus juste)...
On se ramène par bijection à un dénombrement beaucoup plus immédiat à évaluer.

J'avais tapé mon post en même temps que celui de Michel Coste, ça a donc empiété sur ses propres arguments.

Je ne suis pas du tout un professionnel ( contrairement à lui ) et ses termes mathématiques et présentations sont sans doute toujours largement plus à la pointe (extrême) des sujets que moi. Preuve en est aussi à des sujets relatifs à l'algèbre ( corps, corps gauche...).
Vous pouvez donc vous y fier les yeux fermés.
J'avais quand-même eu la bonne intuition pour le coup, pour la preuve directe, la récurrence étant juste une autre façon de procéder, et surtout en général il faut avoir la connaissance du résultat pour l'utiliser.

J' attend avec impatience la suite de l'exo :-).
Ca sera un plaisir de vous aider, vu que l'échange ne s'évanouit pas fantomatiquement dans la nature (comme parfois, pour ne pas dire souvent ) après l'aide apportée, où parfois on prend vraiment sur notre temps ( ne serait-ce que pour mettre de l'ordre et apurer les énoncés, souvent pleins d'erreurs).

Alain

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

Pour vous aider, vous avez aussi un autre fil #ro174... récent auquel j'avais participé, et aussi une autre façon de procéder.

Alain

Saitoh

Membre

Inscription : 13-10-2019

Messages : 10

Re : Dénombrement: Compter les n-uplets vérifiant une condition

Bonjour,

J' attend avec impatience la suite de l'exo :-).
Ca sera un plaisir de vous aider, vu que l'échange ne s'évanouit pas fantomatiquement dans la nature (comme parfois, pour ne pas dire souvent ) après l'aide apportée, où parfois on prend vraiment sur notre temps ( ne serait-ce que pour mettre de l'ordre et apurer les énoncés, souvent pleins d'erreurs).

Alain

Haha, je suis navré mais il n'y a pas de suite à proprement parler.
En fait, il s'agissait d'un lemme utilisé pour une démonstration sur des zéros de polynôme et que j'avais du mal à comprendre.

Je comprends votre ressenti, et je vous remercie d'avoir pris de votre temps pour m'aider.

Pour vous aider, vous avez aussi un autre fil #ro174... récent auquel j'avais participé, et aussi une autre façon de procéder.

Je viens en effet d'y jeter un oeil, merci pour la suggestion!

En vous souhaitant une bonne fin de semaine,

Cordialement.