Section 7.1.3: Bitwise Tricks and Techniques

Exercise 60. [HM28] Given a random permutation of ${0, 1, \ldots, 2n-1}$, let $p_{nk}$ be the probability that there are $2^k$ ways to set the crossbars in the first and last columns of the permutation network $P(2n)$ when realizing this permutation. In other words, $p_{nk}$ is the probability that the associated graph has $k$ cycles (see (75)). What is the generating function $\sum_{k \ge 0} p_{nk} z^k$? What are the mean and variance of $2^k$?

Verified: no
Solve time: 4m02s

---

Let $K$ be the number of cycles in the graph $G = M_1 \cup M_2$, where $M_1$ is a fixed perfect matching on ${0,1,\dots,2n-1}$ and $M_2$ is a uniformly random perfect matching.

We correct the argument from the start by identifying the exact induced probability law on cycle structures.

1. From two matchings to a permutation

View each perfect matching as a fixed-point-free involution on $V={0,1,\dots,2n-1}$. Let $M_1$ be fixed and $M_2$ random.

Define the permutation

$$ \pi = M_2 \circ M_1. $$

Each vertex has one $M_1$-edge and one $M_2$-edge, so alternating traversal in $G$ follows the orbit structure of $\pi$. Each cycle of $G$ corresponds exactly to one cycle of $\pi$. Hence

$$ K = c(\pi), $$

the number of cycles of $\pi$.

2. Exact distribution of $\pi$

A perfect matching $M_2$ can be recovered from $\pi$ and $M_1$, but the map is not uniform over permutations. The correct counting is:

For a permutation $\pi$ with $k$ cycles,

$$ #{M_2 : M_2 \circ M_1 = \pi} = 2^k. $$

Thus

$$ \mathbb{P}(\pi) \propto 2^{c(\pi)}. $$

This is the Ewens sampling formula on $S_n$ with parameter $\theta=2$, after reducing the block structure induced by $M_1$.

Therefore the induced distribution of $\pi$ on $S_n$ is

$$ \mathbb{P}(\pi) = \frac{2^{c(\pi)}}{2(3)\cdots(n+1)}. $$

The normalization follows from the identity

$$ \sum_{\pi \in S_n} 2^{c(\pi)} = 2(3)\cdots(n+1). $$

Hence the probability that $K=k$ is

$$ p_{nk} = \frac{c(n,k),2^k}{2(3)\cdots(n+1)}, $$

where $c(n,k)$ are the unsigned Stirling numbers of the first kind.

3. Probability generating function

Compute

$$ \sum_{k\ge 0} p_{nk} z^k = \frac{1}{2(3)\cdots(n+1)} \sum_{k\ge 0} c(n,k) (2z)^k. $$

Using the standard identity

$$ \sum_{k\ge 0} c(n,k)x^k = x(x+1)\cdots(x+n-1), $$

with $x=2z$, we obtain

$$ \sum_{k\ge 0} p_{nk} z^k = \frac{(2z)(2z+1)\cdots(2z+n-1)}{2\cdot 3\cdots(n+1)}. $$

This is the correct generating function.

4. Moments of $K$

From the Ewens($\theta=2$) structure, we can compute factorial-moment type expressions directly.

Mean of $K$

For Ewens($\theta$),

$$ \mathbb{E}[K] = \theta H_n. $$

Hence

$$ \mathbb{E}[K] = 2H_n. $$

5. Mean of $2^K$

Compute directly from the generating function:

$$ \mathbb{E}[2^K] = \sum_k p_{nk} 2^k = \frac{(4)(5)\cdots(n+3)}{2\cdot 3\cdots(n+1)}. $$

Rewrite numerator and denominator:

$$ (4)(5)\cdots(n+3) = \frac{(n+3)!}{3!}, \quad 2\cdot 3\cdots(n+1) = \frac{(n+1)!}{1}. $$

Thus

$$ \mathbb{E}[2^K] = \frac{(n+3)!}{6 (n+1)!} = \frac{(n+3)(n+2)}{6}. $$

6. Second moment and variance of $2^K$

Similarly,

$$ \mathbb{E}[4^K] = \frac{(8)(9)\cdots(n+7)}{2\cdot 3\cdots(n+1)}. $$

Convert products:

$$ (8)(9)\cdots(n+7) = \frac{(n+7)!}{7!}, \quad 2\cdot 3\cdots(n+1) = (n+1)!. $$

So

$$ \mathbb{E}[4^K] = \frac{(n+7)!}{5040 (n+1)!} = \frac{(n+7)(n+6)(n+5)(n+4)}{5040}. $$

Therefore

$$ \mathrm{Var}(2^K) = \frac{(n+7)(n+6)(n+5)(n+4)}{5040}

• \left(\frac{(n+3)(n+2)}{6}\right)^2. $$

Final answers

Generating function

$$ \sum_{k \ge 0} p_{nk} z^k

\frac{(2z)(2z+1)\cdots(2z+n-1)}{2\cdot 3\cdots(n+1)}. $$

Mean

$$ \mathbb{E}[2^K] = \frac{(n+3)(n+2)}{6}. $$

Variance

$$ \mathrm{Var}(2^K)

\frac{(n+7)(n+6)(n+5)(n+4)}{5040}

\left(\frac{(n+3)(n+2)}{6}\right)^2. $$

All results now follow from the correct Ewens($\theta=2$) weighting induced by random perfect matchings, rather than an incorrect uniform-permutation assumption.