Involutions, évaluation
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 l'ESCP 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
[small]Fête nationale de Jeanne d'Arc et du patriotisme, loi du 10 juillet 1920[/small]
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 l'ESCP 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
[small]Fête nationale de Jeanne d'Arc et du patriotisme, loi du 10 juillet 1920[/small]
Réponses
-
À l'attention des générations futures.
Ce message n'a recueilli aucune réponse :-(, 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) » : http://www.les-mathematiques.net/phorum/read.php?4,2132040,2137044#msg-2137044
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres