Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
170 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Involutions, évaluation

Envoyé par Chaurien 
Involutions, évaluation
il y a cinq années
avatar
Bonjour.
Pour $n \in \mathbb{N}$ un $n$-ensemble est un ensemble à $n$ éléments.
Soit $t_n$ le nombre d'applications involutives d'un $n$-ensemble dans lui-même. C'est la suite A000085 dans l'OEIS.
Ces nombres $t_n$ satisfont à une récurrence linéaire des plus simples : $t_n=t_{n-1}+(n-1)t_{n-2}$.
Ils s'expriment comme : $\displaystyle t_{n}=\underset{k=0}{\overset{\left\lfloor \frac{n}{2}\right\rfloor }{\sum }}\frac{n!}{2^{k}k!(n-2k)!}$.
Leur FGE (fonction génératrice exponentielle) est : $\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}t_{n}\frac{x^{n}}{n!}=e^{x+\frac{x^{2}}{2}}$

Je m'intéresse aujourd'hui à leur évaluation asymptotique, qui est : $t_{n}\sim \frac{1}{\sqrt{2}}n^{\frac{n}{2}}e^{-\frac{n}{2}+\sqrt{n}-\frac{1}{4}}$ quand $n \rightarrow +\infty $.
Pour démontrer cette évaluation, j'ai trois sources :
- Knuth, The Art of computer programming, Vol. 3 ;
- Flajolet, Sedgewick, Analytic Combinatorics ;
- Wilf, generatingfunctionology.
Je trouve plutôt compliquées les méthodes proposées, et même douteuse dans Knuth.
Il y a une quatrième référence, c'est le problème de HEC 1993, qui exprime $t_n$ comme la valeur au point 1 d'un polynôme façon Hermite, et fait prouver force encadrements. Là c'est bien élémentaire mais long.

Il est possible que cette question soit intrinsèquement compliquée, je sais bien que ça arrive, mais je voudrais savoir si vous n'auriez pas autre chose qui permette de simplifier tout ça.

Bonne et belle journée. Bien cordialement.
F. Ch.
08/05/2016
Fête nationale de Jeanne d'Arc et du patriotisme, loi du 10 juillet 1920
Re: Involutions, évaluation
il y a quatre mois
avatar
À l'attention des générations futures.
Ce message n'a recueilli aucune réponse sad smiley, mais ceux qui s'intéressent aux propriétés du nombre $T_n$ d'applications involutives d'un $n$-ensemble pourront se reporter au fil « Suites en U(n+2) = U(n+1) + (n+1)U(n) » : [www.les-mathematiques.net]
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 692, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page