Cómo mostrar $\sum_{k=1}^n \binom{n-1}{k-1} n^{n-k} k! = n^n$

Question

A mí me parece que la prepa es una elegante manera de contar todas las funciones de$[n]$$[n]$. He intentado varios métodos, incluyendo la interpretación de $\binom{n-1}{k-1}$ como el número de soluciones para $n=x_1+\dots +x_k$ donde $\forall_i x_i \ge 1$. Pero no me prestas a algo importante.

Agradecería algunos consejos o soluciones para esto.

Answer 1

El uso de la repetición para el Triángulo de Pascal y una suma telescópica, $$ \begin{align} \sum_{k=1}^n\binom{n-1}{k-1}\frac{k!}{n^k} &=\sum_{k=1}^n\left[\binom{n}{k}-\binom{n-1}{k}\right]\frac{k!}{n^k}\\ &=\sum_{k=1}^n\binom{n-1}{k-1}\frac{(k-1)!}{n^{k-1}}-\sum_{k=1}^n\binom{n-1}{k}\frac{k!}{n^k}\\ &=\sum_{k=0}^{n-1}\binom{n-1}{k}\frac{k!}{n^k}-\sum_{k=1}^n\binom{n-1}{k}\frac{k!}{n^k}\\[6pt] &=1-0\tag{1} \end{align} $$ Multiplicar $(1)$ $n^n$ y obtenemos $$ \sum_{k=1}^n\binom{n-1}{k-1}n^{n-k}k!=n^n\etiqueta{2} $$

Answer 2

Que es una consecuencia de la de Abel-Hurwitz fórmula.

La LHS, puede ser visto como $(n-1)!$ multiplicado por el coeficiente de $x^n$ en el producto entre $$ \sum_{k\geq 0} k x^k=\frac{x}{(1-x)^2},\qquad \sum_{k\geq 0}\frac{n^k x^k}{k!}=e^{nx}. $$

Answer 3

$n^n$ es el número de listas de longitud $n$ cuyas entradas son tomadas de $1,2\dots n$.

Deje $S_k$ ser el conjunto de listas cuyo primer $k$ elementos son pares distintos, pero cuya primera $k+1$ elementos no son (con la convención de que las $S_n$ es sólo el conjunto de listas sin repeticiones). Los conjuntos de $S_k$ $k=1,\dots,n$ son una partición del conjunto de todas las $n^n$ listas. Por lo tanto, lo que demuestra que $|S_k|=\binom{n-1}{k-1}k!n^{n-k}$ demuestra su fórmula.

Answer 4

$\newcommand{\ángulos}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#f00}{\sum_{k = 1}^{n}{n - 1 \choose k - 1}n^{n - k}\,\, k!} & = n^{n}\sum_{k = 0}^{n - 1}{n - 1 \choose k}{\pars{k + 1}! \over n^{k + 1}} \\[5mm] & = n^{n}\sum_{k = 0}^{n - 1}{n - 1 \choose k}\pars{k + 1}!\ \overbrace{% {1 \over \Gamma\pars{k + 1}}\int_{0}^{\infty}t^{k}\expo{-nt}\,\dd t} ^{\ds{\,\,\,\,\,\,=\ {1 \over n^{k + 1}}}} \\[5mm] & = n^{n}\int_{0}^{\infty}\expo{-nt} \sum_{k = 0}^{n - 1}{n - 1 \choose k}\pars{k + 1}t^{k}\,\dd t \\[5mm] & = n^{n}\int_{0}^{\infty}\expo{-nt}\pars{1 + t}^{n - 2}\pars{1 + nt}\,\dd t \\[5mm] & = n^{n}\color{#f00}{\expo{n}}\bracks{% n\int_{1}^{\infty}{\expo{-nt} \over t^{1 - n}}\,\dd t -\pars{n - 1}\int_{1}^{\infty}{\expo{-nt} \over t^{2 - n}}\,\dd t} \label{1}\tag{1} \end{align} La integración por partes de la RHS primera integral: \begin{align} n\int_{1}^{\infty}{\expo{-nt} \over t^{1 - n}}\,\dd t & = -\int_{t\ =\ 1}^{t\ \to\ \infty}{\dd\expo{-nt} \over t^{1 - n}} = \expo{-n} + \pars{n - 1}\int_{1}^{\infty}{\expo{-nt} \over t^{2 - n}}\,\dd t \\ & \mbox{} \end{align} \begin{equation} \mbox{such that}\quad n\int_{1}^{\infty}{\expo{-nt} \over t^{1 - n}}\,\dd t -\pars{n - 1}\int_{1}^{\infty}{\expo{-nt} \over t^{2 - n}}\,\dd t = \color{#f00}{\expo{-n}} \label{2}\tag{2} \end{equation}

---

Con \eqref{1} y \eqref{2}: $$ \color{#f00}{\sum_{k = 1}^{n}{n - 1 \elegir k - 1}n^{n - k}\,\, k!} = \color{#f00}{n^{n}} $$