Zeigen Sie: die Anzahl der k - elementigen lückenhaften Teilmengen von ... ist ...?

Question

Eine Menge \( A \subseteq\{1, \ldots, n\} \) heißt lückenhaft, falls es in \( A \) keine zwei Elemente \( a, b \) mit \( |a-b|=1 \) gibt. Zeigen Sie: die Anzahl der \( k \)-elementigen lückenhaften Teilmengen von \( \{1, \ldots, n\} \) ist \( \left(\begin{array}{c}n+1-k \\ k\end{array}\right) \).

Comments

Ich nehme an mit Induktion, aber wie?

---

Induktionsanfang für n=3...

Weniger macht keinen Sinn.

---

Weniger macht keinen Sinn.

Oh doch, und es wird im Induktionsschluss sogar gebraucht.

---

Du hast natürlich wie immer recht. Um lückenhaft zu sein, braucht man ja nicht zwingend zwei Elemente, zwischen denen dann eine Lücke ist...

Answer 1

Mal vorab (vor dem Induktionsbeweis) ein kombinatorisches Argument:

Wir repräsentieren die Menge {1,...,n} durch eine Reihe von n weißen Kugeln. Wir wählen eine k-elementige Teilmenge aus, indem wir k weiße Kugeln durch rote ersetzen. Die Teilmenge ist lückenhaft, wenn sich zwischen je 2 roten Kugeln eine weiße befindet. Wenn dies so ist, nehmen wir für jede der ersten k-1 Kugeln den rechten (weißen) Nachbarn weg. Wir erhalten eine Repräsentation einer k-elementige Teilmenge von {1,...n+1-k}.

Umgekehrt: Wenn wir eine solche Repräsentation haben, schieben wir neben jeder der ersten k-1 Kugeln eine weiße Kugel ein ....