Abschätzung Binomialkoeffizient?

Question

Hallo, ich bin auf folgendes Problem gestoßen:

Wenn ich eine Menge mit n Elementen betrachte und ein Teilmengensytem darüber betrachte, in dem jedes Element (Menge) 2*k-1 Elemente enthält (k bezeichnet eine Primzahl)... dann ist die Summe der Binomialkoeffizienten der Form n über i, wobei i von 0 bis k-1 betrachtet wird, DEUTLICH kleiner als n über (2*k-1), also die Zahl aller (2*k-1)-elementigen Teilmengen. Dies wird in meiner Vorlesung als offensichtlich angesehen. Für mich ist es jedoch nicht offensichtlich, weshalb eine Summe von k Binomialkoeffizienten, also quasi von k Mengensystemen mit Mengen bis Größe k-1, so viel kleiner sein soll als n über 2*k-1. Kann mir das vielleicht jemand erklären?

Answer 1

die Summe der Binomialkoeffizienten der Form n über i, wobei i von 0 bis k-1 betrachtet wird, DEUTLICH kleiner als n über (2*k-1)

Wähle \(n = 4, k=2\). Dann ist \(\sum\limits_{i=0}^{k-1}{n\choose i} = 5 \nless 4 = {n\choose 2k-1}\)

Irgendetwas stimmt an deiner Behauptung nicht.

Comments

Vielen Dank für die Antwort!

Es geht eigentlich um eine Abschätzung der Anzahl der Elemente eines Mengensystems von (2*k-1)-elementigen Teilmengen über einer n-elementigen Menge. Dabei wurde gefordert, dass der Schnitt von zwei Elementen des Systems nicht genau k-1 sein darf.

Dann sagt dieser Satz, dass diese Anzahl durch die eingangs beschriebene Summe beschränkt ist, und dass man daran erkennen könne, dass durch das Auslassen der Eigenschaft mit den Schnitten, die nicht k-1 sein dürfen, sehr viele Mengen aller möglichen Mengen verloren gehen, was mit deiner Antwort ja widerlegt wäre. Der Satz trifft keine weiteren Annahmen über n und k... In einer Folgerung wird n dann als 4*k angenommen, aber eben nicht im ursprünglichen Satz. Wäre die Behauptung dort korrekt?

---

dass diese Anzahl durch die eingangs beschriebene Summe beschränkt ist

Dass also \(n\choose 2k-1\) durch \(\sum\limits_{i=0}^{k-1}{n\choose i}\) beschränkt ist.

Also soll angeblich \(n\choose 2k-1\) eine obere Schranke für \(\sum\limits_{i=0}^{k-1}{n\choose i}\)  sein.

Die Aussage über die Beschränkung führt also zu der Ungleichung

      \({n\choose 2k-1} \geq \sum\limits_{i=0}^{k-1}{n\choose i}\),

und nicht wie in deiner Frage angegeben zu

        \({n\choose 2k-1} < \sum\limits_{i=0}^{k-1}{n\choose i}\).

---

Genau das habe ich ja zu Beginn geschrieben "dann ist die Summe der Binomialkoeffizienten der Form n über i, wobei i von 0 bis k-1 betrachtet wird, DEUTLICH kleiner als n über (2*k-1), also die Zahl aller (2*k-1)-elementigen Teilmengen"

Das Problem daran ist für mich nun, dass ich die Gültigkeit dieser Aussage nicht offensichtlich finde. Du hast ja sogar ein Gegenbeispiel konstruiert. Vielen Dank dafür nochmal! Jedoch bin ich mir weiterhin nicht im Klaren darüber, warum diese Abschätzung als offensichtlich angenommen wird. Eventuell wurde einfach unsauber gearbeitet was die Verhältnisse von n und p angeht. Später wurde scheinbar aus dem nichts n=4*k angenommen und dann dieser Satz mit der Schranke verwendet. Auch in diesem Fall fänd ich diese Schranke jedoch nicht offensichtlich. Was macht diesen einen Binomialkoeffizienten DEUTLICH größer als die SUMME der k Binomialkoeffizienten?