Number of permutations in the symmetric group $S_n$ composed of $k$ disjoint $m$-cycles

Question

Find the total number of permutations in the symmetric group $S_n$ that are composed of $k$ disjoint $m$-cycles, for valid $m$ and k.

I encountered a simpler version of this question in class for $m=k=2$. They way I solved the $m=k=2$ version is:

First chose $4$ numbers out of $n$, which can be done in $\binom{n}{4}$ ways, now for each of these selections we can make a few of the permutations included in the set, since the permutations we are counting are of the form: $(ab)(cd)$. Now of the four different numbers you can form $\binom{4}{2}$ couples but since disjoint cycles commute in $S_n$ we divide by $2$, which gives the result:
$$\frac{{\binom{n}{4} \cdot \binom{4}{2}}}{2}$$ I had a homework task to create a generalisation of any of the problems we had encountered in class, solve it(by help if necessary) and then present it in class, of which I created this generalization which is the given problem.

I've tried the exact same way for the generalization but there are some things I've used here that aren't valid for the generalization one of which is that $(ij)=(ji)$, and I'm stuck on how to generalize the solution.

Any help is appreciated on how to tackle the generalization or suggest any different routes I could take to generalize it for example removing some restrictions and any suggestion on how to tackle it.

Answer 1

Using combinatorial classes as in Analytic Combinatorics by Flajolet and Sedgewick we have the following class $\mathcal{P}$ of permutations with exactly $k$ $m$-cycles

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

This gives the EGF

$$G(z) = \exp\left(z + \frac{z^2}{2} + \cdots + \frac{z^{m-1}}{m-1} + \frac{z^{m+1}}{m+1} + \cdots\right) \frac{1}{k!} \left[\frac{z^m}{m}\right]^k \\ = \exp\left(\log\frac{1}{1-z}\right) \exp\left(-\frac{z^m}{m}\right) \frac{1}{k!} \left[\frac{z^m}{m}\right]^k \\ = \frac{1}{1-z} \exp\left(-\frac{z^m}{m}\right) \frac{1}{k!} \left[\frac{z^m}{m}\right]^k.$$

Extracting the coefficient on the EGF in $z$ we find

$$n! [z^n] G(z) = n! [z^n] \frac{1}{1-z} \exp\left(-\frac{z^m}{m}\right) \frac{1}{k!} \left[\frac{z^m}{m}\right]^k \\ = \frac{n!}{m^k k!} [z^{n-mk}] \frac{1}{1-z} \exp\left(-\frac{z^m}{m}\right) \\ = \frac{n!}{m^k k!} \sum_{q=0}^{\lfloor n/m \rfloor - k} [z^{n-mk-qm}] \frac{1}{1-z} [z^{qm}] \exp\left(-\frac{z^m}{m}\right) \\ = \frac{n!}{m^k k!} \sum_{q=0}^{\lfloor n/m \rfloor - k} [z^{qm}] \exp\left(-\frac{z^m}{m}\right) \\ = \frac{n!}{m^k k!} \sum_{q=0}^{\lfloor n/m \rfloor - k} [z^{q}] \exp\left(-\frac{z}{m}\right).$$

This is

$$\bbox[5px,border:2px solid #00A000]{ \frac{n!}{m^k k!} \sum_{q=0}^{\lfloor n/m \rfloor - k} \frac{(-1)^q}{m^q q!} \underset{n\rightarrow\infty}{\sim} \frac{n!}{m^k k!} \exp(-1/m).}$$

Observe that when $n=mk$ so there are no other cycles this will produce $\frac{n!}{m^k k!}.$ Note also that e.g. it is not possible to have exactly $n-1$ fixed points in a permutation of length $n$ because the last fixed point is forced to join. And indeed setting $m=1$ we get (derangement numbers appear)

$$\frac{n!}{k!} \sum_{q=0}^{n-k} \frac{(-1)^q}{q!} = \frac{n!}{(n-1)!} \sum_{q=0}^1 \frac{(-1)^q}{q!} = n \times (1-1) = 0.$$

We can verify these numbers with Maple using the following compact code:

with(combinat);


pet_disjcyc :=
proc(p)
local dc, pos;

    dc := convert(p, 'disjcyc');

    for pos to nops(p) do
        if p[pos] = pos then
            dc := [op(dc), [pos]];
        fi;
    od;

    dc;
end;

ENUM :=
proc(n, m, k)
option remember;
local perm, res, fact, mat;

    res := 0;
    perm := firstperm(n);

    while type(perm, `list`) do
        fact := map(nops, pet_disjcyc(perm));
        mat := select(len -> len = m, fact);
        if nops(mat) = k then
            res := res+1;
        fi;

        perm := nextperm(perm);
    od;

    res;
end;

X := (n,m,k) ->
n!/m^k/k!*add((-1)^q/m^q/q!, q=0..floor(n/m)-k);

AX := (n,m,k) -> n!/m^k/k!*exp(-1/m);

Answer 2

For arbitrary integers $m>1$ and $k$ and $n\geq mk$ the number of all permutations which are the product of exactly $k$ independent cycles of length $m$ can be computed by the formula $$ ((m-1)!)^k\frac{1}{k!}\binom{n}{m}\binom{n-m}{m}\ldots\binom{n-(k-1)m}{m}=\frac{n!}{m^kk!(n-mk)!}. $$

If $k=m=2$ we get the OP formula or the same formula given by @lulu in the comment.

PS. By the way, this formula is useful for $m=2$ in one of the proofs that the group $S_n$ at $n\neq6$ has no outer automorphisms.

Answer 3

For PIE we need to choose the required poset which consists of nodes $Q_S$ where $S$ is a set of disjoint $m$-cycles chosen from the $m$-cycles that can be formed using the elements of $[n].$ We build rows for fixed cardinality of $|S|.$ We consider the poset spanned by the nodes on row $k$ and the top row, i.e. the row where $|S|=\lfloor n/m\rfloor.$ The weight attached to the node $Q_S$ is $(-1)^{|S|-k} {|S|\choose k}$ and the poset is ordered by subset inclusion of $S$. The permutations that are represented at each node consist of the $|S|$ cycles of length $m$ with the rest being arranged at liberty. The cardinality of the permutations represented at a node $Q_S$ is thus $(n-m|S|)!.$ We now count the permutations represented by the nodes of the subposet according to their weight. Do this in two ways: the intersection with row $p$ contains

$${n\choose m,m,\ldots,m,n-pm} \frac{1}{p!} (m-1)!^p = \frac{n!}{m^p p!} \frac{1}{(n-pm)!}.$$

nodes. The weight on these is $(-1)^{p-k} {p\choose k}$ and the cardinality of the set of permutations being represented is $(n-pm)!$ for a total of

$$\sum_{p=k}^{\lfloor n/m\rfloor} (-1)^{p-k} {p\choose k} \frac{n!}{m^p p!} \\ = n! \sum_{p=0}^{\lfloor n/m\rfloor -k} (-1)^p {p+k\choose k} \frac{1}{m^{p+k} (p+k)!} \\ = \frac{n!}{m^k k!} \sum_{p=0}^{\lfloor n/m\rfloor -k} \frac{(-1)^p}{m^p p!}.$$

Good, this is our claim. Now to count in the second way, what is the total weight on a permutation with precisely a set $P$ of $m$-cycles where $k\le |P|\le \lfloor n/m \rfloor.$ It is represented at all $Q_S$ where $S\subseteq P$ and $|S|\ge k$ giving the sum

$$\sum_{S\subseteq P, |S|\ge k} (-1)^{|S|-k} {|S|\choose k} = \sum_{p=k}^{|P|} {|P|\choose p} (-1)^{p-k} {p\choose k}.$$

Now a permutation with $|P|=k$ i.e. exactly $k$ $m$-cycles therefore contributes with weight one, as desired. For $|P|>k$ we find

$$\sum_{p=k}^{|P|} (-1)^{p-k} \frac{|P|!}{(|P|-p)! \times k! \times (p-k)!} \\ = {|P|\choose k} \sum_{p=k}^{|P|} (-1)^{p-k} {|P|-k\choose p-k} \\ = {|P|\choose k} \sum_{p=0}^{|P|-k} (-1)^{p} {|P|-k\choose p} = {|P|\choose k} (1-1)^{|P|-k} = 0.$$

We see that permutations with more than $k$ $m$-cycles contribute with weight zero, which concludes the PIE argument.

Shown below is an alternate enumeration routine to verify these data which is a bit more efficient than iterating over all permutations. Rather, we iterate over cycle shapes which we obtain from the cycle index of the symmetric group.

with(numtheory);
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;


ENUM :=
proc(n, m, k)
option remember;
local permtype, res;

    if n=1 then
        return `if`(m=1 and k=1, 1, 0);
    fi;

    
    res := 0;

    for permtype in pet_cycleind_symm(n) do
        if degree(permtype, a[m]) = k then
            res := res + lcoeff(permtype);
        fi;
    od;

    n!*res;
end;

X := (n,m,k) ->
n!/m^k/k!*add((-1)^q/m^q/q!, q=0..floor(n/m)-k);

Answer 4

By combinatorial species we have to count labelled k-sets of m-cycles.

The species formula is

$$ Ens_k(Cyc_m(X)) $$

Passing to e.g.f we get

$$ egf(x) = {1 \over k!} ({x^m \over m})^k = { x^{mk}\over k!m^k} $$

Since there are $mk$ labels, we are now interested in the coefficient of $$ { x^{mk}\over (mk)!} $$

which is the well known

$$ (mk)! \over k!m^k $$

Answer 5

Here we use PIE, the principle of inclusion-exclusion in order to calculate the number $\color{blue}{A_k}$ of permutations of $S_n$ with exactly $k$ $m$-cycles.

We consider $m$-cycles of a permutation $\sigma\in S_n$ as properties of this permutation. Let $T$ be a set of properties, i.e. a set of $m$-cycles. We denote with \begin{align*} N_{\supseteq T}&=\#\{\sigma\in S_n:\sigma\mathrm{\ possesses\ }\bf{at\ least}\mathrm{\ the\ properties\ in}\ \it{T}\}\\ N_{= T}&=\#\{\sigma\in S_n:\sigma\mathrm{\ possesses\ }\bf{exactly}\mathrm{\ the\ properties\ in\ \it{T}}\}\\ \end{align*}

The number of permutations with $k$ (or more) cycles of length $m$ is \begin{align*} \color{blue}{\sum_{T: |T|=k}N_{\supseteq T}}&=\binom{n}{m}\binom{n-m}{m}\ldots\binom{n-(k-1)m}{m} \frac{(m-1)!^k}{k!}(n-km)!\\ &\,\,\color{blue}{=\frac{n!}{m^kk!}}\tag{1} \end{align*}

We recall the generalized inclusion-exclusion principle. Given \begin{align*} N_{\supseteq A}=\sum_{T\supseteq A}N_{=T}\tag{2.1} \end{align*} it follows that \begin{align*} N_{= A}=\sum_{T\supseteq A}(-1)^{|T|-|A|}N_{\supseteq T}\tag{2.2} \end{align*}

We use (2.2) to calculate the number $\color{blue}{A_k}$ of permutations of $S_n$ with exactly $k$ $m$-cycles. We obtain \begin{align*} \color{blue}{A_k}&=\sum_{A:|A|=k}N_{=A}\\ &=\sum_{A:|A|=k}\sum_{T\supseteq A}(-1)^{|T|-|A|}N_{\supseteq T}\tag{$\to \mathrm{(2.2)}$}\\ &=\sum_{T:|T|\geq k}(-1)^{|T|-k}\sum_{A:|A|=k, T\supseteq A}N_{\supseteq T}\tag{3}\\ &=\sum_{q=k}^{\left\lfloor\frac{n}{m}\right\rfloor}(-1)^{q-k}\binom{q}{k}\sum_{T:|T|=q}N_{\supseteq T}\tag{4}\\ &=\sum_{q=k}^{\left\lfloor\frac{n}{m}\right\rfloor}(-1)^{q-k}\binom{q}{k}\frac{n!}{m^qq!}\tag{$\to \mathrm{(1)}$}\\ &=\sum_{q=0}^{\left\lfloor\frac{n}{m}\right\rfloor-k}(-1)^{q}\binom{q+k}{k}\frac{n!}{m^{q+k}(q+k)!}\tag{5}\\ &\,\,\color{blue}{=\frac{n!}{m^kk!}\sum_{q=0}^{\left\lfloor\frac{n}{m}\right\rfloor-k}\frac{(-1)^{q}}{m^qq!}}\tag{6} \end{align*} in accordance with the answers from @MarkoRiedel.

Comment:

• In (3) we exchange the sums.

• In (4) we observe that $N_{\supseteq T}$ does only depend on the number of $m$-cycles in $T$. We can therefore factor out $\binom{|T|}{|A|}=\binom{q}{k}$.

• In (5) we shift the index to start with $q=0$.

• In (6) we cancel and rearrange a little.

Answer 6

(I feel like someone is missing here)

The legacy solution :

• take the multinomial coefficient $ \binom {mk}{m,m,...m} $

• since order does not matter, divide this coefficient by k!

• then, for each part of size m, define (m-1)! cycles.

$$ \binom {mk}{m,m,...m} {1 \over k!} (m-1)!^k = {(mk)!\over m!^k}{1 \over k!}(m-1)!^k = {(mk)!\over m^k k!} $$