Prueba De Coeficiente Binomial De Identidad: $\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$

Question

Wolfram muestran que $\displaystyle\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$. haga clic para ver

Cómo demostrar esta identidad?

Gracias.

Answer 1

Como de costumbre, vamos a $[n]=\{1,2,\ldots,n\}$, y deje $S=[n]\cup\{0\}$. Deje $F$ el conjunto de funciones de$S$$[n]$. Si $f\in F$, vamos

$$k(f)=\min\{k\in S:\exists\ell<k\,(f(k)=f(\ell)\}\;,$$

y deje $K(f)=\{f(\ell):\ell=0,\ldots,k-1\}$; tenga en cuenta que $|K(f)|=k(f)$.

Para $k\in S$ deje $F_k=\{f\in F:k(f)=k\}$. Para una función de $f\in F_k$ hay $\binom{n}k$ formas para elegir el conjunto $K(f)$ $k!$ bijections de$\{0,\ldots,k-1\}$$K(f)$, y $n^{n-k}$ formas de elegir los $f(\ell)$$\ell=k+1,\ldots,n$. Por último, hay $k$ opciones para $f(k)$, ya que debe ser uno de los $k$ de los miembros de $K(f)$. Por lo tanto,

$$|F_k|=kk!n^{n-k}\binom{n}k\;,$$

y

$$|F|=\sum_kkk!n^{n-k}\binom{n}k\;.$$

Por otro lado, es claro que $|F|=n^{n+1}$, por lo que

$$\sum_kkk!n^{n-k}\binom{n}k=n^{n+1}\;,$$

y la identidad se obtiene dividiendo por $n^n$.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove armada]{{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#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{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{n}{k\, k! \over n^{k}}{n \choose k} = n:\ {\large ?}}$.

\begin{align} \sum_{k = 0}^{n}{k\, k! \over n^{k}}{n \choose k} & = n!\sum_{k = 0}^{n}{k \over n^{k}}{1 \over \pars{n - k}!} = n!\sum_{k = 0}^{n}{n - k \over n^{n - k}}\,{1 \over \bracks{n - \pars{n - k}}!} \\[5mm] & = {n! \over n^{n - 1}}\sum_{k = 0}^{n}{n^{k} \over k!} - {n! \over n^{n}}\sum_{k = 1}^{n}{n^{k} \over \pars{k - 1}!} = {n! \over n^{n - 1}}\sum_{k = 0}^{n}{n^{k} \over k!} - {n! \over n^{n}}\sum_{k = 0}^{n - 1}{n^{k + 1} \over k!} \\[5mm] & =\require{cancel} \cancel{{n! \over n^{n - 1}}\sum_{k = 0}^{n}{n^{k} \over k!}} - {n! \over n^{n - 1}}\pars{\cancel{\sum_{k = 0}^{n}{n^{k} \over k!}} - {n^{n} \over n!}} = \bbx{\ds{n}} \end{align}

Answer 3

$$\begin{align*} \sum\limits_{k=1}^n\frac{k\cdot k!}{n^k}\binom{n}{k}&=\int\limits_0^\infty e^{-t}t\left(\sum\limits_{k=1}^n\frac{kt^{k-1}}{n^k}\binom{n}{k}\right)dt\\ &=\int\limits_0^\infty e^{-t}t\left(1+\frac{t}{n}\right)^{n-1}dt\\ &=n^2\int\limits_0^\infty e^{-nt}t(1+t)^{n-1}dt\\ &=n^2\left(\int\limits_0^\infty e^{-nt}(1+t)^n dt-\int\limits_0^\infty e^{-nt}(1+t)^{n-1} dt\right)\\ &=n^2\left(\int\limits_0^\infty e^{-nt}(1+t)^n dt-\frac{1}{n}e^{-nt}(1+t)^n|_0^\infty-\int\limits_0^\infty e^{-nt}(1+t)^n dt\right)\\ &=n \end{align*}$$

Answer 4

Aquí está una manera que es similar a la de Brian M. Scott, pero un poco diferente. Vamos a comprobar el equivalente de identidad $$ \sum_{k=1}^{n} \frac{k k!}{n^{k+1}} \binom{n}{k} = 1. $$ Supongamos que tenemos una muestra de $n+1$ veces a partir de un grupo de $n$ distintos objetos. El principio del palomar nos dice que la probabilidad de escoger un objeto dos veces es $1$. Ahora también podemos pensar acerca de la probabilidad de que nuestro primer duplicado de recogida será en el $k+1$th en la selección del $k = 1, 2, \ldots n$. Esa es nuestra primera $k$ picks son distintos y el $k+1$st es uno de los primeros a $k$. Nuestra primera elección no importa pero entonces nos debe recoger $k-1$ distintos objetos, esto ha probabilidad de $(n-1)(n-2) \ldots (n-k+1)/n^{k-1} = n!/(n^k (n-k)!)$, seguido por una selección de uno de los primeros a $k$ a que la probabilidad de $k/n$. Desde $k$ rangos de $1$ a través de $n$ la probabilidad de obtener un duplicado de la somwhere también puede ser escrita $$ \sum_{k=1}^n \frac{kn!}{n^{k+1} (n-k)!} = \sum_{k=1}^n \frac{k k!}{n^{k+1}} \binom{n}{k} $$