Diferenciando el teorema del binomio

Question

El estándar de la identidad $$ n2^{n-1} = \sum_{k=0}^n k\binom{n}{k} $$ tiene una fácil interpretación combinatoria, que es que ambos lados contar el número de formas de seleccionar un subconjunto de a$[n]$, con un marcado elemento. Alternativamente, podríamos mirar $$ \frac{d}{dx}(x+1)^n = \frac{d}{dx}\left(\sum_{k=0}^n \binom{n}{k}x^k\right) $$ y, a continuación, sustituya $x=1$ para obtener la misma identidad. Podemos pensar en esto como la diferenciación de movimiento entre el conteo de conjuntos y contando "señalado", que es lo que hicimos anteriormente sin la analítica de la maquinaria. Esta es una instancia específica de un hecho acerca de la generación de funciones.

Si en lugar de mirar $$ \frac{d^n}{dx^n}(e^x - 1) = \frac{d^n}{dx^n}\left( \sum_{k=0}^n\binom{n}{k}(-1)^{n-k}e^{kx} \right) $$ y el sustituto de la $x=0$ tenemos otro conocido de identidad (un caso especial de la inclusión-exclusión de la fórmula para el número de surjections) $$ n! = \sum_{k=1}^n (-1)^{n-k}\binom{n}{k}k^n $$ Mi pregunta es si esta derivación es un ejemplo de una más general técnica o tiene algún significado. Yo no soy buena en la generación de funciones, por lo que parece un poco misterioso.

Answer 1

Tomando la derivada $n$ veces y establecimiento $x = 0$ le da el coeficiente de $x^n$ en la exponencial de la generación de la función:

$$ f(x) = \sum_{k = 0}^\infty f^{(k)}(0) \frac{x^k}{k!}. $$

Es típico de escribir esto, como en términos del coeficiente de operador $\left[ \frac{x^n}{n!} \right]$, que cuando se aplica a una potencia de la serie $f(x)$ le da el coeficiente de $\frac{x^n}{n!}$$f(x)$. En otras palabras

$$\left[ \frac{x^n}{n!} \right] \sum_{k = 0}^\infty a_k \frac{x^k}{k!} = a_n. $$

Entonces

\begin{align} \sum_{k = 0}^n \binom{n}{k} (-1)^{n - k}k^n &= \sum_{k = 0}^n \binom{n}{k} (-1)^{n - k} \left[ \frac{x^n}{n!} \right] e^{kx} \\ &= \left[ \frac{x^n}{n!} \right]\sum_{k = 0}^n \binom{n}{k} (-1)^{n - k} e^{kx} \\ &= \left[ \frac{x^n}{n!} \right] (e^x - 1)^n. \end{align}

En la teoría de la combinatoria de las especies, $e^x - 1$ el (exponencial) de generación de la función para la que no está vacía de conjuntos. Es decir, en el mapa que se lleva en un conjunto $X$ y escupe el conjunto de

$$ \mathcal{E}(X) = \begin{cases} \{X\} & \text{if } X \ne \emptyset \\ \emptyset & \text{if } X = \emptyset \end{cases}. $$

Observe que

$$ |\mathcal{E}(X)| = \begin{cases} 1 & \text{if } X \ne \emptyset \\ 0 & \text{if } X = \emptyset \end{cases} $$

Definimos la generación de la función de $\mathcal{E}$

$$ \sum_{n = 0}^\infty |\mathcal{E}([n])| \frac{x^n}{n!} = e^x - 1 $$

donde $[n] = \{1, 2, \dots, n\}$.

Si $\mathcal{F}$ es una combinatoria de las especies, a continuación, definimos el poder $\mathcal{F}^k$ a ser el mapa

$$ \mathcal{F}^k(X) = \bigsqcup_{(S_1,\dots,S_k)} \mathcal{F}(S_1) \times \dots \times \mathcal{F}(S_k) \tag{1}$$

cuando la unión está por encima de todas (ordenada) de las particiones de $X$ a $k$ subconjuntos $S_1,\dots,S_k$. Es decir, $S_1 \cup \dots \cup S_k = X$ $S_1,\dots,S_k$ son disjuntas.

Uno puede mostrar que si $F(x) = \sum_n |\mathcal F([n])| x^n/n!$ es la generación de la función de $\mathcal{F}$ $F(x)^k$ es la generación de la función de $\mathcal{F}^k$.

Traer de regreso a $\mathcal{E}^n$ podemos decir que

$$ \left[ \frac{x^n}{n!} \right] (e^x - 1)^n = |\mathcal{E}^n([n])| $$ es el número de maneras de particionamiento $[n]$ a $n$-no-vacío series porque sólo los términos en $(1)$ que $S_1,\dots,S_n$ son todos los no-vacío va a contribuir a la unión.

Particionamiento $[n]$ a $n$ singleton es la misma cosa como una permutación de $n$ e hay $n!$ de estos. Por lo tanto

$$n! = \left[ \frac{x^n}{n!} \right] (e^x - 1)^n = \sum_{k = 0}^n \binom{n}{k} (-1)^{n - k}k^n. $$