# 3.   Combinatorial Parameters and Multivariate Generating Functions

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

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

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