rekursiv: Wie viele Teilmengen, die keine zwei aufeinander folgenden Zahlen enthalten, besitzt die Menge {1,...,n}?

Question

Aufgabe:

Lösen Sie mit einer Rekursion: Wie viele Teilmengen, die keine zwei aufeinander folgenden Zahlen enthalten, besitzt die Menge {1,...,n}?

Problem/Ansatz:

Wie gehe ich hier vor?

Beispiele für Teilmengen könnten sein: {1}, {2} usw. und {1,2,3,4...}, {2,3,4...} usw., oder?

Answer 1

Du kannst z.B. eine Rekursion für das Problem finden. Hierfür gebe uns \( \varphi(n) \) die Anzahl solcher Folgen für die Menge \( \{1,2, \ldots, n\} \). Nun musst du versuchen, eine Relation zwischen \( \varphi(n) \) und \( \varphi(k) \) zu finden, für \( k \in 1, \ldots, n-1 \). In diesem Fall ergibt sich

\(\begin{aligned} \varphi(n)=\varphi(n-1)+\varphi(n-2)\end{aligned} \)
da wir entweder die Zahl \( n \) garnich beachten und lediglich die Menge \( \{1, \ldots, n-1\} \) betrachten könnten, oder uns dazu entschliessen, dass die Folge \( n \) enthält (und somit nicht \( n-1 \) enthalten kann, da diese beiden ja aufeinander folgen). Du erkennst die Rekursion sicherlich direkt als die Fibonacci Folge wieder, deren geschlossene Form sich auf vielerlei Weisen ermitteln lässt.

Hinweis: Wichtig ist in der obigen Betrachtung, dass die beiden Fälle, welche wir unterscheiden, disjunkt sind, also in diesem Fall, dass wir zum einen alle Folgen zählen, welche \(n\) nicht enthalten, und jene, welche \(n\) enthalten. Somit ist sicher, dass wir keine Folgen mehrfach zählen.

Comments

Also ich habe das jetzt so verstanden:

1. Fall: {1,2,...,n} => n enthalten, also kann n-1 nicht enthalten sein. Das bedeutet, aus diesem Fall leiten wir ab, dass n-2 enthalten sein muss. Damit bekommen wir also schonmal den Teil φ(n-2) der Summe.

2. Fall: {1,2,...,n-1} => n-1 enthalten, also ist n nicht enthalten. Aber dann ist doch n-2 auch nicht enthalten, da es direkt hinter n-1 stehen müsste, also so: {1,2,...,n-2,n-1}.

Also wie leiten wir direkt die n-1 ab. Das heißt φ(n-1).

Durch die Sumenregel hätten wir dann φ(n) = φ(n-1) + φ(n-2).

Aber z.B. ist im zweiten Fall doch auch die n-3 enthalten. Woher weiß ich, dass ich beim zweiten Fall das letzte Element der Menge für die Formel nehmen muss, und nicht z.B. ein beliebiges, was nicht direkt darauf oder davor folgt? also z.b. n-3?

---

Im zweiten Fall wählst du die Elemente in einer solchen Reihenfolge, die alles abdeckt und die eine Rekursion ermöglicht. Ich verstehe deine Frage nicht so ganz...

---

Was meinst du mit "die alles abdeckt" ?

Ich meine halt. Beim zweiten Fall. Wieso nehme ich aus der Menge das letzte Element für die Rekursion?

Ist das eine Regel oder folgert sich das ganz normal aus der Logik?

---

"Sei an die Anzahl Teilmengen von {1, . . . , n} ohne aufeinanderfolgende
Zahlen. Dann gilt a₀ = 1 und a_n+1 = a_n + a_n−1, denn für eine Teilmenge von
X ⊆ {1, . . . , n + 1} ohne aufeinanderfolgende Zahlen, die n + 1 nicht enthält, gibt
es a_n Möglichkeiten; liegt n + 1 ∈ X, so gilt n /∈ X, und daher gibt es a_n−1
Möglichkeiten für X"

Ich habe diese Lösung aus dem Skript gefunden.

Wenn man a_n+1 = a_n + a_n−1   nach an umstellt, erhält man: a_n+1 - a_n-1 = a_n, was aber was anderes ist, als \(\begin{aligned} \varphi(n)=\varphi(n-1)+\varphi(n-2)\end{aligned} \) oder nicht?

---

Das sind die exakt gleichen Rekursionen, nur dass in jener, welche du gefunden hast, die Menge \(\{1, \ldots, n+1\}\) betrachtet wird. Wenn du bei meiner Formel \(n+1\) einsetzt, dann erhältst du ja eben das, deswegen kann ich deine Frage nicht ganz verstehen.

---

Du hast recht! Nur komisch, dass in dieser Lösung n+1 betrachet wurde, als Element der Menge, obwohl diese ja nur bis n gehen sollte. Naja...