idée ? bijection PCSI

[invitef1a58918]

voila je pensais à un truc :

Soit n le nombre d'élement de En.
Il y a n! nombre de bijection de En dans En.
En considérant f une bijection quelconque d'un ensemble a k élément de En telle que f(x) different de x : Nous obtenons donc un dérangement.

Le choix de cette bijection se fait en prenant k élément parmi n: il y en a donc ( k parmi n ).

Mais je sais pas si on peut dire qu'en sommant toutes ces bijections, on a toutes les bijections de En dans En soit n!


est ce possible ? il y a t il une demonstration propre pour le montrer ?
-----

[shokin]

Là, je n'ai pas vraiment compris ce qu'était En.

Pourquoi ya-t-il n! bijections dans En ayant n éléments ? à voir ainsi, je dirais plutôt n(n-1)/2 groupes de 2 éléments parmi n (soit C de 2 parmi n).

Parles-tu de bijections ? relations bijectives entre deux ensembles ?

C'est quoi un dérangement en mathématique ?

Admettons :

Soit En à n élément.

L'on prend k élément parmi n.

Je suppose que tu voulais dire : "Le choix de cette bijection se fait en prenant k éléments parmi n" plutôt que "Le choix de cette bijection se fait en prenant k, élément parmi n." (Désolé d'insister sur le français, mais là j'ai douté encore plus.)

Pour éviter de dire des bêtises, j'aimerais que tu répondes aux questions.

Shokin

[invitef1a58918]

-> En : ensemble ayant n éléments


-> Il me semble que le nombre total des bijections entre un ensemble En à n éléments dans lui même est de n! si je ne me trompe pas ( dans le doute,j'ai regardé sur un site, j'ai trouvé le même resultat : =>
http://membres.lycos.fr/ilemaths/Cou...ment_Cours.htm


-> Un dérangement D, de En dans En, est une bijection de En dans En telle que D(x) est différent de x ( l'image est différent de l'antécédant).


-> Effectivement c'est plutot "Le choix de cette bijection se fait en prenant k élémentS parmi n"


Merci de t'intéresser à cette question

[inviteebde0cf1]

salut, je n'ai pas compris ta question alyward ! ceci etant, le nb de bijection d'un ensemble a n elts sur un autre ensemble (necessairement aussi de cardinal n) est n! . En ce qui concerne le nombre de dérangements. Il est plus facile de dénombrer son complémentaire, c'est-a-dire l'ensemble des bijections ayant au moins un point fixe. En discutant suivant le point laisse fixe (cela peut etre 1, ou bien 2, ... ou bien n) tu vois que cet ensemble est la réunion pour k variant de 1 a n, des ensembles formés des bijections laissant k fixe. Cette reunion n'est pas disjointe. Pour calculer son cardinal, tu dois utiliser la fameuse formule de Poincare ou du crible... Bon courage !

[A voir en vidéo sur Futura]

[shokin]

Ah ! j'ai compris le terme de bijection !!! (je l'avais oublié )

Je comprends donc pourquoi dans En à n élément :

il y a n! bijections
et (n-1)! dérangement.

Mais si je ne prends que k éléments parmi n (avec k=<n),

J'ai donc C de n parmi k groupe de k éléments possibles parmi n, donc :

n!/(k!*(n-k)!)

Une fois ces k éléments choisis, je peux alors obtenir k! bijections.

J'ai donc n!/(k!*(n-k)!)*k! bijections possibles de k éléments parmi n.

ou simplifié : n!/(n-k)! bijections !

Mais combien y a-t-il de bijections en tout pour k allant de 1 à n ?

Somme des n!(n-k)! avec k allant de 1 à n.

Si je développe :

n!/(n-1)!+n!/(n-2)!+n!/(n-3)!+...+n!/(n-n)! = (tout sous le même dénominateur)

n!/(n-1)!+n!(n-1)/(n-1)!+...+n!(n-1)(n-2)...*2*1/(n-1)! = (mise en évidence de n!/(n-1)! )

(n!/(n-1)!)*(1+(n-1)+(n-1)(n-2)+...+(n-1)(n-2)...*2*1.

Je ne vois pas comment écrire plus simplement...

Mais est-ce égal à n! ? je ne sais pas. Et si oui, comment le démontrer ?

Shokin

[invitef1a58918]

je ne sais pas trop comment le démontrer justement, la formule du crible... notre professeur nous a pas donné d'exemple, mais je vais néanmoins essayer.

Si vous avez une autre idée.

En tout cas, merci de me répondre !

[invitef1a58918]

En discutant suivant le point laisse fixe (cela peut etre 1, ou bien 2, ... ou bien n) tu vois que cet ensemble est la réunion pour k variant de 1 a n, des ensembles formés des bijections laissant k fixe.

la formule de Poincarré nous est donnée avec des cardinals et des unions.

je ne vois pas trop comment utiliser cette formule.

Si tu peux m'aider encore stp

merci

[inviteebde0cf1]

salut

Pour le nombre de bijection de {1,..,n} dans lui-même. On peut décrire les étapes qui menent à la construction d'une telle application :

Je choisis l'image de 1. Pour ca j'ai n possibilités.
Je choisis l'image de 2. Pour ca, je n'ai plus que (n-1) possibilités.
(et oui, je ne peux pas reprendre pour 2 la même image que pour 1 sans quoi l'application construite ne serait plus injective.
Ainsi de suite, a chaque fois que je choisis une image, j'enlève une possibilité pour la prochaine.
A la fin,
Je choisis l'image de n-1... il me reste (n-(n-2)=2 possibilités
Je choisis l'image de n il me reste 1 possibilité

Au total, il y a nx(n-1)x...x2x1= n! façons différentes de construire une bijection de {1..n} dans lui-même.

[inviteebde0cf1]

Pour la formule de Poincaré. Il faut savoir que c'est la formule qui sert a calculer la cardinal d'une reunion. Bien sur tu sais que si les ensembles sont disjoints, les cardinaux s'ajoutent. La formule de Poincaré sert justement lorsque les ensembles de la réunion ne sont pas disjoints. Pour calculer le B)cardinal de AuB, on a

c'est la formule de Poincaré pour 2 ensembles.
Dans le cas general, c'est plus compluiqué a ecrire, mais tu l'as ds ton cours. La démonstration de cette formule se fait par récurrence sur le nombre d'ensembles dans la reunion. C'est une preuve technique, il faut faire attention dans le calcul de

[inviteebde0cf1]

Pour le nombre de derangement de {1,..,n} ( c'est dur!). On denombre son complémentaire. Pour cela on note

Quel est le lien entre l'ensemble des dérangements et les ?

Pour calculer le cardinal de A_k, il faut remarquer qu'il y a autant de bijection fixant k que de bijections d'un ensemble a n-1 elts dans lui-même.

Bon courage Aylward !!

[inviteebde0cf1]

Pour la formule de Poincaré. Il faut savoir que c'est la formule qui sert a calculer la cardinal d'une reunion. Bien sur tu sais que si les ensembles sont disjoints, les cardinaux s'ajoutent. La formule de Poincaré sert justement lorsque les ensembles de la réunion ne sont pas disjoints. Pour calculer le B)cardinal de AuB, on a

c'est la formule de Poincaré pour 2 ensembles.
Dans le cas general, c'est plus compluiqué a ecrire, mais tu l'as ds ton cours. La démonstration de cette formule se fait par récurrence sur le nombre d'ensembles dans la reunion. C'est une preuve technique, il faut faire attention dans le calcul de

Un caractere n'etait pas passe je modifie une reponse precedente.