TU Wien:Analysis UE (diverse)/Übungen SS19/Beispiel 103

Aus VoWi
Zur Navigation springen Zur Suche springen

Zeigen Sie die folgende asymptotische Beziehung für die Anzahlen der Kombinationen mit bzw. ohne Wiederholungen für festes k und  n \to \infty:

\binom{n+k-1}{k} \sim \frac{n^k}{k!}

Lösungsvorschlag[Bearbeiten]

Wir wissen: a_n \sim b_n (a_n ist asymptotisch gleich b_n), falls \lim_{n \to \infty} \frac{a_n}{b_n} = 1. Dies brauchen wir nur noch auf die Angabe anwenden.

\binom{n}{k} = \frac{n(n-1)\cdots(n-(k-1))}{k!}

a_n = \binom{n + k - 1}{k} = \frac{(n+k-1)(n+k-2)\cdots(n+k-1-(k-1))}{k!}

Aus diesem Term kann man nun n herausheben:

\frac{n^k(1+\frac{k-1}{n})(1+\frac{k-2}{n})\cdots(1+\frac{k-k}{n})}{k!}

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

Wenn man nun den Grenzwert von \frac{a_n}{b_n} berechnet, kürzt sich n^k und k! weg. Die Brüche gehen gegen 0, wodurch nur mehr 1 übrig bleibt:

\lim_{n \to \infty} \frac{a_n}{b_n} = \lim_{n \to \infty} \left(\left(1 + \frac{k-1}{n}\right) \left(1 + \frac{k-2}{n}\right) \cdots  \left(1 + \frac{k-k}{n}\right) \right) = 1

Somit sind die beiden Terme asymptotisch gleich.

-- Berti933 (Diskussion) 12:44, 18. Mai 2015 (CEST)

Links[Bearbeiten]