Número de permutaciones que son producto de exactamente dos ciclos disjuntos

Question

Dejemos que $a_n$ denotan el número de esas permutaciones $\sigma$ en $\{1,2,3....,n\}$ tal que $\sigma$ es un producto de exactamente dos ciclos disjuntos. Entonces

1. $a_5 = 50$

2. $a_4 = 14$

3. $a_5 = 40$

4. $a_4 = 11$

Intenté específicamente para $a_5$ y $a_4$ con un poco de cálculos. Pero quiero saber sobre una fórmula para $a_n$ con menos cálculos

Answer 1

Hay una fórmula bien conocida para el número de permutaciones con $p_i$ ciclos de longitud $i$ para cada $i$ , a saber

$$ {n! \over \prod_i i^{p_i} (p_i)!}$$

(ver por ejemplo este puesto de Mark Jason Dominus ). En el caso de tener un ciclo de longitud $k$ y uno de longitud $n-k$ y $k \not = n-k$ Entonces, usted tiene $p_k = p_{n-k} = 1$ y esto se reduce a $$n! \times {1 \over k(n-k)}.$$ Si $k = n-k$ es decir, si $k = n/2$ Entonces, usted tiene $p_k = 2$ y el número de tales permutaciones es $$n! \times {2 \over n^2}.$$

Por ejemplo, si $n = 5, k = 2$ la primera fórmula te da que hay $5!/(2 \times 3) = 20$ permutaciones de $[5]$ que consiste en un 2 ciclos y un 3 ciclos. Si $n = 4, k = 2$ la segunda fórmula te da que hay $4! \times 2/4^2 = 3$ permutaciones que consisten en dos 2 ciclos.

A partir de esto se puede derivar una fórmula general para el número de permutaciones de $n$ que son productos de dos ciclos disjuntos sumando sobre los posibles valores de $k$ . Si $n$ es incluso que tendrá que manejar el $k = n/2$ caso por separado del resto de la suma.

(No está claro si su definición cuenta un ciclo de longitud 1 como un ciclo. Por ejemplo, ¿es $(3, 5)(1, 4)(2)(6)$ un producto de dos ciclos distintos en $S_6$ ? Si es así, su suma será más complicada, pero la idea general sigue siendo válida).

Answer 2

Me gustaría presentar la conexión con los números de Stirling ya que no ha sido señalada. Para la primera interpretación en la que los ciclos pueden ser monotonales obtenemos la especie $\mathfrak{P}_{=2}(\mathfrak{C}(\mathcal{Z}))$ lo que da lugar a una función generadora

$$n! [z^n] \frac{1}{2!}\left(\log\frac{1}{1-z}\right)^2 = \left[n\atop 2\right]$$

la secuencia

$$0, 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576,\ldots $$

que es OEIS A000254 que parece ser una partido. La segunda interpretación es cuando no admitimos singletons como ciclos y obtenemos la especie $\mathfrak{P}_{=2}(\mathfrak{C}_{\ge 2}(\mathcal{Z}))$ que da como resultado por función generadora

$$n! [z^n] \frac{1}{2!}\left(-z + \log\frac{1}{1-z}\right)^2$$

la secuencia

$$0, 0, 0, 3, 20, 130, 924, 7308, 64224, 623376,\ldots$$

que es OEIS A000276 . Para $n\ge 2$ este se simplifica a

$$\frac{1}{2} n! [z^n] \left(z^2 - 2z \log\frac{1}{1-z} + \left(\log\frac{1}{1-z}\right)^2\right) \\ = [[n=2]] - n! [z^{n-1}] \log\frac{1}{1-z} + \left[n\atop 2\right] \\ = [[n=2]] - n \times (n-2)! + \left[n\atop 2\right].$$