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

Aus VoWi
Zur Navigation springen Zur Suche springen

(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[Bearbeiten]

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.