Número de elementos de la orden $2$ en $S_n$

Question

Cuántos elementos de orden $2$ están ahí en $S_n$ ?

Usando la combinatoria llegué a esto:

Para $n$ incluso ( $n=2k$ ) hay ${n\choose2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2} {n-2\choose 2}{n-4\choose 2}\dfrac{1}{3!}+\cdots+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\cdots{2\choose 2}\dfrac{1}{k!}$ .

Para $n$ impar ( $n=2k+1$ ) hay ${n\choose 2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\dfrac{1}{3!}+\cdots+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\cdots{3\choose 2}\dfrac{1}{k!}$

¿Pero cómo encuentro las sumas?

Parece que tengo que usar la inducción. Pero no está a la altura.

¡Gracias por la ayuda!

Answer 1

Un elemento de orden $2$ es un producto de $k$ , es decir, 2 ciclos disjuntos.

• Para $k=1$ Hay $\frac{n(n-1)}{2^1\cdot 1!}$ elementos de orden dos.

• Para $k=2$ Hay $\frac{n(n-1)(n-2)(n-3)}{2^2\cdot 2!}$ elementos de orden dos.

• Para $k=3$ Hay $\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{2^3\cdot 3!}$ elementos de orden dos.

En el denominador de cada fracción, tienes un $2^k k!$ ya que cada 2 ciclos puede ser elegido en la forma $(a, b)$ o en la forma $(b, a)$ (por lo que hay que dividir por $2^k$ ), mientras que las diferentes permutaciones de los 2 ciclos no cambian el elemento (por lo que hay que dividir por $k!$ ). Por lo tanto, se obtiene en general:

• Hay $\frac{n!}{(n-2k)!2^k\cdot k!}$ elementos de orden dos que son el producto de $k$ 2 ciclos disjuntos.

Entonces, ¡suma estos para obtener su número! $$\text{number of elements of order two}=e_2(n)=\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{(n-2k)!2^k\cdot k!}$$ Obsérvese que se cumple la siguiente relación de recurrencia. $$e_2(n)=e_2(n-1)+(1+e_2(n-2))(n-1)$$

Answer 2

Probablemente no sea de ayuda, pero creo que su suma puede estar escrita $f(\sqrt{2})$ donde $$ f(x) = \sqrt{2}^{-n} \sum_{k=1}^{\lfloor \frac{n}2 \rfloor} \frac1{k!}\frac{d^{2k}}{dx^{2k}}x^n $$

Answer 3

Si acepta una función hipergeométrica confluente como una forma cerrada, entonces un sistema de álgebra computacional como Mathematica le dará
para incluso $n = 2w$ :
$\left(-\frac{1}{2}\right)^{-w} U\left(-w,\frac{1}{2},-\frac{1}{2}\right)-1$
y para impar $n = 2w-1$ :
$\left(-\frac{1}{2}\right)^{1-w} U\left(1-w,\frac{3}{2},-\frac{1}{2}\right)-1$

Answer 4

Sea $n$ sea un número entero y $J = [\frac{n}{2}]$ y que $T_n^1 = \frac{n(n-1)}{2}$ . Entonces, el número de $j$ -transposiciones ( $1< j\leq J$ ) en $S_n$ es $T_n^j=(n-1)T_{n-j} $ . Por lo tanto, el número de transposiciones posibles es $$\sum_{j=1}^J T_n^j = \sum_{j=1}^J (n-1)T_{n-j}.$$ Por ejemplo, si $n=10$ entonces $\sum_{j=1}^5 T_{10}^j = 45+ 9\big(28+21+15+10 \big)$ .

Answer 5

Utilizando clases combinatorias de Flajolet y Sedgewick, Analítica Combinatoria tenemos para las involuciones la clase

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\textsc{CYC}_{=1}(\mathcal{Z})+ \textsc{CYC}_{=2}(\mathcal{Z})).$$

Sin embargo, debemos tener en cuenta (restar) las permutaciones que consisten en (la identidad, un conjunto de puntos fijos). Esto tiene clase

$$\textsc{SET}(\textsc{CYC}_{=1}(\mathcal{Z})).$$

Esto da el EGF (aquí también hemos cancelado la permutación vacía -- el conjunto vacío)

$$Q(z) = - \exp(z) + \exp(z+z^2/2) = \sum_{n\ge 0} Q_n \frac{z^n}{n!}.$$

Extrayendo los coeficientes encontramos

$$Q_n = - n! [z^n] \exp(z) + n! [z^n] \exp(z) \exp(z^2/2) \\ = -1 + n! \sum_{k=0}^{\lfloor n/2 \rfloor} [z^{2k}] \exp(z^2/2) [z^{n-2k}] \exp(z) \\ = - 1 + n! \sum_{k=0}^{\lfloor n/2 \rfloor} [z^k] \exp(z/2) \frac{1}{(n-2k)!} = - 1 + n! \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{1}{2^k k! (n-2k)!} \\ = n! \sum_{k=1}^{\lfloor n/2 \rfloor} \frac{1}{2^k k! (n-2k)!}.$$

Para obtener la recurrencia diferenciamos $Q(z)$ para obtener

$$Q'(z) = -\exp(z) + \exp(z+z^2/2) (1+z) \\ = - \exp(z) + (Q(z)+\exp(z)) (1+z) \\ = Q(z) (1+z) + z \exp(z).$$

La extracción de coeficientes producirá

$$n! [z^n] Q'(z) = Q_{n+1} = n! [z^n] Q(z) + n! [z^{n-1}] Q(z) + n! [z^{n-1}] \exp(z) \\ = Q_n + n! \frac{Q_{n-1}}{(n-1)!} + n = Q_n + n (Q_{n-1}+1).$$

Esto es OEIS A001189 .