no. 9-10
Combinatoire
On the exponential generating function of labelled trees
[Sur la série génératrice des arbres étiquetés]
Bostan, Alin1 ; Jiménez-Pastor, Antonio2 
1 Inria, 1 rue Honoré d’Estienne d’Orves 91120 Palaiseau, France
2 Johannes Kepler University Linz, Doctoral Program Computational Mathematics, DK15
Comptes Rendus. Mathématique, Tome 358 (2020) no. 9-10, pp. 1005-1009.

Nous montrons que la série génératrice des arbres étiquetés n’est pas D ∞ -finie.

We show that the generating function of labelled trees is not D ∞ -finite.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/crmath.108
Classification : 05A15, 12H05, 34A34
Bostan, Alin 1 ; Jiménez-Pastor, Antonio 2

1 Inria, 1 rue Honoré d’Estienne d’Orves 91120 Palaiseau, France
2 Johannes Kepler University Linz, Doctoral Program Computational Mathematics, DK15 
@article{CRMATH_2020__358_9-10_1005_0,
     author = {Bostan, Alin and Jim\'enez-Pastor, Antonio},
     title = {On the exponential generating function  of labelled trees},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1005--1009},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {358},
     number = {9-10},
     year = {2020},
     doi = {10.5802/crmath.108},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/crmath.108/}
}
TY  - JOUR
AU  - Bostan, Alin
AU  - Jiménez-Pastor, Antonio
TI  - On the exponential generating function  of labelled trees
JO  - Comptes Rendus. Mathématique
PY  - 2020
SP  - 1005
EP  - 1009
VL  - 358
IS  - 9-10
PB  - Académie des sciences, Paris
UR  - http://www.numdam.org/articles/10.5802/crmath.108/
DO  - 10.5802/crmath.108
LA  - en
ID  - CRMATH_2020__358_9-10_1005_0
ER  - 
%0 Journal Article
%A Bostan, Alin
%A Jiménez-Pastor, Antonio
%T On the exponential generating function  of labelled trees
%J Comptes Rendus. Mathématique
%D 2020
%P 1005-1009
%V 358
%N 9-10
%I Académie des sciences, Paris
%U http://www.numdam.org/articles/10.5802/crmath.108/
%R 10.5802/crmath.108
%G en
%F CRMATH_2020__358_9-10_1005_0
Bostan, Alin; Jiménez-Pastor, Antonio. On the exponential generating function  of labelled trees. Comptes Rendus. Mathématique, Tome 358 (2020) no. 9-10, pp. 1005-1009. doi : 10.5802/crmath.108. http://www.numdam.org/articles/10.5802/crmath.108/

[1] Aigner, Martin; Ziegler, Günter M. Proofs from The Book, Springer, 2010, viii+274 pages | DOI | Zbl

[2] Andrews, George E.; Askey, Richard; Roy, Ranjan Special functions, Encyclopedia of Mathematics and Its Applications, 71, Cambridge University Press, 1999, xvi+664 pages | DOI | MR | Zbl

[3] Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J. Graph theory. 1736–1936, Clarendon Press, 1986, xii+239 pages | Zbl

[4] Borchardt, Carl W. Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante, J. Reine Angew. Math., Volume 57 (1860), pp. 111-121 | DOI | MR

[5] Bostan, A.; Di Vizio, L.; Raschel, K. Differential transcendence of Bell numbers and relatives — a Galois theoretic approach, 2020 (In preparation)

[6] Cayley, Aarthur A theorem on trees, Q. J. Math, Volume 23 (1889), pp. 376-378

[7] Corless, Robert M.; Gonnet, Gaston H.; Hare, David E. G.; Jeffrey, David J.; Knuth, Donald E. On the Lambert W function, Adv. Comput. Math., Volume 5 (1996) no. 4, pp. 329-359 | DOI | MR | Zbl

[8] Flajolet, Philippe; Gerhold, Stefan; Salvy, Bruno On the non-holonomic character of logarithms, powers, and the nth prime function, Electron. J. Comb., Volume 11 (2005) no. 2, A2, 16 pages | Zbl

[9] Flajolet, Philippe; Sedgewick, Robert Analytic combinatorics, Cambridge University Press, 2009, xiv+810 pages | DOI | Zbl

[10] Gerhold, Stefan On some non-holonomic sequences, Electron. J. Comb., Volume 11 (2004) no. 1, 87, 8 pages | MR | Zbl

[11] van der Hoeven, Joris Computing with D-algebraic power series, Appl. Algebra Eng. Commun. Comput., Volume 30 (2019) no. 1, pp. 17-49 | DOI | MR | Zbl

[12] Jensen, Johan L. W. V. Sur une identité d’Abel et sur d’autres formules analogues, Acta Math., Volume 26 (1902) no. 1, pp. 307-318 | DOI | Zbl

[13] Jiménez-Pastor, Antonio; Pillwein, Veronika A computable extension for D-finite functions: DD-finite functions, J. Symb. Comput., Volume 94 (2019), pp. 90-104 | DOI | MR | Zbl

[14] Jiménez-Pastor, Antonio; Pillwein, Veronika; Singer, Michael F. Some structural results on D n -finite functions, Adv. Appl. Math., Volume 117 (2020), 102027, 29 pages | DOI | MR | Zbl

[15] Klazar, Martin Bell numbers, their relatives, and algebraic differential equations, J. Comb. Theory, Ser. A, Volume 102 (2003) no. 1, pp. 63-87 | DOI | MR | Zbl

[16] Lovász, László Combinatorial problems and exercises, North-Holland, 1993, 635 pages | Zbl

[17] Mian, Abdul M.; Chowla, Sarvadaman The differential equations satisfied by certain functions, J. Indian Math. Soc., New Ser., Volume 8 (1944), pp. 27-28 | MR | Zbl

[18] Noordman, Marc P.; van der Put, Marius; Top, Jaap Combinatorial Autonomous first order differential equations, 2019 (preprint, https://arxiv.org/abs/1904.08152v1)

[19] Pak, Igor Complexity problems in enumerative combinatorics, Proceedings of the International Congress of Mathematicians — Rio de Janeiro 2018. Vol. IV. Invited lectures, World Scientific (2018), pp. 3153-3180 | Zbl

[20] Rosenlicht, Maxwell The nonminimality of the differential closure, Pac. J. Math., Volume 52 (1974), pp. 529-537 | DOI | MR | Zbl

[21] Rubel, Lee A. A survey of transcendentally transcendental functions, Am. Math. Mon., Volume 96 (1989) no. 9, pp. 777-788 | DOI | MR | Zbl

[22] Singer, Michael F. Algebraic relations among solutions of linear differential equations, Trans. Am. Math. Soc., Volume 295 (1986) no. 2, pp. 753-763 | DOI | MR | Zbl

[23] Stanley, Richard P. Differentiably finite power series, Eur. J. Comb., Volume 1 (1980) no. 2, pp. 175-188 | DOI | MR | Zbl

Cité par Sources :