Nombre d'involutions de E

[Anonyme]

Bonsoir,
J'ai l'exercice suivant qui me pose problème :
Soit Tn le nombre d'involutions de E, E étant un ensemble à n éléments. Calculer T1, T2 et T3.

On suppose désormais n>=3.
Déterminer en fonction de Ti, où 1=- le nombre des involutions s de [1,n] telles que s(n)=n;
- le nombre des involutions s de [1,n] telles que s(n)=k, où k est un noubre entier donné de [1,n-1].

Je ne vois pas comment faire, et surtout je ne comprends pas vraiment comment résoudre la question même T1, T2 et T3. Je sais qu'on appelle involution de E toute bijection f de E sur lui-même telle que fof=Id. Mais à part ça, que faire ?

[abcd22]

Si E est un ensemble à 1, 2 ou 3 éléments, on peut expliciter toutes les bijections de E dans E (ce sont les permutations, il y en a respectivement 1, 2 et 3!=6), donc pour chaque application on peut regarder ce que donne fof.

[yos]

n>=3
Une involution de [1,n] telle que s(n)=n est déterminée par sa restriction à [1,n-1] qui est une involution de [1,n-1]
En d'autre termes il y a autant d'involutions de [1,n] telle que s(n)=n que d'involutions de [1,n-1] , c'est-à-dire...

Dans la seconde catégorie s(n)=k (différent de n). On a donc s(k)=n. Et s est caractérisée par sa restriction à {1,2,...,k-1,k+1,...n-1}. Il y a donc T(n-2) involutions de ce type.

D'où relation de récurrence Tn=...

[Anonyme]

Bonjour, pour T1=1 et T2=2 je suis d'accord par contre T3=6 je ne vois pas. Surtout que dans la suite de l'exercice on me demande vérifier la relation de récurrence Tn=Tn-1 + (n-1)Tn-2. Donc logiquement, T3=4 ?
Sinon pour le reste, j'avoue ne pas avoir très bien compris ...

[yos]

abcd22 n'a jamais dit ça. Il t'a dit qu'il y a 3! permutations. A toi de voir lesquelles sont des involutions. Si E={1,2,3}, les 6 permutations de E sont (123), (132), (213), (231), (312), (321) (on donne à chaque fois les images de 1,2,3 dans l'ordre). Mais l'avant-dernière par exemple n'est pas une involution car (312)o(312)=(231) qui n'est pas l'identité. Tu as raison en disant que T3=4 et je te laisse regarder.

Quant à la relation de récurrence, utilise ce que je t'ai écrit précédemment : Il y a T(n-2) involutions qui envoient n sur k et k peut être choisi de n-1 façons (1,2,...ou n-1 mais pas n). D'où le terme (n-1)T(n-2).