Aufgabe:
Ein CoMa-Baum der Ordnung \( k \) ist rekursiv definiert wie folgt: Für \( k=0 \) besteht er aus einem einzigen Knoten. Für \( k \geq 1 \) besitzt er eine Wurzel des Grades \( k \), deren Kindknoten jeweils Wurzeln von CoMa-Bäumen der Ordnung \( k-1, k-2, \ldots, 0 \) sind (in dieser Reihenfolge von links nach rechts).
CoMa-Heaps. Ein CoMa-Heap ist eine Liste von CoMa-Bäumen, die die folgenden Eigenschaften genügt:
- Jeder CoMa-Baum in der Liste erfüllt die Max-Heap-Eigenschaft.
- Für jedes \( k \geq 0 \) gibt es höchstens einen CoMa-Baum der Ordnung \( k \).
- Die CoMa-Bäume sind nach Ordnung aufsteigend sortiert.
1 Zeigen Sie, dass für alle \( n \in \mathbb{N} \) einen eindeutigen CoMa-Heap gibt, der insgesamt genau \( n \) Knoten enthält.
2 Sei \( A \) ein CoMa-Heap, der insgesamt \( n \) Knoten enthält. Wie viele CoMa-Bäume kann \( A \) höchstens enthalten?
