Identidad del coeficiente binomial de prueba: ∑nk=0kk!nk(nk)=n∑k=0nkk!nk(nk)=n\sum_{k=0}^n\frac{kk!}{n^k}\binom{ n}{k}=n

como de costumbre deja$[n]=\{1,2,\ldots,n\}$, y deja$S=[n]\cup\{0\}$. Dejar$F$Sea el conjunto de funciones de$S$a$[n]$. Si$f\in F$, dejar

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

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

Para$k\in S$dejar$F_k=\{f\in F:k(f)=k\}$. Para una función$f\in F_k$hay$\binom{n}k$formas de elegir el conjunto$K(f)$y$k!$biyecciones de$\{0,\ldots,k-1\}$a$K(f)$, y aquí están$n^{n-k}$maneras de elegir$f(\ell)$para$\ell=k+1,\ldots,n$. Finalmente, hay$k$opciones para$f(k)$, ya que debe ser uno de los$k$miembros de$K(f)$. De este modo,

$$|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}$, entonces

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

y la identidad deseada ahora se obtiene dividiendo entre$n^n$.

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}[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}{\partial #3^{#1}}} \newcommand{\root}[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}$$

$$\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*}$$

Aquí hay una manera que es similar a la de Brian M. Scott pero con una perspectiva ligeramente diferente. Probamos la identidad equivalente

$$\sum_{k=1}^{n} \frac{k k!}{n^{k+1}} \binom{n}{k} = 1.$$ Supongamos que muestreamos $n+1$veces de un grupo de $n$objetos distintos. El principio del casillero nos dice que la probabilidad de elegir un objeto dos veces es $1$. Ahora también podemos pensar en la probabilidad de que nuestra primera selección duplicada esté en el $k+1$ª selección donde $k = 1, 2, \ldots n$. Esa es nuestra primera $k$las selecciones son distintas y las $k+1$st es uno de los primeros $k$. Nuestra primera elección no importa, pero luego debemos elegir $k-1$objetos distintos -- esto tiene probabilidad $(n-1)(n-2) \ldots (n-k+1)/n^{k-1} = n!/(n^k (n-k)!)$seguido de una selección de uno de los primeros $k$que tiene probabilidad $k/n$. Desde $k$se extiende sobre $1$a través de $n$la probabilidad de obtener un duplicado en algún lugar también se puede escribir $$\sum_{k=1}^n \frac{kn!}{n^{k+1} (n-k)!} = \sum_{k=1}^n \frac{k k!}{n^{k+1}} \binom{n}{k}$$