×

zbMATH — the first resource for mathematics

Asymptotic distributions and a multivariate Darboux method in enumeration problems. (English) Zbl 0801.60016
Summary: Let \(c(x,z) = \sum c_{nk} x^ nz^ k\) \((c_{nk} \geq 0)\) be a bivariate generating function satisfying a functional equation \(c = G(c,x,z)\). By using a central limit theorem of Bender it is shown that discrete random variables \(X_ n\) with \(P[X_ n=k] = c_{nk}/(\sum c_{ni})\) are asymptotically normal with mean \(\mu_ n \sim \mu n\) and variance \(\sigma^ 2_ n \sim \sigma^ 2n\). Furthermore a bivariate asymptotic expansion for the coefficients \(c_{nk}\) can be obtained by two different methods. After some applications to tree enumeration problems a multivariate Darboux-method is formulated.

MSC:
60F05 Central limit and other weak theorems
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bender, E. A.: Central and local limit theorems applied to asymptotic enumeration. J. combin theory ser. A 15, 91-111 (1973) · Zbl 0242.05006
[2] Bender, E. A.; Richmond, L. B.: Central and local limit theorems applied to asymptotic enumeration II: Multivariate generating functions. J. combin. Theory ser. A 34, 255-265 (1983) · Zbl 0511.05003
[3] Drmota, M.: On generalized Fibonacci numbers of trees. Applications of Fibonacci numbers 3, 63-76 (1990) · Zbl 0718.05057
[4] Flajolet, Ph; Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete math. 3, 216-240 (1990) · Zbl 0712.05004
[5] Kirschenhofer, P.: On the height of leaves in binary trees. J. combin. Inform. system sci. 8, 44-60 (1983) · Zbl 0629.05031
[6] Kirschenhofer, P.: On the average shape of simply generated families of trees. J. graph theory 7, 311-323 (1983) · Zbl 0489.05022
[7] Kirschenhofer, P.: A tree enumeration problem involving the asymptotics of the diagonals of a power series. Ann. discrete math. 33, 157-170 (1987) · Zbl 0633.05035
[8] Kirschenhofer, P.; Prodinger, H.; Tichy, R. F.: Fibonacci numbers of graphs III: Planted plane trees. Fibonacci numbers and their applications, 105-120 (1986) · Zbl 0597.05034
[9] Meir, A.; Moon, J. W.: On maximal independent sets of nodes in trees. J. graph theory 12, 265-283 (1988) · Zbl 0655.05039
[10] Meir, A.; Moon, J. W.: On an asymptotic method in enumeration. J. combin. Theory 51, 77-89 (1989) · Zbl 0683.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.