La búsqueda combinatoria o grupo teórico de la prueba de permutación identidad

Question

Mientras se trabaja en otro problema, he encontrado el siguiente combinatoria de la igualdad, pero yo tengo analíticamente, y tengo la curiosidad de encontrar un recuento de argumento.

Fix $n$ un entero positivo. Para$n_1\leq n_2\leq \cdots \leq n_k$$\sum n_i=n$, vamos a $s_{n_1,\dots,n_k}$ el número de permutaciones en $\Sigma_n$ con la ordenada del ciclo de longitudes $n_1,n_2,\dots,n_k$.

A continuación, mostrar:

$$\sum_{n_1,\dots,n_k} 4^{k-1}s_{n_1,\dots,n_k}=n\cdot n!$$

donde la suma se limita al caso en que todos los $n_i$ son impares.

Supongo que sólo podría escribir $t_k$ como el número de permutaciones en $\Sigma_n$ abono de $k$ impar ciclos, y escribo como $\sum_{k} 4^{k-1}t_k = n\cdot n!$.

Por ejemplo, para $n=5$, las posibles permutaciones de la firma $s_{5}=4!$, $s_{1,1,3}=2\binom{5}{2}=20$, $s_{1,1,1,1,1}=1$ por lo que la suma es:

$$4^0\cdot24+4^2\cdot 20 + 4^4\cdot 1=600=5\cdot 5!$$

Tengo una prueba de esto, que es bruto - que implica la sustitución de la energía de la serie de $\theta=\arctan x$ en el poder de la serie para $\sin 4\theta$ $\cos 4\theta$ (para los pares y los impares $n$, respectivamente). Que parece desagradable, por lo que estoy buscando de una manera más directa combinatoria argumento.

Una cosa que yo consideraba era la posibilidad de utilizar la identidad:

$$\sum_{n=0}^{m} n\cdot n! =(m+1)!-1$$

Answer 1

Permutaciones impares ciclos sólo y el conteo de ciclo marcado han la especie

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=5}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=7}(\mathcal{Z}) + \cdots).$$

que los rendimientos del FEAG

$$G(z,u) = \exp\left(uz+ u\frac{z^3}{3}+ u\frac{z^5}{5}+ u\frac{z^7}{7}+\cdots\right) \\ = \exp\left(u\sum_{k\ge 0}\frac{z^{2k+1}}{2k+1}\right) \\ = \exp\left(u\log\frac{1}{1-z} - u\sum_{k\ge 1} \frac{z^{2k}}{2k}\right) \\ = \exp\left(u\log\frac{1}{1-z} - u\frac{1}{2}\log\frac{1}{1-z^2}\right).$$

Ahora tenemos a $u=4$, por lo que continuamos con

$$\frac{1}{(1-z)^4} \exp\left(2\log(1-z^2)\right) = \frac{(1-z^2)^2}{(1-z)^4} = \frac{(1+z)^2}{(1-z)^2} \\ = (1+2z+z^2) \frac{1}{(1-z)^2}.$$

Nos recibe como resultado la cantidad

$$\frac{1}{4} n! [z^n] G(z, 4) = \frac{1}{4} n! \left({n+1\elegir 1} + 2{n\elegir 1} + {n-1\elegir 1}\right) \\ = \frac{1}{4} n! (n+1+2n+n-1) = n! \times n.$$

Answer 2

Voy a introducir una elegante estructura, que es un color de permutación.

Un color de permutación $\sigma$ es una permutación de actuar en $\{1,2,\ldots,n\}$, con la propiedad de que cada elemento tiene una extraña orden. Por otra parte, los elementos de $\{1,\ldots,n\}$ son de color con algún color de $\{\text{cyan},\text{magenta},\text{yellow},\text{black}\}$ y la permutación es el color-la conservación, es decir, el color de $\sigma(a)$ es el mismo que el color de $a$. Queremos contar el número de permutaciones de color, dada por: $$ L_n=\!\!\!\!\sum_{\substack{n_1,\ldots,n_k \text{ odd}\\ n_1+\ldots n_k=n}}\!\!\! 4^k\cdot s_{n_1,\ldots,n_k}.$$

Preliminar lema: el número de permutaciones de $\{1,\ldots,k\}$ de manera tal que cada elemento tiene una extraña orden está dada por: $$ C_k = k!\cdot [x^k]\frac{1}{1-x}\cdot\exp\left(-\frac{x^2}{2}-\frac{x^4}{4}-\ldots\right)= k!\cdot [x^k]\sqrt{\frac{1+x}{1-x}}. $$

Consecuencia: el número de permutaciones de color está dado por $$ \sum_{c+m+y+k=n}\binom{n}{c}\binom{n-c}{m}\binom{n-c-m}{y} C_c C_m C_y C_k = n!\cdot [x^n]\left(\frac{1+x}{1-x}\right)^2=4n\cdot n!.$$

Hecho. La doble contabilización gana de nuevo.

---

Otra posibilidad sería dado por mostrar que $L_{n+1}-L_n = (n+1)!-n!$ por algunos recursiva argumento. Sin embargo, yo no era capaz de encontrarlo.