Buscar

Question

Voy a la universidad en octubre y pensé en ir a un par de preguntas de uno de sus últimos papeles. He completado la mayoría de esta pregunta, pero estoy atascado en la última parte. En la honestidad, he estado trabajando en este papel un tiempo y ahora estoy un poco cansado, así que probablemente estoy dando para arriba antes de lo habitual.

No voy a escribir la pregunta completa, sólo la última parte:

Deje $$S_r(n) = \sum_{m=0}^n\ (-1)^m m^r {n \choose m}$$ donde r es un entero no negativo . Mostrar que $S_r(n)=0$$r<n$. Evaluar $S_n(n)$.

Me han demostrado que $S_r(n)=0$ $r<n$ tomando $(1+z)^n= \sum_{m=0}^n\ z^m {n \choose m}$, dejando $D_r(f(z))=z\frac d{dz}(z\frac d{dz}...(\frac d{dz}(f(z)))...)$ donde $z\frac d{dz}$ se aplica $r$ veces y lo aplicó a ambos lados. El lado izquierdo da un polinomio, de grado n que tiene factor de $(1+z)$ todos los $r<n$ y el lado derecho da $\sum_{m=0}^n\ z^m (m)^r {n \choose m}$. Establecimiento $z=-1$ se obtiene el resultado requerido.

Hay algunas construir a esto, así que estoy bastante seguro de que esta era la intención de método.

Estoy atascado sin embargo en la última parte. He tratado de encontrar una forma para $D_r((1+z)^n)$, pero estoy bastante seguro de que este no es el enfoque correcto, ya que la redacción de la pregunta implica que $S_n(n)$ debe ser considerado por separado.

Estoy sorprendido de que yo no encuentro que esta cuestión ya había sido formulada, así que disculpas si ha sido.

Gracias.

Answer 1

La forma general de la suma

$$\sum_{m=0}^n(-1)^mm^n\binom{n}m\;,\tag{1}$$

con la alternancia de signo y el coeficiente binomial $\binom{n}m$, sugiere que puede ser interpretado como una inclusión-exclusión en el cálculo. Sin embargo, el $m=0$ plazo es $0$, a partir de la cual comenzamos por la sustracción de una cantidad positiva $\binom{n}1=n$, lo cual es un poco extraño para dicho cálculo. Esto sugiere dejando $k=n-m$, y reescribir como

$$\sum_{k=0}^n(-1)^{n-k}(n-k)^n\binom{n}{n-k}=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\;,$$

donde la derecha ha sido diseñado para parecerse a un más o menos típico de inclusión-exclusión en el cálculo. El factor de $(n-k)^n$ es el que no es parte de la inclusión-exclusión de la maquinaria. Tiene una interpretación natural como el número de funciones de $[n]$ $[n]$cuyos rangos son distintos de algunas $k$-elemento subconjunto de $[n]$. Si para cada una de las $k\in[n]$ dejamos $F_k$ el conjunto de funciones de $[n]$ $[n]$cuyos rangos no contienen $k$, tenemos

$$\left|\bigcap_{k\in I}F_k\right|=(n-|I|)^n$$

siempre que $\varnothing\ne I\subseteq[n]$, por lo que

$$\begin{align*} \left|\bigcup_{k=1}^nF_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}\left|\bigcap_{k\in I}F_k\right|\\ &=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}(n-|I|)^n\\ &=\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n\;. \end{align*}$$

Este es el número de funciones de $[n]$ $[n]$que no son surjective, es decir, el número de los que no bijections. De ello se deduce que el número de bijections de $[n]$ $[n]$es

$$n^n-\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\;.$$

Por otro lado, sabemos que hay $n!$ bijections de$[n]$$[n]$, por lo que

$$\sum_{m=0}^n(-1)^mm^n\binom{n}m=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n=(-1)^nn!\;.$$

Tenga en cuenta que el mismo argumento se encarga de la parte anterior del problema. El factor de $(n-k)^n$ es reemplazado por $(n-k)^r$, el número de funciones de $[r]$ $[n]$cuyos rangos son distintos de algo de lo especificado $k$-elemento subconjunto de $[n]$. La expresión

$$\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^r$$

cuenta la surjective funciones de$[r]$$[n]$, y si $r<n$, esto es, por supuesto,$0$.

Todo esto está muy estrechamente relacionado con los números de Stirling del segundo tipo.

Answer 2

La siguiente relación encapsula la semántica del número de Stirling:

PS

Esto rinde por su suma.

$$ S_r (n) = r! [z ^ r] \ sum_ {m = 0} ^ n {n \ elige m} (-1) ^ m \ exp (mz) = r! [z ^ r] (1- \ exp (z)) ^ n. $$

Ahora observa que

PS

lo que significa que$$m^r = r! [z^r] \exp(mz).$ comienza en$$1-\exp(z) = - z - \frac{z^2}{2} - \frac{z^3}{6} -\cdots$ donde$(1-\exp(z))^n$ con coeficiente$[z^r]$, produciendo para la suma el valor

PS

y los coeficientes en$r=n$ con$(-1)^n$ son cero.