3.   Combinatorial Parameters and Multivariate Generating Functions

III.1 An introduction to bivariate generating functions (BGFs)

III.2 Bivariate generating functions and probability distributions

III.3 Inherited parameters and ordinary MGFs

III.4 Inherited parameters and exponential MGFs

III.5 Recursive parameters

III.6 Complete generating functions and discrete models

III.7 Additional constructions

III.8 Extremal parameters

III.9 Perspective

Selected Exercises

Note III.17

Leaves and node-degree profile in Cayley trees. For Cayley trees, the bivariate EGF with $u$ marking the number of leaves is the solution to $$T(z,u)=uz+z(e^{T(z,u)}-1).$$ (By Lagrange inversion, the distribution is expressible in terms of Stirling partition numbers.) The mean number of leaves in a random Cayley tree is asymptotic to $ne^{-1}$. More generally, the mean number of nodes of outdegree $k$ in a random Cayley tree of size~$n$ is asymptotic to $$n\cdot e^{-1}\, {1\over k!}.$$ Degrees are thus approximately described by a Poisson law of rate 1.

Note III.21

After Bhaskara Acharya (circa 1150 AD). Consider all the numbers formed in decimal with digit 1 used once, with digit 2 used twice, ..., with digit 9 used nine times. Such numbers all have 45 digits. Compute their sum $S$ and discover, much to your amazement that $S$ equals 45875559600006153219084769286399999999999999954124440399993846780915230713600000. This number has a long run of nines (and further nines are hidden!). Is there a simple explanation? This exercise is inspired by the Indian mathematician Bhaskara Acharya who discovered multinomial coefficients near 1150 AD.

Selected Experiments

Program III.1

Write a program that generates 1000 random permutations of size $N$ for $N$ = $10^3$, $10^4$, ... (going as far as you can) and plots the distribution of the number of cycles, validating that the mean is concentrated at $H_N$.