Ungleichung Kombinatorik

29.04.2016, 17:26

Shalec

Ungleichung Kombinatorik

Hallo,
laut dem Übungsblatt gilt:
$\begin{eqnarray*} n^k \geq \frac{n!}{(n-k)!}\geq \begin{pmatrix} n+k-1\\ k\end{pmatrix} \geq \begin{pmatrix}n\\ k\end{pmatrix} \end{eqnarray*}$
insofern die Aufgabe korrekt interpretiert wurde. Es gibt nämlich mehrere Interpretationsmöglichkeiten der Aufgabe - sie ist nicht eindeutig.
Die Aufgabe lautet (bezogen auf http://www.math.uni-bremen.de/~dickhaus/...kript-stoch.pdf ) "Die vier Ausdrücke aus Schema 2.10 (S. 22) im Skript sind für alle zulässigen Werte von n und k stets in der gleichen Weise ihrer Größe nach geordnet."
Nun ist natürlich die Leserichtung einer Tabelle nicht eindeutig definiert. Angesichts von P P* und C sowie C* machte für mich obrige Aufreihung sinn.

Könnte mir hier jemand Hinweise geben, wie sich die Ungleichungen begründen, nicht unbedingt beweisen lassen?

29.04.2016, 17:51

HAL 9000

Auf diesen Beitrag antworten »

Die Beweise für erste und letzte Ungleichung sind offensichtlich, interessant ist nur die mittlere:

Für diese sehen wir zunächst, dass für $\begin{align*} 1\leq j<n \end{align*}$ die Ungleichung $\begin{align*} (j-1)(n-j-1)\geq 0 \end{align*}$ gilt, umgestellt zu $\begin{align*} j(n-j+1)\geq n+j-1 \end{align*}$ bzw. $\begin{align*} n-j+1 \geq \frac{n+j-1}{j} \end{align*}$ . Multipliziert von $\begin{align*} j=1\ldots k \end{align*}$ ergibt dies $\begin{align*} \frac{n!}{(n-k)!} \geq \binom{n+k-1}{k} \end{align*}$ . Klappt so allerdings nur für $\begin{align*} k\leq n-1 \end{align*}$ , für $\begin{align*} k=n \end{align*}$ muss man sich noch was ausdenken.

EDIT: Für $\begin{align*} 2\leq n\leq 5 \end{align*}$ sowie $\begin{align*} k=n \end{align*}$ ist die mittlere Ungleichung FALSCH, für $\begin{align*} n=k\geq 6 \end{align*}$ stimmt sie aber wieder. Augenzwinkern

Da $\begin{align*} 2\leq n=k\leq 5 \end{align*}$ nun aber durchaus "zulässige Werte" sind, erweist sich die Aussage

Zitat:

Original von Shalec
"Die vier Ausdrücke aus Schema 2.10 (S. 22) im Skript sind für alle zulässigen Werte von n und k stets in der gleichen Weise ihrer Größe nach geordnet."

als Unfug.

30.04.2016, 13:18

Shalec

Auf diesen Beitrag antworten »

Oha.. vielen Dank. Mit solch umfangreicher Antwort und Hilfestellung hatte ich nicht gerechnet. Ich werde das aber in jedem Fall nachrechnen.

Aber mal zur Aufgabeninterpretation: Hättest du diese Aufgabe ebenfalls so interpretiert wie ich?

Viele Grüße und vielen Dank.

30.04.2016, 14:14

HAL 9000

Auf diesen Beitrag antworten »

In dem Skript habe ich nur die bekannten vier Kombinatorik-Anzahlformeln gefunden, nicht aber dies:

Zitat:

Original von Shalec
"Die vier Ausdrücke aus Schema 2.10 (S. 22) im Skript sind für alle zulässigen Werte von n und k stets in der gleichen Weise ihrer Größe nach geordnet."

Insofern kann ich nicht einschätzen, ob du die tatsächliche Aufgabenstellung richtig (und vollständig!) wiedergegeben hast.

30.04.2016, 16:21

Shalec

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
In dem Skript habe ich nur die bekannten vier Kombinatorik-Anzahlformeln gefunden, nicht aber dies:

Zitat:

Original von Shalec
"Die vier Ausdrücke aus Schema 2.10 (S. 22) im Skript sind für alle zulässigen Werte von n und k stets in der gleichen Weise ihrer Größe nach geordnet."

Insofern kann ich nicht einschätzen, ob du die tatsächliche Aufgabenstellung richtig (und vollständig!) wiedergegeben hast.

Das Zitat ist 1-zu-1 vom dazugehörigen Aufgabenzettel abgetippt. Unter der Annahme, dass dies fehlerfrei ist, ließe sich dann die Aufgabe entsprechend oder eindeutig interpretieren?

30.04.2016, 17:54

HAL 9000

Auf diesen Beitrag antworten »

Eigentlich habe ich alles gesagt: Für $\begin{align*} 2\leq n=k\leq 5 \end{align*}$ ist

$\begin{align*} \frac{n!}{(n-k)!} < \binom{n+k-1}{k} \end{align*}$ ,

während für alle anderen $\begin{align*} n,k \end{align*}$ mit $\begin{align*} 0\leq k\leq n \end{align*}$ die gegenteilige Ungleichung

$\begin{align*} \frac{n!}{(n-k)!} \geq \binom{n+k-1}{k} \end{align*}$

gilt. Insofern stimmt die von die in der Aufgabenstellung getroffene Aussage in dieser Allgemeinheit "für alle zulässigen Werte von n und k" nicht.

Neue Frage »

Antworten »

Ungleichung Kombinatorik

Verwandte Themen