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.
 A: 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.$$
A: 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}
A: 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.
