Bonsoir,
objectif c'est de déterminer le nombre d'applications croissantes de [1,n] dans [1,p]
que je sais calculer on faisant tronsformer une application croissante on une application strictemment croissante
mais mon problème c'est que on me donne l' indication suivante:
"interpréter une application croissante par le schéma suivant: une rangée de n+p-1 points, (p-1) d'entre eux étant séparés d'un trait vertical appelé cloison"
merci
nombre d'applications croissantes
Re: nombre d'applications croissantes
Bonjour
On établit une liste de la manière suivante :
Tant que les entiers de 1 à k ont pour image 1, on écrit $k$ "1" qui se suivent et on termine par une cloison.
Si aucun entier n'a pour image 1, on commence par une cloison.
On poursuit avec autant de 2 qu'il y a d'entiers suivants qui ont pour image 2 puis une cloison. Si aucun entier n'a pour image 2, on met simplement une cloison.
Et ainsi de suite sauf que lorsqu'on arrive aux derniers entiers qui ont pour image p, il est inutile de terminer par une cloison
Un exemple : soit l'application de [1,4] dans [1,5] telle que $f(1)=1, f(2)=1, f(3)=3, f(4)=5$. Elle est représentée par :
1 1 | | 3 | | 5.
Si $f(1)=f(2)=2, f(3)=f(4)=4$ la représentation est : | 2 2 | | 4 4 |
On a donc écrit $n$ nombres et $p-1$ cloisons donc $n+p-1$ symboles. Une application croissante est déterminée par la place des $p-1$ cloisons.
Le nombre d'applications croissantes est donc $n+p-1 \choose p-1$
On établit une liste de la manière suivante :
Tant que les entiers de 1 à k ont pour image 1, on écrit $k$ "1" qui se suivent et on termine par une cloison.
Si aucun entier n'a pour image 1, on commence par une cloison.
On poursuit avec autant de 2 qu'il y a d'entiers suivants qui ont pour image 2 puis une cloison. Si aucun entier n'a pour image 2, on met simplement une cloison.
Et ainsi de suite sauf que lorsqu'on arrive aux derniers entiers qui ont pour image p, il est inutile de terminer par une cloison
Un exemple : soit l'application de [1,4] dans [1,5] telle que $f(1)=1, f(2)=1, f(3)=3, f(4)=5$. Elle est représentée par :
1 1 | | 3 | | 5.
Si $f(1)=f(2)=2, f(3)=f(4)=4$ la représentation est : | 2 2 | | 4 4 |
On a donc écrit $n$ nombres et $p-1$ cloisons donc $n+p-1$ symboles. Une application croissante est déterminée par la place des $p-1$ cloisons.
Le nombre d'applications croissantes est donc $n+p-1 \choose p-1$
Re: nombre d'applications croissantes
c claire merci