(Para mi respuesta original, ver el final del post.)
Esta respuesta da una combinatoria argumento para ambas identidades, con las sugerencias anteriores. Se apoya en gran medida en las ideas de la Sección 12 en estas notas.
En primer lugar, si $X = \{1, 2, \ldots, n\}$, sabemos que hay $n^n$ funciones $\alpha:X \to X$.
Identidad de la primera: Cualquier función de $\alpha: X \to X$ puede ser representado como una etiqueta, en forma de grafo dirigido $G_\alpha$ con conjunto de vértices $X$ donde $(i,j)$ es una arista en el grafo si $\alpha(i) = j$. Supongamos que empezar en algún vértice $i \in G_\alpha$. Desde $X$ es finito, y cualquier vértice con $\alpha(j) = j$ tiene un auto-loop, si seguimos siguientes dirigida bordes en el gráfico de $i$ $\alpha(i)$ % # % y así sucesivamente -- debemos, finalmente, llegar a un vértice visitado ya. En otras palabras, cada suficientemente larga trayectoria en $\alpha(\alpha(i))$ termina en un ciclo. Esto significa que cada componente de $G_\alpha$ se compone de un conjunto de árboles conectado a un ciclo. (Un árbol, pueden consistir en un único nodo.) Por otra parte, podemos pensar de cada árbol como enraizada por el vértice, que es común para el árbol y el ciclo que termina en. (Véase, por ejemplo, la imagen en la parte inferior de la página 4 aquí.) Dado un conjunto de ciclos disjuntos es sólo una permutación, las raíces de los árboles junto con el conjunto de borde $G_\alpha$ por cada raíz $(i,j)$ forman una permutación de las etiquetas de las raíces. Por lo tanto, cualquier función de $i$ puede ser considerado como una permutación de los árboles (a través de sus raíces) en un bosque en el vértice set $\alpha: X \to X$.
Todo esto significa que únicamente pueden especificar una función de $\{1, 2, \ldots, n\}$ por
- La elección de un número de árboles de raíces y un conjunto múltiple de los tamaños de los árboles,
- La elección de una permutación del conjunto múltiple de árbol de tamaños,
- La distribución de las etiquetas de $\alpha: X \to X$ entre los árboles, y
- La elección de una etiqueta, arraigada estructura de árbol para cada elemento en el conjunto múltiple de árbol de tamaños.
Los pasos 1 y 2 corresponden a la elección de una $1, 2, \ldots, n$ $k$ tal que $i_1, i_2, \ldots, i_k$. Para el Paso 3, se están distribuyendo $i_1 + i_2 + \cdots + i_k = n$ etiquetas entre conjuntos de tamaño $n$, y por lo tanto el Paso 3 se puede hacer en $i_1, i_2, \ldots, i_k$ maneras. Para el Paso 4, de Cayley de la fórmula nos dice que hay $\binom{n}{i_1, i_2, \ldots, i_k} = \frac{n}{i_1! i_2! \cdots i_k!}$ etiquetado de los árboles con $n^{n-2}$ vértices. Desde allí se $n$ maneras de seleccionar una raíz, se $n$ arraigada, con la etiqueta de árboles con $n^{n-1}$ vértices. Por lo tanto, hay $n$ formas de realizar el Paso 4. Poniendo todo esto junto rendimientos
$i_1^{i_1-1} i_2^{i_2-1} \cdots i_k^{i_k-1}$$
Segunda identidad: Romper los componentes conectados de $$n^n=\sum\limits_{\substack{k,i_1,\ldots, i_k\ge1,\\ i_1+\cdots+i_k=n}}\frac{n!}{i_1!\cdots i_k!}i_1^{i_1-1}\cdots i_k^{i_k-1}.$ en dos grupos: 1) aquellas que terminan en un ciclo que consta de un solo vértice, y 2) los que terminan en un ciclo que consta de más de un vértice. Para el primer grupo, crear una nueva etiqueta el vértice. Adjuntar la raíz de cada árbol en el primer grupo a la nueva, sin etiquetar los vértices para crear un único árbol de raíces en el que todos los vértices, excepto la raíz están etiquetados. Dado que el segundo grupo no tiene vértices para que $G_\alpha$, se puede considerar como una función de $\alpha(i) = i$$\alpha':S \to S$, de tal manera que $S \subset X$ cualquier $\alpha'(i) \neq i$. Por lo tanto, podemos únicamente especificar una función de $i$ por
- Elegir un subconjunto $\alpha: X \to X$ $X-S$ a constar de los elementos en el primer grupo,
- La elección de un árbol de raíces estructura en $X$ en el que todos los vértices, excepto la raíz están etiquetados, y
- La elección de una función de $X-S$ sin puntos fijos.
Para un tamaño fijo $\alpha':S \to S$$k$, $X - S$ formas de realizar el Paso 1. Un árbol de raíces con las etiquetas de todos los vértices, excepto la raíz es equivalente a una totalmente marcadas árbol sin raíz, por lo que hay, por la fórmula de Cayley, $\binom{n}{k}$ formas de realizar el Paso 2. Por último, hay $(k+1)^{k-1}$ funciones de un conjunto de tamaño $(n-k-1)^{n-k}$ a sí mismo que no contienen puntos fijos. Poniendo todo esto junto rendimientos
$n-k$$
Respuesta Original:
La segunda igualdad se sigue de Abel variación sobre el teorema del binomio:
$$n^n =\sum\limits_{k=0}^n {n\choose k}(k+1)^{k-1}(n-k-1)^{n-k}.$$
Deje $$\sum_{k=0}^m \binom{m}{k} (w+m-k)^{m-k-1}(z+k)^k=w^{-1}(z+w+m)^m.$ para obtener
$m = n, w = 1, z = -1$$
Entonces, la nueva indexación de la suma a través de $$\sum_{k=0}^n \binom{n}{k} (n-k+1)^{n-k-1}(k-1)^k=n^n.$ los rendimientos de la segunda identidad
$k \to n-k$$
Para una breve prueba de Abel teorema del binomio, consulte este artículo reciente de Chu. Una generalización de la que también aparece en la Ecuación 5.64 en Concreto de las Matemáticas (2ª ed., p. 202).
