0 Daumen
482 Aufrufe

Aufgabe:

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

Lösen Sie die Aufgabe mit einer Rekursion und vergessen Sie die leere Menge nicht.

Avatar von

Immer erst einmal kleine Beispiele überlegen:

n = 1: , {1}

n = 2: ∅, {1}, {2}

n = 3: ∅, {1}, {2}, {3}, {1,3}

n = 4: ∅, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}

n = 5: ∅, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}, {5}, {1,5}, {2,5}, {3,5}, {1,3,5}

Hier erkennst du hoffentlich ein Muster. Die Anzahl der Teilmengen wir also durch die Folge

$$ a_1 = 2, a_2 = 3 $$ $$ a_{n} = a_{n-1} + a_{n-2} $$

beschrieben

1 Antwort

0 Daumen

Sei \(P(n)\) die Menge aller Teilmengen von \(\{1,\dots,n\}\), die keine zwei aufeinander folgenden Zahlen enthalten.

Die Elemente von \(P(n)\) lassen sich in zwei Klassen einteilen:

  • Mengen die Element von \(P(n-1)\) sind.
  • Mengen die aus Elemente von \(P(n-2)\) entstanden sind indem \(n\) hinzugefügt wurde.
Avatar von 105 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community