# (Average) Number of cycles of length m in permutations on N with k cycles

Suppose we have permutations on $[1,2,...,n]$ that have exactly $k$ cycles (which there are $|s(n,k)|$ of where $s(n,k)$ is the Stirling number of the first kind).

What is the average number of cycles of length $m$ for one of these permutations? Let's call this number $C(m,n,k)$.

So for $m=1$, this is the total number of fixed points in all those permutations divided by |s(n,k)|. Even for this case I'm having trouble formulating a recurrence relation.

We know by definition that $\sum_m C(m,n,k)=k$ and $\sum_m m.C(m,n,k)=n$.

For example, for $n=4,k=2$, $|s(4,2)|=11$ and we have, $$C(1,4,2) = 8/11, \qquad C(2,4,2) = 6/11, \qquad C(3,4,2) = 8/11$$ and for $n=9, k=3$, $|s(9,3)|=118124$ and we have, $$\;\;\;C(1,9,3)=117612/|s(9,3)|=0.9957..., \\\; C(2,9,3)= 63504/|s(9,3)|=0.5376...,\\\; C(3,9,3)=46032/|s(9,3)|=0.3897..., \\\; C(4,9,3)=37800/|s(9,3)|=0.3200...,\\\; C(5,9,3)=33264/|s(9,3)|=0.2816...,\\\; C(6,9,3)=30240/|s(9,3)|=0.2560...,\\\;C(7,9,3)=25920/|s(9,3)|=0.2194...$$

At the moment, I'm mainly interested in the case where $n=k^2$. From the above experiment it seems possibly \lim_{k\to\infty} C(1,k^2,k)=1. edit: From Marko's answer this is not true.

Ultimately, I'm interested the cumulative distribution, say, $$\lim_{k\to\infty} \sum_{m=0}^{kx} C(m,k^2,k)$$

Any references or help would be greatly appreciated.

For the first part of the question with $$Q(n, k, m)$$ the number of cycles of size $$m$$ among permutations of $$[n]$$ having $$k$$ cycles we get the species

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}_{=k}( \textsc{CYC}_{\lt m}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{= m}(\mathcal{Z}) + \textsc{CYC}_{\gt m}(\mathcal{Z})).$$

This yields the bivariate generating function

$$G(z, u) = \frac{1}{k!}\left(\log\frac{1}{1-z}-\frac{z^m}{m} + u\frac{z^m}{m}\right)^k.$$

The desired statistic has generating function

$$\left.\frac{\partial}{\partial u} G(z, u)\right|_{u=1} \\ = \left. \frac{1}{(k-1)!}\left(\log\frac{1}{1-z}-\frac{z^m}{m} + u\frac{z^m}{m}\right)^{k-1} \frac{z^m}{m} \right|_{u=1} \\ = \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \frac{z^m}{m}.$$

Extracting coefficients we obtain

$$n! [z^n] \frac{z^m}{m} \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \\ = \frac{n!}{m} [z^{n-m}] \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \\ = \frac{n!}{m (n-m)!} (n-m)! [z^{n-m}] \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1}.$$

Divide by $${n\brack k}$$ for the expectation

$$\bbox[5px,border:2px solid #00A000]{ \frac{n!}{m (n-m)!} {n-m\brack k-1} {n\brack k}^{-1}.}$$

For the proof that these sum to $$k$$ which must hold by first principles we observe that we need $$n-m\ge k-1$$ or $$n+1-k\ge m$$ and obtain the claim

$${n\brack k}^{-1} \sum_{m=1}^{n+1-k} \frac{n!}{m (n-m)!} {n-m\brack k-1} = k.$$

The EGF of the sum is

$$\sum_{n\ge k} \frac{w^n}{n!} \sum_{m=1}^{n+1-k} \frac{n!}{m (n-m)!} (n-m)! [z^{n-m}] \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \\ = \sum_{n\ge k} w^n \sum_{m=1}^{n+1-k} \frac{1}{m} [z^{n}] z^m \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1}.$$

Now we may actually extend the inner sum to infinity because when $$m\gt n+1-k$$ we have $$m+k-1\gt n$$ and there is no contribution to $$[z^n].$$ We get

$$\sum_{n\ge k} w^n \sum_{m\ge 1} \frac{1}{m} [z^{n}] z^m \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \\ = \sum_{n\ge k} w^n [z^n] \sum_{m\ge 1} \frac{1}{m} z^m \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \\ = \sum_{n\ge k} w^n [z^n] \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k} \\ = \frac{1}{(k-1)!} \left(\log\frac{1}{1-w} \right)^{k}.$$

Extracting coefficients we find

$${n\brack k}^{-1} n! [w^n] k \frac{1}{k!} \left(\log\frac{1}{1-w} \right)^{k} = {n\brack k}^{-1} k {n\brack k} = k$$

as claimed. For sanity check number two the claim is

$${n\brack k}^{-1} \sum_{m=1}^{n+1-k} \frac{n!}{(n-m)!} {n-m\brack k-1} = n.$$

Re-using the computation from the first one yields

$$\sum_{n\ge k} w^n [z^n] \sum_{m\ge 1} z^m \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \\ = \sum_{n\ge k} w^n [z^n] \frac{z}{1-z} \frac{1}{(k-1)!} \left(\log\frac{1}{1-z} \right)^{k-1} \\ = \frac{w}{1-w} \frac{1}{(k-1)!} \left(\log\frac{1}{1-w} \right)^{k-1} = w \frac{d}{dw} \frac{1}{k!} \left(\log\frac{1}{1-w} \right)^{k}.$$

Extracting coefficients we find

$${n\brack k}^{-1} n! [w^n] w \frac{d}{dw} \frac{1}{k!} \left(\log\frac{1}{1-w} \right)^{k} = {n\brack k}^{-1} n {n\brack k} = n$$

again as claimed. The first sanity check must hold because when we sum the expectations of the number of cycles of all possible sizes we should get $$k$$ cycles, which is constant in the problem. The second must hold because if we sum the lengths times the number of cycles of all possible sizes we should cover all of $$n,$$ also a constant here.

These formulae were verified using the cycle index $$Z(S_n)$$ of the symmetric group with the following Maple script which is practicable to about $$n=45.$$ For example with $$n=20$$ and $$k=15$$ (permutations of twenty elements having fifteen cycles) we get for the total count of cycles of lengths one to six the values

$$10995785640, 2640350580, 737990400, 191280600, 39070080, 4651200$$

and for the expectation we find

$$11.28998110, 2.710993931, 0.7577355487, 0.1963983683, \\ 0.04011541140, 0.004775644215$$

and these do indeed sum to fifteen.

with(combinat);

pet_cycleind_symm :=
proc(n)
option remember;

if n=0 then return 1; fi;

end;

Q :=
proc(n, k)
option remember;
local idx, conjclass, cyc, count;

count := table([seq(q=0, q=1..n+1-k)]);

if n=1 then
idx := [a[1]]
else
idx := pet_cycleind_symm(n);
fi;

for conjclass in idx do
if degree(conjclass) = k then
for cyc in indets(conjclass) do
count[op(1, cyc)] :=
count[op(1, cyc)]
+ degree(conjclass, cyc)
* lcoeff(conjclass);
od;
fi;
od;

[seq(n!*count[q], q=1..n+1-k)];
end;

QX :=
(n, k, m) -> n!/m/(n-m)! * abs(stirling1(n-m, k-1));

QXS := (n, k) -> [seq(QX(n, k, m), m=1..n+1-k)];


Remark. The above used the technique of annihilated coefficient extractors (ACE), otherwise known as the substitution rule for formal power series. There are several more examples at this MSE link I and at this MSE link II and also here at this MSE link III.

• Very nice and instructive! (+1) – Markus Scheuer May 2 '17 at 10:22