# How many permutations

How many permutations $\pi \in S_{2n}$ for which $\exists a\in [2n]$ such that set $\lbrace a,\pi (a),\pi ^2(a),\pi^3(a),... \rbrace$ has exactly $n$ elements.

I need help to solve this.

• Do you know about cycle decompositions of permutations? – Christoph Apr 19 '15 at 14:43
• You need to count the permutation that have at least one cycle of length $n$ in decomposition to cycles. – user207868 Apr 19 '15 at 14:44

You need to count the permutation that have at least one cycle of length n in decomposition to cycles.

First choose $n$ elements and make them a cycle, you can achieve this in ${2n \choose n} \cdot (n-1)!$ ways. You can permute the rest as you wish, which means that we have to multiply the just computed number by $n!$.

Unfortunately we count the permutations that decompose to two cycles of length $n$ twice. So the final answer is

$${2n \choose n} n! (n-1)! - \frac{{2n \choose n} (n-1)!^2}{2} = \frac{(2n)!}{n^2} \cdot \frac{2n-1}2.$$

• nice work. i wish i can count as well as you do! – abel Apr 19 '15 at 23:45

Such a permutation will have a cycle of length $n$, but can act on the remaining $n$ elements in any way....

We have:

\begin{align} \binom{2n}{n} (n-1)! \end{align}

Possible cycles of length $n$ (choose the elements, choose an ordering).

And $n!$ ways to permute the other elements. Multiplying these gives:

\begin{align} \binom{2n}{n} n! (n-1)! \end{align}

But wait! I have double counted those permutations which consist of two cycles of length $n$. There are:

\begin{align} \frac{1}{2}\binom{2n}{n} (n-1)!^2 \end{align}

of those.... So this gives an overall answer of:

\begin{align} \binom{2n}{n} n! (n-1)! - \frac{1}{2}\binom{2n}{n} (n-1)!^2 = \binom{2n}{n} (n-1)!^2 (n-\tfrac{1}{2}) \end{align}

By way of enrichment here is an alternate formulation using combinatorial species. The species of permutations with cycles of size $n$ marked is $$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=2}(\mathcal{Z}) + \cdots + \mathcal{U}\mathfrak{C}_{=n}(\mathcal{Z}) + \mathfrak{C}_{=n+1}(\mathcal{Z}) + \cdots).$$

This gives the generating function $$G(z, u) = \exp\left(z+\frac{z^2}{2}+\frac{z^3}{3}+\cdots +u\frac{z^n}{n}+\frac{z^{n+1}}{n+1}+\cdots\right)$$ which is $$G(z, u) = \exp\left(u\frac{z^n}{n} - \frac{z^n}{n} +\log\frac{1}{1-z}\right)$$ or $$G(z, u) = \frac{1}{1-z}\exp\left(-\frac{z^n}{n}\right) \exp\left(u\frac{z^n}{n}\right).$$

We seek to compute $$(2n)! [z^{2n}] [u] G(z, u) + (2n)! [z^{2n}] [u^2] G(z, u).$$

The first component is $$(2n)! [z^{2n}] \frac{1}{1-z} \exp\left(-\frac{z^n}{n}\right) \frac{z^n}{n}.$$ Since we are extracting $[z^{2n}]$ this becomes $$(2n)! [z^{2n}] \frac{1}{1-z} \left(1-\frac{z^n}{n}+\frac{1}{2}\frac{z^{2n}}{n^2}\right) \frac{z^n}{n}.$$

The second component is $$(2n)! [z^{2n}] \frac{1}{1-z} \exp\left(-\frac{z^n}{n}\right) \frac{1}{2} \frac{z^{2n}}{n^2}.$$

Since we are extracting $[z^{2n}]$ this becomes $$(2n)! [z^{2n}] \frac{1}{1-z} \left(1-\frac{z^n}{n}+\frac{1}{2}\frac{z^{2n}}{n^2}\right) \frac{1}{2} \frac{z^{2n}}{n^2}.$$

Adding these we obtain $$(2n)! [z^{2n}] \frac{1}{1-z} \left(1-\frac{z^n}{n}+\frac{1}{2}\frac{z^{2n}}{n^2}\right) \left(\frac{z^n}{n} + \frac{1}{2} \frac{z^{2n}}{n^2}\right).$$

This produces $$(2n)! [z^{2n}] \frac{1}{1-z} \left(\frac{z^n}{n}-\frac{z^{2n}}{n^2}+ \frac{1}{2}\frac{z^{3n}}{n^3} +\frac{1}{2}\frac{z^{2n}}{n^2} -\frac{1}{2}\frac{z^{3n}}{n^3} +\frac{1}{4}\frac{z^{4n}}{n^4}\right).$$

We may omit the terms in $z^{3n}$ and $z^{4n}$ to get $$(2n)! [z^{2n}] \frac{1}{1-z} \left(\frac{z^n}{n}-\frac{z^{2n}}{n^2} +\frac{1}{2}\frac{z^{2n}}{n^2}\right) \\ = (2n)! [z^{2n}] \frac{1}{1-z} \left(\frac{z^n}{n}-\frac{1}{2}\frac{z^{2n}}{n^2}\right).$$

This finally yields $$(2n)!\frac{1}{n} [z^n]\frac{1}{1-z} - (2n)! \frac{1}{2}\frac{1}{n^2} [z^0] \frac{1}{1-z} \\ = (2n)! \left(\frac{1}{n} - \frac{1}{2} \frac{1}{n^2}\right) \\ = \frac{(2n)!}{n^2} \frac{2n-1}{2} = \frac{(2n-1)!}{n} (2n-1).$$

This gives the sequence $$1, 9, 200, 8820, 653184, 73180800, 11564467200, 2451889440000,\ldots$$ which is OEIS A052145.