Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Näherung Binomialkoeffizient n,k groß: (n*e/k)^k

Näherung Binomialkoeffizient n,k groß: (n*e/k)^k

Universität / Fachhochschule

Funktionen

Grenzwerte

Tags: Asymptotisches Verhalten, Binomialkoeffizient, Funktion, Grenzwert, Näherung

MrSpecks aktiv_icon

16:18 Uhr, 25.10.2021

Mir ist folgende Näherung untergekommen und ich weiß leider nicht so recht, weshalb diese so stimmen sollte:

die Voraussetzungen sind:

n, k groß
(asymptotisches Verhalten), die Ungleichung die umgeschrieben wird lautet:

n > > (\binom{n}{k}) * 2^{1 - (\binom{k}{2})}

Die Näherung, welche verwendet wird, um daraus einen schöneren Ausdruck zu erhalten und über die ich mir nicht im klaren bin lautet:

(\binom{n}{k}) = \frac{n!}{k! * (n - k)!} \approx \frac{n^{k}}{k^{k} * e^{- k}}

Hat diese einen Namen oder einen leicht einzusehenden Ursprung?

Danke schonmal für Hinweise.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Grenzwert (Mathematischer Grundbegriff)
Regel von l'Hospital (Mathematischer Grundbegriff)
Wichtige Grenzwerte
Funktion (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Ableiten mit der h-Methode
Einführung Funktionen
Grenzwerte - Linksseitiger/rechtsseitiger Grenzwert an einer Polstelle
Grenzwerte - Verhalten im Unendlichen

Ableiten mit der h-Methode
Einführung Funktionen
Grenzwerte - Linksseitiger/rechtsseitiger Grenzwert an einer Polstelle

Zu diesem Thema passende Musteraufgaben einblenden

Ableitung an einer Stelle

Wie bestimmt man die Ableitung

f' (x)

einer Funktion

f (x)

an der Stelle

x_{0}

Grenzwert einer Funktion

Wie bestimmt man den Grenzwert einer Funktion?

Grenzwert mit l'Hospital bestimmen

Wie bestimmt man einen Grenzwert mit der Regel von l'Hospital?

Wie bestimmt man einen Grenzwert, bei dem

\frac{0}{0}

oder

\frac{\infty}{\infty}

herauskommt?

Kurvendiskussion einer ganzrationalen Funktion 3. Grades

Wie führt man eine Kurvendiskussion einer ganzrationalen Funktion 3. Grades durch?

Kurvendiskussion einer ganzrationalen Funktion 5. Grades

Wie führt man eine Kurvendiskussion einer ganzrationalen Funktion 5. Grades durch?

DrBoogie aktiv_icon

16:23 Uhr, 25.10.2021

Ja, Stirling-Formel:
de.wikipedia.org/wiki/Stirlingformel

HAL9000

16:45 Uhr, 25.10.2021

Aber nur sehr grob: Für Stirling müsste noch ein

\sqrt{2 π k}

in den Nenner.

Es fehlt mir ein wenig Information, um welchen Grenzübergang für

n, k

es hier genau geht: Selbst mit der Stirlingkorrektur im Nenner gilt diese Näherung asymptotisch nur für

k \to \infty

bei gleichzeitigem

\frac{n}{k^{2}} \to \infty

MrSpecks aktiv_icon

17:14 Uhr, 25.10.2021

Danke für die Beiträge. Offensichtlich scheint mir nur die Aussage:

(\binom{n}{k}) < (\frac{n e}{k})^{k}

. Das ergibt sich mithilfe der Stirlingformel recht einfach via:

(\binom{n}{k}) < \frac{n^{k}}{k!} < (s t i r l i n g) \frac{n^{k}}{\sqrt{2 π k} (\frac{k}{e})^{k}} < \frac{n^{k}}{(\frac{k}{e})^{k}}

Das ist in dem Kontext aber wenig hilfreich, da wir ja an

(\binom{n}{k}) > (\frac{n e}{k})^{k}

oder

(\binom{n}{k}) \approx (\frac{n e}{k})^{k}

interessiert sind (siehe ungleichung). Also im Grunde nicht so recht sinnvoll. Mit der Aussage von
@HAL9000 allerdings könnte was draus werden, denn:

Es geht darum ein Maximum für

n - (\binom{n}{k}) \cdot 2^{1 - (\binom{k}{2})}

zu finden für große n,k.
Für große n gilt (erstmal intuitiv) wohl tatsächlich:

n > > k^{2}

.
Der Faktor

\sqrt{2 π k}

kann vernachlässigt werden, da wir letztendlich die k(-1)-te Wurzel ziehen, um auf n zu kommen.

MrSpecks aktiv_icon

17:23 Uhr, 25.10.2021

Etwas Präziser:
k ist fest und wird groß, n(k) maximiert den o.g. Ausdruck.

HAL9000

17:45 Uhr, 25.10.2021

Deine Binomialkoeffizienten scheinen verunstaltet zu sein... Also mal von vorn:

Es geht um

f (n, k) = n - (\begin{array}{c} n \\ k \end{array}) \cdot 2^{1 - \frac{k}{2}}

, richtig?

Es gibt kein Maximum für große

n, k

, denn es ist beispielsweise

f (n, n) = n - 2^{1 - \frac{n}{2}}

, und das wächst unbeschränkt. Also was genau willst du: Das Maximum über

k

bei festem

n

? Irgendwie macht das bisher für mich keinen Sinn.

EDIT: Ah Ok, das 17:23 hatte ich noch gar nicht gesehen. Also Maximierung bzgl.

n

bei festem

k

MrSpecks aktiv_icon

17:58 Uhr, 25.10.2021

f(k,n) ist richtig, wobei die Funktion in Abhängigkeit von k zum maximieren ist, d.h. bei festem, großen k ist das n(k) zu finden, s.d. f(k, n(k)) maximal.

HAL9000

18:02 Uhr, 25.10.2021

n \mapsto f (n, k)

wächst solange, wie die Differenz

g (n) := f (n + 1, k) - f (n, k) = 1 - ((\begin{array}{c} n + 1 \\ k \end{array}) - (\begin{array}{c} n \\ k \end{array})) \cdot 2^{1 - \frac{k}{2}} = 1 - (\begin{array}{c} n \\ k - 1 \end{array}) \cdot 2^{1 - \frac{k}{2}}

positiv ist. Zunächst ist

g (n) = 1

für alle

n < k - 1

, also Wachstum. Darüber hinaus ist

g (n)

für

n \geq k

dann streng monoton fallend, und wird irgendwann die Null unterschreiten - direkt davor ist die Maximumstelle von

n \to f (n, k)

.

Von

n ≫ k^{2}

für die Maximumstelle

n

kann nicht im geringsten die Rede sein. Ich fürchte, du bist mit deinen Näherungen total auf dem falschen Dampfer. :(

MrSpecks aktiv_icon

18:24 Uhr, 25.10.2021

Desto mehr ich hier hantiere, desto eher beschleicht mich dieses Gefühl auch... werde wohl nochmal Rücksprache mit dem Auftraggeber halten müssen...

HAL9000

18:26 Uhr, 25.10.2021

Nach einigen Testfällen zu urteilen scheint in einem weiten

k

-Parameterbereich die

n

-Maximumstelle eher in der Nähe von

1.1 \cdot k

zu liegen, d.h. ca. 10% größer.

MrSpecks aktiv_icon

18:41 Uhr, 25.10.2021

Danke für den Aufwand. Mir ist grade aufgefallen:
Im Exponenten der 2 in f(k,n(k)) steht k ÜBER 2 (wie oben angegeben) und nicht k/2! Etwas ungünstig zu lesen. Damit ergeben sich durch kurzes Ausprobieren gänzlich andere Verhältnisse, z.B für
k=20 ist

n > 7800

. Damit auch

n > > k^{2}

HAL9000

18:59 Uhr, 25.10.2021

> Mir ist grade aufgefallen: Im Exponenten der 2 in f(k,n(k)) steht k ÜBER 2 (wie oben angegeben) und nicht k/2! E

Danke und Tschüss: Die ganze Arbeit wieder mal im Arsch, weil bei der Formeldarstellung rumgeschlampt wird.

> wie oben angegeben) un

Nirgendwo ist oben ein Binomialkoeffizient im Exponenten der Zweierpotenz zu lesen. Jedenfalls nicht mit meinem Browser. :(

MrSpecks aktiv_icon

19:02 Uhr, 25.10.2021

Tut mir leid. Darstellung liegt wohl am Browser, hier passt das alles.

Werde die Tage nochmal die Lösung hier hochladen, wenn ich sicher bin.

HAL9000

19:20 Uhr, 25.10.2021

Mit Firefox sehe ich in keinem deiner Beiträge irgendwelche Binomialkoeffizienten.

Genau wegen dieser Darstellungsprobleme hier auf onlinemathe verwende ich schon seit längerer Zeit das aufwändige Konstrukt

\left(\begin{array}{c}n\\ k\end{array}\right)

statt {n\choose k} um Binomialkoeffizienten darzustellen.

HAL9000

22:51 Uhr, 25.10.2021

Also gut,

f (n, k) = n - (\begin{array}{c} n \\ k \end{array}) \cdot 2^{1 - (\begin{array}{c} k \\ 2 \end{array})} = n - (\begin{array}{c} n \\ k \end{array}) \cdot 2^{1 - \frac{k (k - 1)}{2}}

und damit dann

g (n) := f (n + 1, k) - f (n, k) = 1 - (\begin{array}{c} n \\ k - 1 \end{array}) \cdot 2^{1 - \frac{k (k - 1)}{2}}

Wenn ich richtig abgeschätzt habe, dann sollte für große

k

die

n

-Maximumstelle von

f

etwa bei

2^{\frac{k}{2}} \cdot \frac{k}{e}

liegen.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1543253

1543209

	Status: nicht eingeloggt	Noch nicht registriert?