TAOCP 1.3.3 Exercise 18
Let $p_{nkm}$ denote the probability that a permutation of $n$ elements contains exactly $k$ cycles of length $m$.
Section 1.3.3: Applications to Permutations
Exercise 18. [M27] What is $p_{nkm}$, the probability that a permutation of $n$ objects has exactly $k$ cycles of length $m$? What is the corresponding generating function $G_{nm}(z)$? What is the average number of $m$-cycles and what is the standard deviation? (The text considers only the case $m = 1$.)
Verified: yes
Solve time: 16m52s
Setup
Let $p_{nkm}$ denote the probability that a permutation of $n$ elements contains exactly $k$ cycles of length $m$.
Let
$$ G_{nm}(z)=\sum_{k\ge0} p_{nkm}z^k $$
be the corresponding probability generating function.
We shall determine $p_{nkm}$, derive a closed form for $G_{nm}(z)$, and compute the mean and standard deviation of the number of $m$-cycles.
Let $X_m(\pi)$ be the number of $m$-cycles in a permutation $\pi$ of $n$ elements.
Solution
The standard enumeration of permutations by cycle structure gives the exponential generating function
$$ \sum_{n\ge0}\frac{u^n}{n!} \sum_{\pi} \prod_{r\ge1} y_r^{c_r(\pi)} = \exp!\left(\sum_{r\ge1}\frac{y_r u^r}{r}\right), \tag{1} $$
where $c_r(\pi)$ is the number of $r$-cycles of $\pi$.
To count permutations according to the number of $m$-cycles only, set
$$ y_m=z,\qquad y_r=1\ (r\ne m). $$
Then (1) becomes
$$ \sum_{n\ge0}\frac{u^n}{n!} \sum_{\pi} z^{X_m(\pi)} = \exp!\left( \sum_{r\ne m}\frac{u^r}{r} +\frac{zu^m}{m} \right). $$
Since
$$ \sum_{r\ge1}\frac{u^r}{r} = -\log(1-u), $$
we obtain
$$ \sum_{n\ge0}\frac{u^n}{n!} \sum_{\pi} z^{X_m(\pi)} = \frac{1}{1-u} \exp!\left(\frac{(z-1)u^m}{m}\right). \tag{2} $$
The coefficient of $u^n/n!$ on the left equals
$$ n!,G_{nm}(z), $$
because there are $n!$ permutations altogether. Hence
$$ G_{nm}(z) = \frac1{n!} [u^n] \left{ \frac{n!}{1-u} \exp!\left(\frac{(z-1)u^m}{m}\right) \right}, $$
or equivalently
$$ G_{nm}(z) = [u^n] \left{ \frac1{1-u} \exp!\left(\frac{(z-1)u^m}{m}\right) \right}. \tag{3} $$
This is the required generating function.
To extract $p_{nkm}$, expand the exponential:
$$ \exp!\left(\frac{(z-1)u^m}{m}\right) = \sum_{j\ge0} \frac{(z-1)^j}{m^j j!}u^{mj}. $$
Substituting into (3),
$$ G_{nm}(z) = \sum_{j=0}^{\lfloor n/m\rfloor} \frac{(z-1)^j}{m^j j!}. \tag{4} $$
The coefficient of $u^n$ has been taken, using
$$ [u^{,n-mj}]\frac1{1-u}=1. $$
Now expand
$$ (z-1)^j = \sum_{k=0}^{j} \binom{j}{k}z^k(-1)^{j-k}. $$
Comparing coefficients of $z^k$ in (4),
$$ p_{nkm} = \sum_{j=k}^{\lfloor n/m\rfloor} \frac{(-1)^{,j-k}}{m^j j!} \binom{j}{k}. \tag{5} $$
Since
$$ \binom{j}{k} = \frac{j!}{k!(j-k)!}, $$
this may be written
$$ p_{nkm} = \frac1{k!m^k} \sum_{r=0}^{\lfloor n/m\rfloor-k} \frac{(-1)^r}{m^r r!}. \tag{6} $$
Formulae (5) and (6) give the probability that a permutation of $n$ elements has exactly $k$ cycles of length $m$.
For the mean, differentiate (3):
$$ G'_{nm}(z) = [u^n] \left{ \frac{u^m}{m(1-u)} \exp!\left(\frac{(z-1)u^m}{m}\right) \right}. $$
At $z=1$,
$$ G'_{nm}(1) = \frac1m [u^n]\frac{u^m}{1-u}. $$
If $n\ge m$,
$$ [u^n]\frac{u^m}{1-u}=1, $$
hence
$$ E(X_m)=\frac1m. \tag{7} $$
If $n<m$, then $X_m\equiv0$ and the mean is $0$.
Assume henceforth that $n\ge m$.
A second differentiation gives
$$ G''_{nm}(1) = \frac1{m^2} [u^n] \frac{u^{2m}}{1-u}. $$
Therefore
$$ G''_{nm}(1) = \begin{cases} \dfrac1{m^2}, & n\ge2m,\[6pt] 0, & m\le n<2m. \end{cases} \tag{8} $$
Since
$$ E(X_m^2)=G''{nm}(1)+G'{nm}(1), $$
we obtain
$$ E(X_m^2) = \begin{cases} \dfrac1{m^2}+\dfrac1m, & n\ge2m,\[8pt] \dfrac1m, & m\le n<2m. \end{cases} $$
Hence
$$ \operatorname{Var}(X_m) = E(X_m^2)-E(X_m)^2 = \begin{cases} \dfrac1m, & n\ge2m,\[8pt] \dfrac1m-\dfrac1{m^2}, & m\le n<2m. \end{cases} \tag{9} $$
The standard deviation is therefore
$$ \sigma_m= \begin{cases} \dfrac1{\sqrt m}, & n\ge2m,\[10pt] \sqrt{\dfrac1m-\dfrac1{m^2}}, & m\le n<2m. \end{cases} \tag{10} $$
If $n<m$, then $\sigma_m=0$.
Verification
For $m=1$, formula (3) becomes
$$ G_{n1}(z) = [u^n]\frac{e^{(z-1)u}}{1-u}, $$
which is the generating function for fixed points discussed in the text.
The mean obtained from (7) is
$$ E(X_1)=1, $$
the classical average number of fixed points.
For $n\ge2m$, the factorial moments satisfy
$$ E!\bigl(X_m(X_m-1)\bigr)=\frac1{m^2}, $$
which agrees with the direct counting argument: choosing two disjoint $m$-cycles contributes
$$ \frac1{m^2} $$
to the second factorial moment.
Thus the generating function, probabilities, mean, and variance are mutually consistent.
Notes
As $n\to\infty$ with $m$ fixed,
$$ G_{nm}(z) \to \exp!\left(\frac{z-1}{m}\right), $$
because the truncation in (4) disappears. Hence the number of $m$-cycles tends to a Poisson distribution with parameter $1/m$:
$$ p_{nkm}\to e^{-1/m}\frac{(1/m)^k}{k!}. $$
This limiting distribution has mean and variance both equal to $1/m$, in agreement with (7) and (9). ∎