6
$\begingroup$

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.

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

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.$$

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

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}

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.