Nombre d'applications

[mehdi-128]

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 .
* Pour construire f donnons nous une injection. Il y a choix d'injections.
* 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). [b]
* Parmi ces injections, une seule est strictement croissante.

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|].

[LB2]

Bonjour mehdi-128,

il s'agit d'un principe de combinatoire connu sous le nom de lemme des bergers : si on compte 4n pattes de moutons, on déduit qu'il y a n moutons car chaque mouton a quatre pattes.

[Pseuda]

Bonjour,

Pour construire une injection de [|1,p|] dans [|1,n|], on a choisi p nombres distincts parmi n, et on les a ordonnés (d'où A(n,p) le nombre d'injections). Il y a p! façons d'ordonner p nombres, et parmi celles-ci, il n'y a qu'une seule façon de ranger ces p nombres en ordre croissant (donc strictement croissant puisque ces nombres sont distincts) . D'où le résultat.

Mais f(X)=(f(1), ..., f(p)) écrit ainsi, ne veut à mon sens rien dire. Ils veulent certainement parler des injections qui ont le même ensemble image qu'une injection : {f(1), ..., f(p)}=f( [|1,p|]). Mais je ne vois pas ce que vient faire le X là-dedans (désigné ainsi, X serait une partie de [|1,p|]).

[Pseuda]

Bonjour,

En relisant la question, j'ai dû la comprendre de travers. Tout d'abord, A(n,p) est un multiple de p!, car A(n,p)=C(n,p)*p!

On regroupe les A(n,p) applications injectives par paquets de p! applications injectives : un paquet est formé de toutes celles qui ont le même ensemble image par f. Parmi ces p! applications, 1 seule est strictement croissante. Donc il y a autant d'applications injectives strictement croissantes qu'il y a de paquets, et il y a combien de paquets ?

[Pseuda]

C'est beaucoup se compliquer : autant dire directement qu'il y a autant d'applications injectives strictement croissantes qu'il y a de façons de choisir p nombres distincts parmi n, car une fois ces nombres choisis, il n'y a qu'une façon de les ordonner de manière croissante, et on affecte : f(1)=le plus petit de ces nombres, f(2)=le 2ème plus petit, etc... . Soit il y en a C(n,p).

[mehdi-128]

Bonjour,

En relisant la question, j'ai dû la comprendre de travers. Tout d'abord, A(n,p) est un multiple de p!, car A(n,p)=C(n,p)*p!

On regroupe les A(n,p) applications injectives par paquets de p! applications injectives : un paquet est formé de toutes celles qui ont le même ensemble image par f. Parmi ces p! applications, 1 seule est strictement croissante. Donc il y a autant d'applications injectives strictement croissantes qu'il y a de paquets, et il y a combien de paquets ?

Mais je comprends pas d'où sort ce

Bah il y a p! paquets et dans chaque paquet 1 seule application strictement croissante donc il y a p! application strictement croissante je comprends pas je trouve pas la même chose.

[mathelot]

bonjour,
si l'on prend p nombres de [|1;n|] dans le désordre, i.e, une partie de [|1;n|] à p éléments, il y a une seule façon d'en ordonner ses éléments.
A une partie de [|1;n|] à p éléments on associe bijectivement une fonction strictement croissante de [|1;p|] dans [|1;n|]
il y a donc fonctions strictement croissantes de [|1;p|] dans[|1;n|]

[mehdi-128]

bonjour,
si l'on prend p nombres de [|1;n|] dans le désordre, i.e, une partie de [|1;n|] à p éléments, il y a une seule façon d'en ordonner ses éléments.
A une partie de [|1;n|] à p éléments on associe bijectivement une fonction strictement croissante de [|1;p|] dans [|1;n|]
il y a donc fonctions strictement croissantes de [|1;p|] dans[|1;n|]

J'ai pas compris votre démonstration, vous allez trop vite.

Sinon j'aimerais comprendre le passage de la démo que j'ai mise.

[Pseuda]

Mais je comprends pas d'où sort ce

Bah il y a p! paquets et dans chaque paquet 1 seule application strictement croissante donc il y a p! application strictement croissante je comprends pas je trouve pas la même chose.

Ne connais-tu pas les formules pour le nombre d'arrangements de p éléments pris dans un ensemble à n éléments, et le nombre de combinaisons C(n,p) = (ou coefficient binomial) de p parmi n ?

https://fr.wikipedia.org/wiki/Arrangement

On voyait cela en terminale avant. Mais c'est vrai qu'ils apprennent aujourd'hui à calculer un intervalle de fluctuation, mais qu'ils ne connaissent pas la formule du coefficient binomial !

Sinon, @mathelot a très bien répondu à ta question.

Messages croisés, je laisse.

[Pseuda]

Le mieux est de prendre un exemple numérique : n=5, p=3. Le nombre d'applications injectives est =5*4*3=60 (nombre de façons de choisir dans l'ordre 3 éléments parmi 5). Parmi ces applications, certaines ont le même ensemble image, par exemple f(1)=5, f(2)=1, f(3)=4, et g(1)=1, g(2)=4, g(3)=5, ont le même ensemble image {1,4,5}. Il y a 3!=6 applications qui ont le même ensemble image (6=nombre de façons d'ordonner 1,4,5). Parmi ces 6 applications, une seule est strictement croissante (c'est la 2ème de mon exemple).
Reprenons. Pour chaque ensemble image, il y a 3! applications injectives dont 1 seule strictement croissante. Donc, pour obtenir le nombre d'applications strictement croissantes, on divise le nombre d'applications injectives : 60, par le nombre d'ensembles images : 3!, cela en fait 10 =.

On peut dire aussi directement qu'il y a ensembles images (nombre de façons de choisir 3 éléments parmi 5, l'ordre ne comptant pas) et 1 seule application strictement croissante par ensemble image, donc il y a en 10.

[mehdi-128]

@Mathelot a donné une autre démonstration que je comprends pas d'ailleurs.
Mais j'ai juste envie de comprendre celle qui est donnée dans mon livre de maths.

[mehdi-128]

Le mieux est de prendre un exemple numérique : n=5, p=3. Le nombre d'applications injectives est =5*4*3=60 (nombre de façons de choisir dans l'ordre 3 éléments parmi 5). Parmi ces applications, certaines ont le même ensemble image, par exemple f(1)=5, f(2)=1, f(3)=4, et g(1)=1, g(2)=4, g(3)=5, ont le même ensemble image {1,4,5}. Il y a 3!=6 applications qui ont le même ensemble image (6=nombre de façons d'ordonner 1,4,5). Parmi ces 6 applications, une seule est strictement croissante (c'est la 2ème de mon exemple).
Reprenons. Pour chaque ensemble image, il y a 3! applications injectives dont 1 seule strictement croissante. Donc, pour obtenir le nombre d'applications strictement croissantes, on divise le nombre d'applications injectives : 60, par le nombre d'ensembles images : 3!, cela en fait 10 =.

On peut dire aussi directement qu'il y a ensembles images (nombre de façons de choisir 3 éléments parmi 5, l'ordre ne comptant pas) et 1 seule application strictement croissante par ensemble image, donc il y a en 10.

Ah voilà votre exemple est super

Le passage que je comprends pas est le suivant :

Donc, pour obtenir le nombre d'applications strictement croissantes, on divise le nombre d'applications injectives : 60, par le nombre d'ensembles images : 3!

[mehdi-128]

C'est une formule de probabilité ?

[Pseuda]

On a 60 bonbons (applications injectives). On les mets dans des paquets (ensembles images) qui n'admettent que la même couleur de bonbons. Il y a donc une seule couleur (application strictement croissante) par paquet. Chaque paquet contient 10 bonbons. Il y a combien de couleurs ?

[Pseuda]

C'est une formule de probabilité ?

Cela n'a rien à voir avec les probabilités. C'est du dénombrement. Les formules de dénombrement peuvent aider à calculer certaines probabilités (discrètes et équiprobables), mais elles peuvent s'en passer.

[LB2]

C'est une formule de probabilité ?

Non c'est le principe des bergers, ce que je t'expliquais plus haut. Si par exemple on a 240 œufs qu'on regroupe par boite de 12 œufs, on peut dire qu'on a 20 douzaines.

Pour reprendre l'exemple de Pseuda, avec et, il y a applications injectives de dans .

Pour un ensemble image fixé, par exemple {1,4,5} on peut trouver 6 applications qui ont cette image.
En notant une application comme un triplet , on a
(1,4,5)
(1,5,4)
(4,1,5)
(4,5,1)
(5,1,4)
(5,4,1)

soit tous les ordres possibles (on parle de permutation). Il y a 6 ordres possibles. Parmi ces 6, seul 1 est "dans le bon ordre", c'est à dire correspond à une application strictement croissante, c'est (1,4,5).

Il y a donc autant d'applications strictement croissantes que de "paquet de 6 applications". Il y a 10 paquets. Donc il y a 10 applications strictement croissantes.

[hdci]

Ne connais-tu pas les formules pour le nombre d'arrangements de p éléments pris dans un ensemble à n éléments, et le nombre de combinaisons C(n,p) = (ou coefficient binomial) de p parmi n ?
[...]
On voyait cela en terminale avant. Mais c'est vrai qu'ils apprennent aujourd'hui à calculer un intervalle de fluctuation, mais qu'ils ne connaissent pas la formule du coefficient binomial !

Moi, j'ai vu ces formules en seconde... (seconde C de l'époque...)
Mais c'est vrai, aujourd'hui on apprend à utiliser des calculatrices (qu'on ne rencontre pas dans le monde professionnel d'ailleurs puisqu'il y a Excel) mais pas les formules...

[hdci]

Pour comprendre les formules :

1) Permutation de éléments (on dispose de éléments différents et on cherche le nombre total de possibilité de rangement dans cases) :

• pour la première case, il y a choix possibles
• pour la seconde case, il reste choix possibles. Donc pour chacun des premiers choix (case 1), il y a choix (case 2), soit combinaisons
• pour la troisième case, il reste choix, soit avec les combinaisons précédentes, possibilités
• etc.
• pour la dernière case, il ne reste qu'un seul choix, et compte tenu de ce qui précède, cela fait possibilités au total

Il y a donc possibilités de ranger éléments dans cases.

2) Arrangements : ou quel est le nombre de possibilités du tiercé dans l'ordre.
C'est le même principe, on dispose de éléments, mais de cases seulement. On voit alors avec le raisonnement précédent que le nombre de possibilités est , ce que l'on note . On voit facilement que

3) Combinaisons : ou quel est le nombre de possibilités du tiercé dans le désordre (c'est-à-dire sans se soucier de l'ordre), ou encore le nombre de combinaisons du loto (5 boules parmi 49, l'ordre n'est pas important)
On sait que le nombre d'arrangement (dans l'ordre) est .
On sait aussi que le nombre de permutations de éléments est
Il y a donc exactement arrangements qui contiennent les mêmes éléments dans un ordre quelconque. Soit p! arrangements pour une combinaison, le nombre de combinaisons est donc

On remarque d'ailleurs avec cette formule que

[mathelot]

2) Arrangements : ou quel est le nombre de possibilités du tiercé dans l'ordre.
C'est le même principe, on dispose de éléments, mais de cases seulement. On voit alors avec le raisonnement précédent que le nombre de possibilités est , ce que l'on note . On voit facilement que

[hdci]

@mathelot : euh oui, merci pour la correction ! Je modifie mon message