Analytic methods in asymptotic enumeration

DOI10.1016/0012-365X(95)00139-NMaRDI QIDQ1917527zbMATH OpenFDO

Publication date 25 November 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00139-N

asymptotic enumeration binary trees degree sequence generating functions Haiman-admissible functions random permutation saddle point method set partition

Mathematics Subject Classification ID

Asymptotic enumeration (05A16)

Review text

The paper discusses successes and failures of analytic techniques in asymptotic enumeration. The paper shows problems from asymptotic enumeration, when standard analytic techniques work nicely, and the user does not have to go through the pains of the saddle point method (Haiman-admissible functions). Asymptotic enumeration using generating functions with increasing number of variables is inherently more complicated than asymptotic enumeration using single variable generating functions. However, McKay and Wormald managed to obtain an asymptotic formula for the number of labeled simple graphs by the degree sequence, if all degrees are properly separated from 0 and \(n\). For the length of the maximum increasing subsequence of a random permutation of \(n\) elements, the asymptotics \(2\sqrt n\) has been known, but no further asymptotic expansion is known. Odlyzko et al. have used asymptotics of multivariate integrals to find asymptotics for the probability that the random permutation has no increasing subequence longer than \(k\) for \(k= o(\sqrt n)\). Such estimate has not been obtained yet for \(k= c\sqrt n\). Even single variable generating functions can present challenges, when the generating function does not have an explicit form (enumeration of binary trees by height or set partition into sets of different sizes). The paper is not an introduction to asymptotic enumeration, for this purpose see the author [Asymptotic enumeration methods, in: R. L. Graham (ed.) et al.: Handbook of combinatorics, 1063-1229 (1995; Zbl 0845.05005)].

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Analytic methods in asymptotic enumeration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917527)