Cuántas permutaciones

Question

Cuántas permutaciones $\pi \in S_{2n} $ que $\exists a\in [2n] $ tal que $\lbrace a,\pi (a),\pi ^2(a),\pi^3(a),... \rbrace $ tiene exactamente $n$ elementos.

Necesito ayuda para solucionar esto.

Answer 1

Es necesario contar la permutación que tienen al menos un ciclo de longitud n en la descomposición en ciclos.

Primero elija $n$ elementos y hacer que un ciclo, puede conseguirlo en ${2n \choose n} \cdot (n-1)!$ maneras. Usted puede permutar el resto como quieras, que significa que tenemos que multiplicar al número sólo computado por $n!$.

Por desgracia contamos las permutaciones que se descomponen a dos ciclos de longitud $n$ dos veces. Así que la respuesta final es

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