# 3.   Combinatorial Parameters and Multivariate Generating Functions

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

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