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, show that the bivariate EGF with $u$ marking the number of leaves is the solution to $$T(z,u)=uz+z(e^{T(z,u)}-1).$$ Then show that the mean number of leaves in a random Cayley tree is asymptotic to $ne^{-1}$ and, more generally, that 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$.Web Exercises
III.1
(Exercise 5.13 in Analysis of Algorithms) What is the average number of 1 bits in a random bitstring of length $N$ having no 00?
III.2
(E. Neyman) Use the symbolic method and an OBGF to compute the average sum of the digits in a random ternary (base 3) number with $N$ digits. For $N=1$, the result is (0 + 1 + 2)/3 = 1. For $N=2$, with the nine possibilities 00, 01 , 02, 10,11, 12, 20, 21, 22, the result is (0 + 1 + 2 + 1 + 2 + 3 + 2 + 3 + 4)/9 = 2. Note: This is not the easiest way to solve this problem—the purpose of this question is to test your understanding of the technique.
III.3
(D. Mavrides) Derive an OBGF for the number of 1s in the set of compositions of an integer, and use it to compute the expected number of 1s in a randomly selected composition of $N$.
III.4
(M. Bahrani) A run in a bitstring is a maximal sequence of consecutive identical bits. For example, the string 11010100001 has 7 runs, with lengths 2, 1, 1, 1, 1, 4, 1 respectively. What is the average number of runs in a random binary string of length $N$? List the corresponding horizontal and vertical OBGFs. Is the distribution of the number of runs in binary strings concentrated?
III.5
(T. Ratigan) Derive a combinatorial construction leading to an equation involving the OBGF for the number of vertices of degree $d$ in a Catalan tree with $n$ node Solve the equation for $d=1$ and give an asymptotic estimate of the number of degree-1 nodes in a random $n$-node Catalan tree.
III.6
(M. Tyler) Define the unit $n$-hypercube to be the set of points $[0,1]^n \subset \mathbb{R}^n$. For example, the unit 0-hypercube is a point, and the unit 3-hypercube is the unit cube. Define a $k$-face of the unit $n$-hypercube to be a copy of the $k$-hypercube in the exterior of the $n$-hypercube. More formally, a $k$-face of the unit $n$-hypercube is a set of the form $\prod_{1\le i\le n}S_i$ where $S_i$ is either $\{0\}$, $\{1\}$, or $[0, 1]$ for each $i$ between $1$ and $n$ and there are exactly $k$ indices $i$ such that $S_i = [0, 1]$. Derive a combinatorial construction leading to an OBGF and an explicit formula for the number of $k$-faces in the unit $n$-hypercube. Use the OBGF to derive the expected value of the dimension a random face of the unit $n$-hypercube.
III.7
(F. Dong) Consider random mappings from {1,...,N} to {1,...k}. For $k>2$, show that the number of pre-images of even size is larger than the number of preimages of odd size in expectation.
III.8
(A. Alag) Give a ~-approximation for the average number of even terms in a random composition of $N$.