Bruno Salvy
Abstract
We describe the GFUN package which contains functions for manipulating sequences, linear recurrences, or differential equations and generating functions of various types. This article is intended both as an elementary introduction to the subject and as a reference manual for the package.
- BERGERON, F. AND PLOUFFE, S. 1992. Computing the generating function of a series given its first terms. J. Exp. Math. 1, 4, 308 312,Google Scholar
- BOREL, E. 1901. Leqons sur les s~ries divergentes. In Collectwn de monograph~es sur la thdorie des fonctions, pubh& sous la &rectzon de M. Y~mde Borel. Gauthiers-Villars, Pans. Second ed. 1928 Reprinted by J. Gabay, 1988.Google Scholar
- CANDELPERGHER, B. 1989. Une introduction h la r~surgence. Gazette des Mathdmaticiens 42 (Oct.), 36-64.Google Scholar
- CHUDNOVSKY, D. V. AND CHUDNOVSKY, G.V. 1987. On expansion of algebraic functions in power and Puiseux series, II. J. Complex. 3, 1, 1-25. Google Scholar
- CHUDNOVSKY, n. V. AND CHUDNOVSKY, G.V. 1986. On expansion of algebraic functions in power and Puiseux series, I. J. Complex. 2, 4, 271-294. Google Scholar
- COMTET, L. 1974. Advanced Combinatorics. Reidel, Dordrecht, The Netherlands.Google Scholar
- COMTET, L. 1964. Calcul pratique des coefficients de Taylor d'une fonction alg~brique. L'Enseignement Mathdmatique 10,267-270.Google Scholar
- DELEST, M.-P. AND VIENNOT, G. 1984. Algebraic languages and polyominoes enumeration. Theor. Comput. Sct. 34, 1-2, 169-206.Google Scholar
- DUVAL, D. 1987. Diverses questions relatives au calcul formel avec des nombres alg~briques. Doctorat d'l~tat, Universit~ scientifique, technologique et m~dicale de Grenoble.Google Scholar
- GOURDON, X. AND SALVY, B. 1992. Asymptotics of linear recurrences with rational coefficients. Tech. Rep., INRIA, Le Chesnay Cedex, France.Google Scholar
- GRAHAM, R., KNUTH, D., AND PATASHNIK, O. 1989. Concrete Mathematics. Addison Wesley, Reading, Mass. Google Scholar
- GUTTMANN, A. J. AND ENTING, I.G. 1988. The number of convex polygons on the square and honeycomb lattices. J. Phys. A 21,467-474.Google Scholar
- LIPSHITZ, L. 1989. D-finite power series. J. Alg. 122, 2, 353-373.Google Scholar
- LODAY-RICHAUD, M. 1990. Introduction ~ la multisommabilit6. Gazette des Math~matie~ens 44, 41-63.Google Scholar
- MALGRANGE, B. AND RAMIS, J.-P, 1992. Fonctions mu}tisommables. Annales de l'lnstitut Fourier 42, 1-2, 353-368.Google Scholar
- SLOANE, N. J. A, 1973. A Handbook of Integer Sequences. Academic Press, New York.Google Scholar
- STANLEY, R.P. 1980. Differentiably finite power series. Eur. J. Combinatorics 1,175-188.Google Scholar
- THOMANN, J. 1990. Resommation des s6ries formelles. Solutions d'~quations diff~rentielles lin6aires du second ordre dans }e champ complexe au voisinage de singularities irr~guli~res. Numer. Math. 58, 5, 503-535.Google Scholar
- ULMER, F. 1991. On algebraic solutions of linear differential equations with primitive unimodular Galois group. In Algebraic Algortthms and Error Correcting Codes. Lecture Notes in Computer Science, vol. 307. Springer-Verlag, Berlin, 446-455. Google Scholar
- WASOW, W. 1987. Asymptotic Expansions for Ordinary Differenttal Equattons. Dover, New York, 1965.Google Scholar
- WmF, H.S. 1990. Generatingfuncttonology. Academic Press, New York.Google Scholar
- ZEILBERGER, n. 1992. A proof of Julian West's conjecture that the number of two-stack-sorta-ble permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!). Dtsc. Math. 102, 1, 85 93. Google Scholar
- ZEmBERGER, D. 1990. A holonomlc systems approach to special functions identities. J. Cornput. Appl. Math. 32, 3, 321-368. Google Scholar
Index Terms
- GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable
Recommendations
D-finiteness: algorithms and applications
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computationDifferentially finite series are solutions of linear differential equations with polynomial coefficients. P-recursive sequences are solutions of linear recurrences with polynomial coefficients. Corresponding notions are obtained by replacing classical ...
Fast algorithms for polynomial solutions of linear differential equations
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computationWe investigate polynomial solutions of homogeneous linear differential equations with coefficients that are polynomials with integer coefficients. The problems we consider are the existence of nonzero polynomial solutions, the determination of the ...
Low complexity algorithms for linear recurrences
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computationWe consider two kinds of problems: the computation of polynomial and rational solutions of linear recurrences with coefficients that are polynomials with integer coefficients; indefinite and definite summation of sequences that are hypergeometric over ...
Reviews
Peter Paule
According to Wilf [1], “a generating function is a clothesline on which we hang up a sequence of numbers for display.” The package GFUN has been designed for assisting in the use of this classic tool. The paper provides a clear description, together with illustrative examples, of the various GFUN procedures for the discovery and manipulation of generating functions. For instance, given the first terms of a sequence as input, GFUN can conjecture the next terms by guessing (or computing, if the type is specified) the generating function. Algorithmically, this is based on an indeterminate coefficient method. An electronic prototype “superseeker” using GFUN procedures can find about 22 percent of the generating functions for the approximately 4500 sequences contained in Sloane's book [2] automatically without error. In cases where the result cannot be presented in closed form, the output is a differential or algebraic equation satisfied by the generating function. Holonomic functions (or holonomic sequences), being defined as solutions of an ordinary linear differential (or recurrence) equation with polynomial coefficients, satisfy nice closure properties. For instance, the product of two holonomic functions is again holonomic, and the product of two generating functions is generating. GFUN computes the differential equation of the product from the defining differential equations of the factors. The package provides various procedures of this kind, and similar procedures for recurrence and algebraic equations, which can be used for computing, experimenting, guessing, proving, or finding. One can hardly overestimate the practical value of the GFUN package. Besides being of great help in passing certain so-called intelligence tests, GFUN is an indispensable tool for anyone who encounters generating functions and number sequences in his or her daily life.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments