4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.