Beweis Binomialkoeffizient Identität: ∑nk=0kk!nk(nk)=n∑k=0nkk!nk(nk)=n\sum_{k=0}^n\frac{kk!}{n^k}\binom{ n}{k}=n

Wie gewohnt lassen$[n]=\{1,2,\ldots,n\}$, und lass$S=[n]\cup\{0\}$. Lassen$F$sei die Menge der Funktionen aus$S$Zu$[n]$. Wenn$f\in F$, lassen

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

und lass$K(f)=\{f(\ell):\ell=0,\ldots,k-1\}$; beachten Sie, dass$|K(f)|=k(f)$.

Für$k\in S$lassen$F_k=\{f\in F:k(f)=k\}$. Für eine Funktion$f\in F_k$es gibt$\binom{n}k$Möglichkeiten, das Set zu wählen$K(f)$Und$k!$Bijektionen aus$\{0,\ldots,k-1\}$Zu$K(f)$, und da sind$n^{n-k}$Wege zu wählen$f(\ell)$für$\ell=k+1,\ldots,n$. Endlich gibt es$k$Wahlmöglichkeiten für$f(k)$, da es einer der sein muss$k$Mitglieder von$K(f)$. Daher,

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

Und

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

Andererseits ist das klar$|F|=n^{n+1}$, So

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

und die gewünschte Identität erhält man nun durch Division durch durch$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*}$$

Hier ist ein Weg, der dem von Brian M. Scott ähnelt, aber eine etwas andere Einstellung hat. Wir beweisen die äquivalente Identität

$$\sum_{k=1}^{n} \frac{k k!}{n^{k+1}} \binom{n}{k} = 1.$$ Angenommen, wir probieren $n+1$Mal aus einer Gruppe von $n$unterschiedliche Objekte. Das Schubladenprinzip sagt uns, dass die Wahrscheinlichkeit, einen Gegenstand zweimal auszuwählen, gleich groß ist $1$. Jetzt können wir auch über die Wahrscheinlichkeit nachdenken, dass unser erster Duplikat-Pick auf dem sein wird $k+1$Auswahl wo $k = 1, 2, \ldots n$. Das ist unser erstes $k$Picks sind unterschiedlich und die $k+1$st ist einer der ersten $k$. Unsere erste Wahl spielt keine Rolle, aber wir müssen uns dann entscheiden $k-1$verschiedene Objekte - dies hat Wahrscheinlichkeit $(n-1)(n-2) \ldots (n-k+1)/n^{k-1} = n!/(n^k (n-k)!)$gefolgt von einer Auswahl von einem der ersten $k$was Wahrscheinlichkeit hat $k/n$. Seit $k$reicht über $1$durch $n$die Wahrscheinlichkeit, irgendwo ein Duplikat zu bekommen, kann auch geschrieben werden $$\sum_{k=1}^n \frac{kn!}{n^{k+1} (n-k)!} = \sum_{k=1}^n \frac{k k!}{n^{k+1}} \binom{n}{k}$$