Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-25T07:05:02.205Z Has data issue: false hasContentIssue false
  • English
  • Français

How to obtain an asymptotic expansion of a sequence from an analytic identity satisfied by its generating function

Part of: Combinatorics Graph theory

Published online by Cambridge University Press:  09 April 2009

J. M. Plotkin  and
John W. Rosenthal
J. M. Plotkin
Affiliation:
Department of Mathematics, Michigan State University, East Lansing, Michigan, 48824
John W. Rosenthal
Affiliation:
Department of Mathematics and Computer Science, Ithaca College, Ithaca, New York 14850
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let fn be a sequence of nonnegative integers and let f(x): = Σn≥0 fn xn be its generating function. Assume f(x) has the following properties: it has radius of convergence r, 0 < r < 1, with its only singualarity on the circle of convergence at x = r and f(r) = s; y = f(x) satisfies an analytic identity F(x, y) = 0 near (r, s); for some k ≥ 2 F0.j = 0, 0 ≤ j < k, F0.k ≠ 0 where Fi is the value at (r, s) of the ith partial derivative with respect to x and the jth partial derivative with respect to y of F. These assumptions form the basis of what we call the typical and general cases. In both cases we show how to obtain an asymptotic expansion of fn. We apply our technique to produce several terms in the asymptotic expansion of combinatorial sequences for which previously only the first term was known.

Keywords

Generating functionanalytic identityWeierstrass Preparation Theoremfractional power seriesasymptotic expansiontreesnumber of trees.

MSC classification

Secondary: 05A15: Exact enumeration problems, generating functions 05C30: Enumeration in graph theory
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 56 , Issue 1 , February 1994 , pp. 131 - 143
Copyright
Copyright © Australian Mathematical Society 1994

References

[1]Bender, E. A., ‘Asymptotic methods in enumeration’, Siam Rev. 16 (1974), 485–515.CrossRefGoogle Scholar
[2]Harary, F. and Prins, G., ‘The number of homeomorphically irreducible trees and other species’, Acta Math. 101 (1959), 141–162.CrossRefGoogle Scholar
[3]Harary, F., Robinson, R. W. and Schwenk, A. J., ‘Twenty step algorithm for determining the asymptotic number of trees of various species’, J. Austral. Math. Soc. (Series A) 20 (1975), 483–503.CrossRefGoogle Scholar
[4]Hormander, L., An introduction to complex analysis in several variables (Van Nostrand, Princeton, 1966).Google Scholar
[5]Otter, R., ‘The number of trees’, Ann. of Math. 49 (1948), 583–599.CrossRefGoogle Scholar
[6]Plotkin, J. M. and Rosenthal, J. W., ‘Some asymptotic methods in combinatorics’, J. Austral. Math. Soc. (Series A) 28 (1979), 452–460.CrossRefGoogle Scholar
[7]Plotkin, J. M. and Rosenthal, J. W., ‘The expected complexity of analytic tableaux analyses in propositional calculus’, Notre Dame J. of Formal Logic 23 (1982), 409–426.CrossRefGoogle Scholar
[8]Pólya, G., ‘Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und Chemische Verebindungen’, Acta Math. 86 (1937), 145–254.CrossRefGoogle Scholar
[9]Szegö, G., Orthogonal Polynomials, Colloquium Publications 23, revised edition (Amer. Math. Soc., Providence, 1959).Google Scholar
[10]Walker, R. J., Algebraic curves (Princeton University Press, Providence, 1978).CrossRefGoogle Scholar