TU Wien:Analysis VU (diverse)/Übungen 2024S/Beispiel 102

Zeigen Sie die folgenden asymptotischen Beziehungen für die Anzahl der Kombinationen mit bzw. ohne Wiederholungen für festes $k$ und $n\to \infty$:

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Das folgende Dokument enthält die Lösung (Beispiel 500)

https://web.archive.org/web/*/www.informatik-forum.at/attachment.php?attachmentid=1097&d=1052595529

Lösungsvorschlag von Lit

Wir verwenden die Definition der asymptotischen Äquivalenz: $a_{n}\sim b_{n}\iff \lim \limits _{n\to \infty }{\frac {a_{n}}{b_{n}}}=1$

Einsetzen und umformen: $\lim \limits _{n\to \infty }{\frac {\frac {n!}{k!(n-k)!}}{\frac {n^{k}}{k!}}}=\lim \limits _{n\to \infty }{\frac {n!k!}{k!(n-k)!n^{k}}}=\lim \limits _{n\to \infty }{\frac {n!}{(n-k)!n^{k}}}$

Die Terme der Faktorielle im Nenner kürzen die der im Zähler von $n-k$ bis $1$ weg.

Es "fehlen" noch die $k$ Terme der Faktorielle zwischen $n$ und $n-k$.

Übrig bleibt also noch:

${\frac {n*(n-1)*\cdots *(n-k+1)}{n^{k}}}\iff$.

${\frac {n}{n}}*{\frac {n-1}{n}}*\cdots *{\frac {n-k+1}{n}}$

Für jeden dieser Terme gilt (mit konstanten, damit vernachlässigbaren, $x$, wobei $0\leq x<k$):

$\lim \limits _{n\to \infty }{\frac {n-x}{n}}=\lim \limits _{n\to \infty }{\frac {n}{n}}-{\frac {x}{n}}=1-0=1$

Die $k$ Faktoren wirken sich im Grenzwert (bzw. bei hinreichend großem $n$) also nicht mehr aus.

Daher ergibt sich für den gesamten Grenzwert $1^{k}*1=1$, was eine asymptotische Äquivalenz anzeigt. $\square$

Ist das formal korrekt? Feedback erwünscht. --Literallie (Diskussion) 17:00, 17. Apr. 2018 (CEST)