TU Wien:Analysis UE (diverse)/Übungen WS11/Beispiel 64

(64-65) Zeigen Sie die folgende asymptotische Beziehung für die Anzahlen der Kombinationen mit bzw. ohne Wiederholungen für festes $k$ und $n\rightarrow \infty$ :

${\binom {n}{k}}\backsim {\frac {n^{k}}{k!}}$

Lösung von Tina

Asymptotische Gleichheit: für $n\rightarrow \infty$ sind die beiden Ausdrücke irgendwann einmal gleich. Das heißt: $\lim _{n\rightarrow \infty }{\frac {a_{n}}{b_{n}}}=1$

$a_{n}={\binom {n}{k}}={\frac {n(n-1)...(n-(k-1))}{k!}}$ (= Definition des Binomialkoeffizienten)

$b_{n}={\frac {n^{k}}{k!}}$

$\lim _{n\rightarrow \infty }{\frac {a_{n}}{b_{n}}}=\lim _{n\rightarrow \infty }{\frac {\frac {n(n-1)...(n-(k-1))}{k!}}{\frac {n^{k}}{k!}}}=\lim _{n\rightarrow \infty }{\frac {n\cdot (n-1)...(n-(k-1))\cdot k!}{k!\cdot n^{k}}}=$

$k!$ kürzen, $n$ aus allen Klammern herausheben:

$=\lim _{n\rightarrow \infty }{\frac {n\cdot n(1-{\frac {1}{n}})\cdot n(1-{\frac {2}{n}})\cdot n(1-{\frac {3}{n}})...\cdot n(1-{\frac {k+1}{n}})}{n^{k}}}=$

$n$ kommt im Nenner $k$-mal vor

$=\lim _{n\rightarrow \infty }{\frac {n^{k}(1-{\frac {1}{n}})...(1-{\frac {k+1}{n}})}{n^{k}}}=(1-0)\cdot ...\cdot (1-0)=1$

Die beiden Ausdrücke sind asymptotisch gleich.