Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Partager :

Nombre d'involutions

Posté par
toureissa 02-07-18 à 10:04

Bonjour,

J'ai  besoin  d'aide  sur la deuxième  question.

Pour toi ensemble  E fini , de cardinal  n>=1 , on note u_n le nombre  d'involution  de E,  c'est-à-dire  d'applications  f de E dans E telles que  fof=idE .

1) calculer  u_1,u_2 et u_3.

Pas de problème  j'ai eu u_1=1,\;  u_2=2\;  u_3=4


2) Pour tout n\in \N* montrer que u_{n+2}=u_{n+1}+(n+1)u_{n}

Posté par
jsvdbre : Nombre d'involutions 02-07-18 à 11:01

Bonjour toureissa.

Je te propose de numéroter les éléments de E et donc de considérer E=E_n = [[1;n]] pour n \geq 1.

De manière générale, je vais (re)noter \matcal I_X, l'ensemble des involutions d'un ensemble X non vide et fini.

Dans un premier temps tu découpes I_{[[1;n+2]]} = \bigcup_{k=1}^{k=n+2}\{f\in I_{[[1;n+2]]}~/~f(1)=k\}. Ça forme une partition de I_{[[1;n+2]]}.

\bullet Pour k = 1 tu formes la bijection \blue \varphi_1 : \{f\in I_{[[1;n+2]]}~/~f(1)=1\} \rightarrow I_{[[2;n+2]]},~\varphi_1(f) = f|_{[[2;n+2]]}.
Tu vérifies évidemment que \varphi_1 est bien bijective (et au passage, tu trouves son inverse).

\bullet Pour k > 1 tu formes la bijection \blue \varphi_k : \{f\in I_{[[1;n+2]]}~/~f(1)=k\} \rightarrow I_{[[2;n+2]]\backslash\{k\}},~\varphi_k(f) = f|_{[[2;n+2]]\backslash\{k\}}.
Tu vérifies évidemment que \varphi_k est bien bijective (et au passage, tu trouves son inverse).

On prend les cardinaux dans la partition, on utilise les bijections et bien entendu l'hypothèse de récurrence :

\begin {aligned}u_{n+2} &= \text{ Card }I_{[[1;n+2]]} \\ & =\sum_{k=1}^{n+2}{\text{Card }\{f\in I_{[[1;n+2]]}~/~f(1)=k\}} \\ & = \cdots\end{aligned}

Posté par
Zrunre : Nombre d'involutions 02-07-18 à 11:02

Distinguer suivant  f(n)=n ou pas ...

Posté par
toureissare : Nombre d'involutions 02-07-18 à 14:46

Est-ce  vrai ce que j'ai  dit :

Card({f\in I_{[|1; n+2|]}/f(1)=k})=(n+1)!
Parce-que  l'image  d'un élément  est fixé  et il ya  (n+1)!  bijections des éléments  restant ?

Posté par
carpediemre : Nombre d'involutions 02-07-18 à 15:10

salut

soit E = E_n, F = E_{n + 1} et G = E_{n + 2}  avec les notations de jsvdb


alors il y a deux cas :

soit f est une involution de F et alors pour que f soit une involution de G il est nécessaire que f(n + 2) = n + 2

soit f n'est pas une involution de F à cause d'un des n + 1 éléments de F mais est une involution de E

...

Posté par
jsvdbre : Nombre d'involutions 02-07-18 à 15:32

... tout-à-fait.

Donc ce que carpediem a fait avec "n+2", je l'ai fait avec "1", mais ça change rien :

\begin {aligned}u_{n+2} &= \text{ Card }I_{[[1;n+2]]} \\ & =\sum_{k=1}^{n+2}{\text{Card }\{f\in I_{[[1;n+2]]}~/~f(1)=k\}} \\ & =\text{Card }\{f\in I_{[[1;n+2]]}~/~f(1)=1\}}+\sum_{k=2}^{n+2}{\text{Card }\{f\in I_{[[1;n+2]]}~/~f(1)=k\} \\ & = u_{n+1} + (n+1)u_n\end{aligned}

La dernière ligne étant obtenue simultanément grâce aux bijections et à l'hypothèse de récurrence.

Posté par
toureissare : Nombre d'involutions 02-07-18 à 16:52

Avec les bijections on a :

Card(\{f\in I_{[|1; n+2|] }/ f(1)=k\})=Card(I_{[|1:n+2|]-{k}})?

J'ai compris  ce que vous avez écrit  mais je ne sais pas d'où  vient u_{n+1} \; et\; (n+1) u_n

Posté par
jsvdbre : Nombre d'involutions 02-07-18 à 17:17

Effectivement, s'il y a bijection de A sur B alors par définition du cardinal, #A = #B.

\{f\in I_{[[1;n+2]]}~/~f(1)=1\}} est l'ensemble des involutions de [[1;n+2]] qui laissent "1" stable. C'est donc en bijection avec les involutions de [[2;n+2]] qui est de cardinal u_{n+1} par hypothèses de récurrence.

Tu fais un raisonnement identique avec les n+1 autres membres de la somme.

Posté par
Jezebethre : Nombre d'involutions 02-07-18 à 17:37

Bonjour

Curiosité : pourrait-on se débrouiller pour récupérer le terme explicite à partir de cette relation ? (je cherche)

Posté par
jsvdbre : Nombre d'involutions 02-07-18 à 17:56

Bonjour Jezebeth.
Je ne comprends pas ce que vous voulez dire ?

Posté par
Jezebethre : Nombre d'involutions 02-07-18 à 17:58

Une envie naturelle serait de déduire de

\forall n \in N^*,\, u_{n+2}=u_{n+1}+(n+1)u_n

et des deux premiers termes une expression de u_n en fonction de n, non ?

Posté par
jsvdbre : Nombre d'involutions 02-07-18 à 18:00

Ah d'accord pourquoi pas, mais ça viendrait donc dans un second temps par rapport à l'exercice.

Posté par
Jezebethre : Nombre d'involutions 02-07-18 à 18:01

En tout cas là tout de suite je ne vois pas trop comment m'y prendre.

Posté par
toureissare : Nombre d'involutions 02-07-18 à 18:33

u_{n+2}=Card(\{f\in I_{[|1; n+2|]}/f(1)=1\})+\sum_{k=2}^{n+2}{Card\{f\in I_{[|1; n+2|]}/f(1)=k\}})

u_{n+2}=u_{n+1}+\sum_{k=2}^{n+2}{Card\{f\in I_{[|1; n+2|]}/f(1)=k\}})

u_{n+2}=u_{n+1}+\sum_{k=2}^{n+2}{Card(I_{[|2; n+2|]-\{k\}}})

u_{n+2}=u_{n+1}+\sum_{k=2}^{n+2}{u_n}

u_{n+2}=u_{n+1}+(n+2-2+1)u_n

u_{n+2}=u_{n+1}+(n+1)u_n

C'est bon ?

Posté par
toureissare : Nombre d'involutions 03-07-18 à 09:30

Bonjour,
Est-ce que ce que  je fais c'est bon ?

Posté par
toureissare : Nombre d'involutions 03-07-18 à 09:34

J'ai le souci  d'avoir  un Professeur  comme vous  a  côté  de moi qui m'expliquait  les maths.

Depuis au collège  j'ai  un professeur  qui pousse les élèves  à  aimer les maths.

Posté par
jsvdbre : Nombre d'involutions 03-07-18 à 09:36

oui c'est bon pour ton dernier calcul

Posté par
toureissare : Nombre d'involutions 03-07-18 à 09:40

Merci à vous !

Posté par
verdurinre : Nombre d'involutions 03-07-18 à 16:16

Salut Jezebeth.

Citation :
Une envie naturelle serait de déduire de

\forall n \in N^*,\, u_{n+2}=u_{n+1}+(n+1)u_n

et des deux premiers termes une expression de u_n en fonction de n, non ?

Je ne crois pas que ce soit possible, et j'ai triché pour le savoir.
OEIS

Posté par
Jezebethre : Nombre d'involutions 03-07-18 à 16:55

Salut verdurin,

Je ne vois pas sur la page l'endroit où ils abordent la question ?

Posté par
verdurinre : Nombre d'involutions 03-07-18 à 17:25

Assez bas, il y a une entrée FORMULA.

Posté par
Jezebethre : Nombre d'involutions 03-07-18 à 17:35

Ah oui merci !


En même temps tous les exercices ne demandent que la relation de récurrence, j'aurais dû m'en douter...

Posté par
carpediemre : Nombre d'involutions 03-07-18 à 17:54

Jezebeth @ 03-07-2018 à 17:35

Ah oui merci !


En même temps tous les exercices ne demandent que la relation de récurrence, j'aurais dû m'en douter...
non certains !!!

Posté par
Jezebethre : Nombre d'involutions 03-07-18 à 17:55

Qu'est-ce qu'on peut bien demander d'autre que la relation de récurrence alors ?

Posté par
carpediemre : Nombre d'involutions 03-07-18 à 18:37

ben je ne sais pas ... seul le posteur peut nous le dire ...

je t'ai simplement repris (en toute cordialité) sur ton affirmation qui est fausse ....

heureusement que tous les exercices ne demandent pas que la relation de récurrence ...

Posté par
Jezebethre : Nombre d'involutions 03-07-18 à 18:41

Ah oui, d'accord. Je voulais bien sûr dire "tous les exercices sur le sujet"


(Merci au passage de ton intervention sur le sujet Dénombrement II, il faut que je reprenne cela à tête reposée, pour le moment je ne réponds pas pour ne pas polluer le fil inutilement.)

Posté par
Jezebethre : Nombre d'involutions 03-07-18 à 19:46

Rectification : c'est possible. Bon, en alternant sur la parité.

Pour tout entier n naturel non nul,

u_{2n}=\sum_{k=0}^{n}\frac{(2k)!}{2^kk!}\begin{pmatrix} 2n\\2k \end{pmatrix}

u_{2n+1}=\sum_{k=0}^{n}\frac{(2k)!}{2^kk!}\begin{pmatrix} 2n+1\\2k \end{pmatrix}

sauf erreur.

Posté par
Jezebethre : Nombre d'involutions 04-07-18 à 17:18

On peut même trouver le terme général :

u_n=\sum_{k=0}^{\frac{n}{2}}\frac{n!}{2^k(n-2k)!k!}

Posté par
toureissare : Nombre d'involutions 04-07-18 à 17:28

Comment  vous avez trouvé  ces résultats ?

Posté par
Jezebethre : Nombre d'involutions 04-07-18 à 17:29

En l'occurrence c'est un exercice posté par Jean-Michel Ferrard : http://www.mathprepa.fr/2016/12/involutions-series-entieres/

Posté par
toureissare : Nombre d'involutions 04-07-18 à 17:41

Ah oui  je vois.
Je n'ai pas encore vu les séries  entières.

Posté par
verdurinre : Nombre d'involutions 04-07-18 à 21:46

Pour rire :
on veut calculer u_{10}.

Utiliseriez vous la formule

u_{10}=\sum_{k=0}^{5}\frac{n!}{2^k(n-2k)!k!}\ ?

ou la formule

u_{n+2}=u_{n+1}+(n+1)u_n\ ?

Posté par
Jezebethre : Nombre d'involutions 05-07-18 à 00:01

La première bien sûr !

Posté par
carpediemre : Nombre d'involutions 05-07-18 à 13:01

je ne calcule pas ... j'utilise un esclave ...

Posté par
Jezebethre : Nombre d'involutions 05-07-18 à 21:45

Bon, promis, après j'arrête les remarques sur ce fil. Une jolie résolution pourrait aussi être de se ramener aux matrices. Le dénombrement demandé se ramène, moyennant quelques raisonnements, à celui du cardinal de GLn(K), K étant le corps commutatif du pb. Ce qui se fait sans trop d'encombres, c'est assez classique. (Construire les colonnes de la matrice une à une, sachant qu'elles doivent être linéairement indépendantes.)


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1768 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !