Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-25T09:23:22.816Z Has data issue: false hasContentIssue false

Some asymptotic methods in combinatorics

Published online by Cambridge University Press:  09 April 2009

J. M. Plotkin
Affiliation:
Michigan State UniversityEast Lansing 48824, USA
John Rosenthal
Affiliation:
Ithaca CollegeIthaca 14850, USA
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 〈fn0 be nonnegative real numbers with generating function f(x) = Σfnxn. Assume f(x) has the following properties: it has a finite nonzero radius of convergence x0 with its only singularity on the circle of convergence at x = x0 and f(x0) converges to y0; y = f(x) satisfies an analytic identity F(x, y) = 0 near (x0, y0); Fy(l) (x0, y0)= 0, 0 ≦ i < k and Fy(k) (x0, y0) ≠ 0. There are constants γ, a positive rational, and c such that fn~cx0−n n−(1 +ggr;). Furthermore, we show (i) in all cases how to determine γ and c from f(x) and (ii) in certain cases how to determine them from F(x, y).

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1979

References

Bender, E. A. (1974), ‘Asymptotic methods in enumeration’, Siam Review 16, 485515.CrossRefGoogle Scholar
Harary, F., Robinson, R. W. and Schwenk, A. J. (1975), ‘Twenty step algorithm for determining the asymptotic number of trees of various species’, J. Austral. Math. Soc. Ser. A 20, 483503.CrossRefGoogle Scholar
Hörmander, L. (1966), An introduction to complex analysis in several variables (Van Nostrand, Princeton).Google Scholar
Plotkin, J. M. and Rosenthal, J. (1979), ‘On the expected number of branches in analytic tableaux analyses in prepositional calculus’ (preprint).Google Scholar
Pólya, G. (1937), ‘Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen’, Acta Math. 68, 145254.CrossRefGoogle Scholar
Walker, R. J. (1950), Algebraic curves (Princeton University Press, Princeton).Google Scholar