Inscription / Connexion Nouveau Sujet
Nombre d'applications strictement croissantes
Ramanujan
Bonsoir,
Le but de l'exercice est de déterminer le nombre d'application strictement croissance de [|1,p|] dans [|1,n|].
* L'application doit être nécessairement injective . j'ai compris
* Pour construire f donnons nous une injection. Il y a choix d'injections. j'ai compris
* On s'intéresse à l'ensemble image de ces injections qu'on note f(X) où . f(X) est inclus dans [|1,n|]. Quitte à permuter les éléments de X, il y a
injections qui auront la même image f(X). j'ai compris
* Parmi ces injections, une seule est strictement croissante. j'ai compris
Je comprends pas le passage de la partie précédente à la conclusion
Il y a donc : application strictement croissance de [|1,p|] dans [|1,n|].
Soit E l'ensemble des injections de [|1,p|] dans [|1,n|]
Si f et g sont dans E on écrit f R g au lieu de f( [|1,p|] ) = g ( [|1,p|] ) .
C'est une équivalence .
Le nombre de classes modulo R est exactement le nombre d'applications strictement croissantes de [|1,p|] dans [|1,n|].
Soit Sp le groupe des bijections de [|1,p|] sur [|1,p|] .
Si f et g de E vérifient f R g et si s 
Sp il est clair qu'on a : f o s R g o s
….
J'ai rien compris. J'ai pas encore vu les classes et les groupes de bijection, je suis au 1er chapitre.
Je demandais par rapport à la démonstration que j'ai écrite comment on obtient la dernière ligne ?
Si je pars dans une autre démo compliquée je vais tout mélanger.
salut
tu n'as jamais vu les groupes ?
ce que dit etniopal :
soit I = [1, p], J = [1, n] et K une partie de J à p éléments
pour tout couples f et g d'injections (et donc de bijections) de I dans K il existe une bijection s telle que g = s o f
et parmi toutes les injections de I dans K il y en a une seule qui soit croissante ...
et il y a p! injections de I dans K
Pas encore vu les groupes je suis au chapitre 1.
Toujours rien compris au couple d'injections f et g. et à la composée qui sort de nulle part. C'est du chinois.
Je reste sur la démo de mon livre qui est plus claire et compréhensible :
Il y a choix d'injections.
Il y a p! injection qui ont la même image et 1 qui est strictement croissante.
Je vois pas comment en déduire le nombre d'application croissantes.
Bonsoir,
j'imagine que, quelque part dans l'énoncé, il y a écrit p
n.
Si ce n'est pas le cas, il faut dire qu'il n'y a aucune injection de I=[|1 ; p|] dans K=[|1 ; n|] quand p>n.
Ensuite on choisit une partie L de K à p éléments, et il n'y a qu'une injection strictement croissante de I dans L. C'est d'ailleurs une bijection de I dans L.
Et ce qu'écrivit carpediem, que je salue, est faux.
@ThierryPoma.
Je suis sans doute un peu vieux.
Mais ton lien me semble un bon exemple de démonstration prétentieuse.
C'est à dire que l'on met plein de circonvolutions pseudo-rigoureuses pour faire semblant de démontrer une évidence.
Bonjour,
Rapidement de mon boulot :
@Carpi : Tu choisis une partie de
constituée de
éléments mutuellement distincts. Cette partie est totalement ordonnée (et même bien ordonnée) par l'ordre usuel sur
induit sur toutes ses parties (y compris la partir vide !). Il existe donc
bijections de
sur
, dont une seule est strictement croissante. Où en est-on ?
Tu auras soin de remarquer que ce n'est pas la même chose que de considérer l'ensemble de toutes les injections de dans
et dont on connait le cardinal.
On pourrait, peut-être faire simple ... :
Si f est strictement croissante de dans
, l'image de
est une partie de
à
éléments (ben oui, les
pour
sont 2 à 2 différents).
Si est une partie de
à
éléments, il y a une et une seule application strictement croissante
de
dans
:
est nécessairement l'élément d'indice minimum de
,
le suivant et ainsi de suite jusqu'à
.
Il y a donc autant d'appplications strictement croissantes de dans
que de sous-ensembles à
éléments de l'ensemble à
éléments
, c'est-à-dire
(c'est naturellement
si
)
Mais pourquoi faire simple quand on peut faire compliqué ?
Bonjour,
Aurais-tu lu ce document-ci ?
Oui c'est la même démo que dans mon livre de Costantini je comprends tout sauf le dernier passage comme j'ai expliqué dans mon post.
On a regroupé les injections de [|1,p|] vers [|1,n|] en paquets disjoints de cardinal n! suivant leur Image Im(f).
Et là je comprends pas comment il en déduit la phrase suivante :
Il y a donc tels paquets.
Dans chaque paquet il y a une seule application croissante donc il y a telles applications en tout.
On a regroupé les injections de [|1,p|] vers [|1,n|] en paquets disjoints de cardinal n! suivant leur Image Im(f).
Et là je comprends pas comment il en déduit la phrase suivante :
Il y a donc tels paquets.
Dans chaque paquet il y a une seule application croissante donc il y a telles applications en tout.
On pourrait, peut-être faire simple ... :
Si f est strictement croissante de
Si
Il y a donc autant d'appplications strictement croissantes de
Mais pourquoi faire simple quand on peut faire compliqué ?
Totalement, j'ai compris votre preuve
J'aimerais juste comprendre celle qui est dans mon livre.
Je cite :
représente le nombre d'applications strictement croissantes de l'ensemble
dans l'ensemble
.
Démonstration :
Un telle application f est nécessairement injective (si 2 éléments distincts avaient la même image, f ne pourrait être strictement croissante).
Pour construire f, il faut se donner déjà une telle injection : il y a choix.
Regroupons toutes ces injections selon leur ensemble image . Il y aura toujours
injections qui auront le même ensemble image f(X), une seule est strictement croissante. (il n'y a qu'une seule façon de trier dans l'ordre croissant une série de nombre donnés).
Le nombre d'applications strictement croissantes de dans l'ensemble
est : ?
Et là je voix pas comment trouver ce nombre d'applications croissantes
Bonjour,
Tu peux ce schéma.
Le cas où p=2 et n=3(ça ne sert à rien de définir n ici)
Prenons par le paquet d'applications qui ont pour image {1,2} , ce paquet contient deux applications f1 et f2 soit p ! =2! applications , dont seule f1 est croissante et c'est évident que chaque paquet contient 2 applications dont une seule est croissante.
Comme dans chaque paquet on choisit 1 et que chaque paquet contient 2!, alors pour trouver le total on fait la somme divisé par 2! au lieu de divisé chaque paquet par 2! Et faire la somme ensuite.
Pour p=3 aussi remarquer que chaque paquet contient 6=3! Applicationns.
"Comme dans chaque paquet on choisit 1 et que chaque paquet contient 2!, alors pour trouver le total on fait la somme divisé par 2!"
J'ai pas compris pourquoi on doit diviser par 2! ...
Une façon de faire :
n et p étant des entiers tels que 0 < p n on désigne par
. 
l'ensemble des applications strictement croissantes de [|1,p|] dans [|1,n|]
. J l'ensemble des injections de [|1,p|] dans [|1,n|]
. S l'ensemble des injections de [|1,p|] dans [|1,p|]
Si s S et f on pose U(s , f) = f o s . C' est , clairemen t , un élément de J et on définit ainsi une application de 
S vers J .
Si on montre que U est bijective on aura le résultat annoncé , càd p!.Card() = Card(J) .
... Pour la surjectivité de U :
Soit g J .
{g(1),....,g(p)} est un ensemble de p éléments de [|1,n|] .
Si on les range par ordre croissant on va avoir {g(1),....,g(p)} = {g(t1) , …., g(tp)} où l'application t : k 
sk est injective donc est un élément de S .On voit alors que f := g o t est croissante et que g = f o t-1 = U(f , t-1) .
...Pour l'injectivité de U .
Si f , g sont dans , t et t ' dans S et f o t = g o t ' alors g o s = f si s := t ' o t-1 .
s est dans S et , comme g et f sont croissantes , s ne peut âtre que Id[|1,p|] de sorte que t = t ' et f = g .
Ca a l'air joli etnopial mais je laisse ça aux plus aguéris. J'ai pas encore le niveau, je préfère rester sur des choses simples sinon je vais me décourager.
"Comme dans chaque paquet on choisit 1 et que chaque paquet contient 2!, alors pour trouver le total on fait la somme divisé par 2!"
J'ai pas compris pourquoi on doit diviser par 2! ...
Une autre manière de comprendre :
Comme dans chaque paquet on a une application strictement croissante, il y'a donc autant d'applications strictement croissante que de paquets.
Combien vaut le nombre de paquets ?
Chaque paquet correspond à un ensemble d'applications qui ont pour image un sous-ensemble à p éléments de [|1,n|],donc il y'a autant de paquets que de parties de [|1,n|] à p éléments .
Il y'a combien de parties de [|1,n|] à p éléments.
Bien-sûr tu connais la réponse : C(n,p)=A(n,p)/p !.
Donc en fin il y'a A(n,p)/p ! applications strictement croissante de [|1,p|] vers [|1,n|].
@Toureissa en effet vous avez raison mais j'ai réussi finalement à comprendre la démonstration que j'ai posté grâce à votre exemple.
J'ai enfin compris grâce à cet exemple !
Il y a applications injectives et parmi elles
applications qui ont la même image.
Notons k le nombre d'applications qui ont la même image. Ainsi :
Or il y a 1 seule application strictement croissante tout les p! il y a donc k applications strictement croissantes en tout. Finalement :
Une façon de faire :
n et p étant des entiers tels que 0 < p
n on désigne par
.
l'ensemble des applications strictement croissantes de [|1,p|] dans [|1,n|]
. J l'ensemble des injections de [|1,p|] dans [|1,n|]
. S l'ensemble des injections de [|1,p|] dans [|1,p|]
Si s
S et f on pose U(s , f) = f o s . C' est , clairemen t , un élément de J et on définit ainsi une application de S vers J .
Si on montre que U est bijective on aura le résultat annoncé , càd p!.Card(
) = Card(J) .
... Pour la surjectivité de U :
Soit g
J .
{g(1),....,g(p)} est un ensemble de p éléments de [|1,n|] .
Si on les range par ordre croissant on va avoir {g(1),....,g(p)} = {g(t1) , …., g(tp)} où l'application t : k
sk est injective donc est un élément de S .On voit alors que f := g o t est croissante et que g = f o t-1 = U(f , t-1) .
...Pour l'injectivité de U .
Si f , g sont dans
, t et t ' dans S et f o t = g o t ' alors g o s = f si s := t ' o t-1 .
s est dans S et , comme g et f sont croissantes , s ne peut âtre que Id[|1,p|] de sorte que t = t ' et f = g .
Honnêtement c'est incompréhensible, y a des t1 ,..., tp qui sortent de nulle part on sait même pas c'est quoi.
Le t on comprend rien il correspond à quoi.
Vous appliquer
U dépend de 2 applications, la façon dont vous montrez la surjectivité est bizarre : dans le cours ça dépend que d'une variable.
Bref, c'est pas du tout niveau maths sup ou je suis très nul.
Bonjour,
Rapidement de mon boulot :
Il y a
Notons k le nombre d'applications qui ont la même image. Ainsi :
Es-tu certain d'avoir bien compris ?
C'est incompréhensible pour ceux qui ne veulent pas comprendre et ne font aucun effort pour comprendre .
Concernant les tj :
{g(1),....,g(p)} est un ensemble de p éléments de [|1,n|] . les g(k) sont distincts .
Soit m1 son plus petit élément .
{ k [|1,p|] │ g(k) = m1 } est un singleton ( faut te le prouver ? ) . Je le note { t1 } . Donc m1 = g(t1) .
Soit m2 le plus petit élément de {g(1),....,g(p)} \ { m1}
{ k [|1,p|] │ g(k) = m2 } est un singleton . Je le note { t2 } . Donc m2 = g(t2) . De plus on a t1 
t12 .(Pas clair ? faut te le prouver ? )
etc
Les tj ainsi fabriqués étant distincts l'application k tk (que je note bien sûr t ) qui part de [|1,p|] pour arriver dans [|1,p|] est donc bijective .(faut te le prouver ? ) .C'est donc un élément de S .
Bonjour,
Rapidement de mon boulot :
Il y a
Notons k le nombre d'applications qui ont la même image. Ainsi :
Es-tu certain d'avoir bien compris ?
Mon raisonnement est faux ?
C'est incompréhensible pour ceux qui ne veulent pas comprendre et ne font aucun effort pour comprendre .
Concernant les tj :
{g(1),....,g(p)} est un ensemble de p éléments de [|1,n|] . les g(k) sont distincts .
Soit m1 son plus petit élément .
{ k
[|1,p|] │ g(k) = m1 } est un singleton ( faut te le prouver ? ) . Je le note { t1 } . Donc m1 = g(t1) .
Soit m2 le plus petit élément de {g(1),....,g(p)} \ { m1}
{ k
[|1,p|] │ g(k) = m2 } est un singleton . Je le note { t2 } . Donc m2 = g(t2) . De plus on a t1 t12 .(Pas clair ? faut te le prouver ? )
etc
Les tj ainsi fabriqués étant distincts l'application k
tk (que je note bien sûr t ) qui part de [|1,p|] pour arriver dans [|1,p|] est donc bijective .(faut te le prouver ? ) .C'est donc un élément de S .Ah là c'est beaucoup plus clair
Annuler
connectez vous
analyse en post-bac