etude du nombre Tn
Dominique Bernardi
In article (Dans l'article) <63ae19$heb$1...@nef.ens.fr>,
cass...@chaland.ens.fr (Julien Cassaigne) wrote (écrivait) :
>michel blois <Michel...@wanadoo.fr> demande :
>>etant donne un nombre entier nat non nul et un ens E a n elem ,on appel
>> involution de E toute bijection surE telle que fof =Id ouId designe l
>>application identique de E. obj du pb est l etude du nbr Tn d
>>involutions deE par la rech entre autre d un equival simple de Tn
>> CALCULER T1 T2 ,T3
>>COMMENT DEMARRER? merci
>
>Une permutation (i.e. bijection sur un ensemble fini) se décompose
>en cycles. Quelle doit être la forme de ces cycles pour que la
>permutation soit une involution ? Combien y a-t-il de manières
>différentes de placer de tels cycles dans E ?
Ca donne une formule exacte pour Tn, mais est-il simple d'en tirer une
expression asymptotique ?
On peut aussi calculer Tn+1 en fonction de Tn et Tn-1 et en déduire
une horrible équation différentielle satisfaite par la série génératrice
des Tn. Je ne sais pas reconnaître les équations différentielles résolubles
et les autres...
--
Dominique Bernardi, Théorie des Nombres
Institut de Mathématiques - Université Pierre et Marie Curie
4 place Jussieu - F75005 Paris Tel (33-1) 44275441
bern...@math.jussieu.fr
michel blois
etant donne un nbre entier naturel non nul et un ensemble E
a n elements ,on appelle involution de E toute bijection
sur E telle que f o f=Id ou Id designe l application
identique de E.L objectif du prob est l etude du nbre Tn d
involutions de E par la recherche entre autres d un
equivalent simple de Tn.
On suppose n>OU=3
je voudrais determiner en fct de T1 OU 1(<=)i(<=)n
_le nbre d involutions s de [1,n] telles que s(n)=n
_le nbre d involutions s de [1,n] telles que s(n)=k ou k
est un entier donne de [1,n-1]
demande de l aide svp (niveau maths sup);merci!
Patrice Gross
{réponse au message de michel blois à fr.sci.maths le 30-Oct-97 12:40:57}
>etant donne un nombre entier nat non nul et un ens E a n elem ,on appel
> involution de E toute bijection surE telle que fof =Id ouId designe l
>application identique de E. obj du pb est l etude du nbr Tn d
>involutions deE par la rech entre autre d un equival simple de Tn
Appelons i le nombre d'éléments a de E tels que pour l'involution f
f(a) = a.
Le nombre d'involutions possédant i éléments fixes est ainsi égal
au nombre de partitions possibles de l'ensemble des n-i éléments
en sous-ensembles de 2 éléments, égal à P_{n-i}.
Le nombre i pouvant varier de 0 à n, le nombre T_n est donc égal
à :
_n _n
T_n = > [C(i,n).P_{n-i}] = > [C(i,n).P_i]
¯0 ¯0
C(i,n) étant le nombre de combinaisons de i éléments choisis parmi n
(coefficient du binôme)
Il ne reste plus qu'à déterminer P_i, en remarquant que P_i = 0 si
i est impair (donc, poser i = 2k). Je te laisse terminer.
--
Patrice Gross
Création de fr.sci.cindyniques : clôture du scrutin le 25/11/1997
Envoi de l'AAV par E-Mail sur simple demande
Raphael Bomboy
michel blois <Michel...@wanadoo.fr> writes:
>
> etant donne un nombre entier nat non nul et un ens E a n elem ,on appel
> involution de E toute bijection surE telle que fof =Id ouId designe l
> application identique de E. obj du pb est l etude du nbr Tn d
> involutions deE par la rech entre autre d un equival simple de Tn
> CALCULER T1 T2 ,T3
> COMMENT DEMARRER? merci
>
Commencer par ecrire en francais, ou en anglais (ou en russe, etc...)
a la limite, mais dans une langue dont la syntaxe soit decriptable...
Raph.
-------------------------------------------------------------------------------
Raphael BOMBOY
bom...@desargues.univ-lyon1.fr
Julien Cassaigne
Dominique Bernardi écrit :
> Ca donne une formule exacte pour Tn, mais est-il simple d'en tirer une
> expression asymptotique ?
> On peut aussi calculer Tn+1 en fonction de Tn et Tn-1 et en déduire
> une horrible équation différentielle satisfaite par la série génératrice
> des Tn. Je ne sais pas reconnaître les équations différentielles résolubles
> et les autres...
Bon, maintenant que le temps a un peu passé on peut donner des détails.
Donc, une involution est une permutation dont les cycles sont de longueur
1 (points fixes) ou 2 (transpositions). Il est donc équivalent de compter
le nombre de partititions de {1,...,n} en parties à 1 ou 2 éléments.
À partir de là, il y a deux techniques : trouver une formule de
récurrence, et écrire la série génératrice. Je commence par la première
puisque les séries génératrices ne sont pas vraiment au programme de sup.
Supposons donc T(0) à T(n) connus, et calculons T(n+1). Il y a deux
possibilités pour une involution sur {1,...,n+1} : soit n+1 est un
point fixe, soit il est transposé avec un autre élément p. Dans le
premier cas, la restriction à {1,...,n} est une involution quelconque,
donc il y a T(n) possibilités; dans le second, il y a n façons de choisir
p, et T(n-1) façons de choisir la restriction à {1,...,n}-{p}. D'où
la relation de récurrence : T(n+1) = T(n) + n * T(n-1).
Pour obtenir la série génératrice, pas besoin de calcul. Il faut juste
se souvenir d'un principe : quand on travaille sur des objets indiscernables,
on utilise les séries génératrices ordinaires sum(T(n)*x^n,n=0..infini),
mais quand on travaille sur des objets étiquetés, ce qui est le cas
ici (l'ensemble {1,...,n}), on utilise les séries génératrices
exponentielles F(x)=sum(T(n)*x^n/n!,n=0..infini).
Ensuite, il n'y a qu'a appliquer les règles de construction.
Un point fixe, c'est un singleton, donc x; un cycle de longueur 2, c'est
une paire, donc x^2/2; un cycle de longueur 1 ou 2, c'est x+x^2/2;
et une assemblée de tels cycles, c'est exp(x+x^2/2).
Tout ça ne nous donne pas d'expression asymptotique... En fait,
ce n'est pas si facile que cela, c'est des calculs style preuve
de la formule de Stirling, bien taupinaux quoi. Un point de départ :
Si on pose v(n) = T(n)/T(n-1), la relation de récurrence devient :
v(n+1) = 1 + n/v(n). C'est tout de même un peu plus sympathique, non ?
Julien.
--
Julien Cassaigne cass...@iml.univ-mrs.fr
Institut de Mathématiques de Luminy (CNRS), Marseille, France
http://www.eleves.ens.fr:8080/home/cassaign/