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\to \mathrm{\infty }$ :

$(\genfrac{}{}{0ex}{}{n}{k})\backsim \frac{n^k}{k!}$

Lösung von Tina

Asymptotische Gleichheit: für $n\to \mathrm{\infty }$ sind die beiden Ausdrücke irgendwann einmal gleich. Das heißt: $\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=1$

$a_n=(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\mathrm{...}(n-(k-1))}{k!}$ (= Definition des Binomialkoeffizienten)

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

$\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=\underset{n\to \mathrm{\infty }}{lim}\frac{\frac{n(n-1)\mathrm{...}(n-(k-1))}{k!}}{\frac{n^k}{k!}}=\underset{n\to \mathrm{\infty }}{lim}\frac{n\cdot (n-1)\mathrm{...}(n-(k-1))\cdot k!}{k!\cdot n^k}=$

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

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

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

$=\underset{n\to \mathrm{\infty }}{lim}\frac{n^k(1-\frac{1}{n})\mathrm{...}(1-\frac{k+1}{n})}{n^k}=(1-0)\cdot \mathrm{...}\cdot (1-0)=1$

Die beiden Ausdrücke sind asymptotisch gleich.