# ºtÁ¿¤½§i

### ·s»D¼ÐÃD¡G¡@( 2016-11-07 )

ºtÁ¿¥DÃD¡GFrom algebraic to differential-algebraic functions in combinatorics

¥DÁ¿¤H¡GCyril Banderier ³Õ¤h (CNRS, University of Paris Nord)

ºtÁ¿¤é´Á¡G2016¦~11¤ë22¤é(¬P´Á¤G) ¤U¤È2:20 ¡V3:20

ºtÁ¿¦aÂI¡G(¥ú´_®Õ°Ï) ¬ì¾Ç¤@À]223«Ç

¯ù·|®É¶¡¡G·í¤Ñ¤U¤È3:20 (¬ì¾Ç¤@À]205«Ç)

ºKn¤º®e¡G

Abstract. Asymptotics of recurrences is the key to get the typical properties of combinatorial structures, and thus the complexity of many algorithms relying on these structures. The associated generating function often follows a linear differential equation: we are here in the so-called "D-finite" world. For the matters of asymptotics, this case of linear recurrences (with polynomial coefficients) is well covered by the "Analytic Combinatorics" book of Flajolet and Sedgewick (though the computations of constants is still a challenge, related to the theory of Kontsevich-Zagier periods and evaluation of G-functions and E-functions). At the border of this D-finite world, lies "algebraic-differential functions". The terminology is not yet fixed and similar terms are used, up to a permutation, by several authors: let dz^m be the m-th derivative of F(z), the function is said "algebraic-differential" if there a exists a polynomial P such that P(z,F,F',..., dz^m F)=0. For all these worlds, having some positive (integer) coefficients leads to some strong constraints on the asymptotics (these is now well understood for algebraic function), and we try to see what happens in a more general setting.

We will give examples of such functions (motivated by some combinatorial problems), and show how a symbolic combinatorics approach can help for automatic asymptotics of their coefficients, and some open related open questions/challenges for computer algebra (joint works with Michael Drmota and Hsien-Kuei Hwang)