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