Considere las siguientes dos funciones de generación: $$e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}$$ $$\log\left(\frac{1}{1-x}\right)=\sum_{n=1}^{\infty}\frac{x^n}{n}.$$ Si vivimos en función de la tierra, es bastante claro que hay una relación inversa entre estas dos cosas. En particular, $$e^{\log\left(\frac{1}{1-x}\right)}=1+x+x^2+x^3+\ldots$$ Si vivimos en la generación de la función de la tierra, esta identidad no es realmente tan obvio. Podemos averiguar que el coeficiente de $x^n$ en $e^{\log\left(\frac{1}{1-x}\right)}$ es dado como $$\sum_{a_1+\ldots+a_k=n}\frac{1}{a_1\cdot \cdots \cdot a_k}\cdot \frac{1}{k!}$$ donde la suma se ejecuta sobre todas las formas de escribir $n$ como un ordenado suma de enteros positivos. Supuestamente, para cada elección de $n$, esta cosa sumas a $1$. Yo realmente no veo por qué. Hay una combinatoria argumento que establece esta?
Respuestas
¿Demasiados anuncios?
En su suma, que se distinguen entre la misma colección de números cuando se produce en diferentes órdenes. Así que usted tendrá diferentes sumandos para $(a_1,a_2,a_3,a_4)=(3,1,2,1)$, $(2,3,1,1)$, $(1,1,3,2)$ etc.
Dado un conjunto múltiple de $k$ números de la adición de a $n$ consta de $t_1$casos de $b_1$ a $t_j$ instancias de $b_j$, que contribuye $$\frac{k!}{t_1!\cdot\cdots\cdot t_j!}$$ (un coeficiente multinomial) sumandos de la suma, y por lo general contribución de $$\frac{1}{t_1!b_1^{t_1}\cdot\cdots\cdot t_j!b_j^{t_j}}$$ a la suma. Pero eso $1/n!$ veces el número de permutaciones con la estructura del ciclo de $b_1^{t_1}\cdot\cdots\cdots b_j^{t_j}$. Así que esta identidad establece que el número total de permutaciones de $n$ objetos es $n!$.
En breve, $n!$ veces sumando en la suma de anotar es igual al número de permutaciones en $n$ símbolos que descomponer en el producto de ciclos disjuntos de longitudes $a_1,\dots,a_k$. Más precisamente, esto es cierto si se combina todos los términos de la suma correspondiente a la misma conjunto múltiple $\{a_1,\dots,a_k\}$.
Vea los ejercicios 10.2 y 10.3 de estas notas para el material relacionado.
