Analytic methods in asymptotic enumeration (Q1917527)

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)].