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$.