Der in der Vorlesung vorgestellte Algorithmus (revolving door) zum Durchlaufen der k-Teilmengen einer n-elementigen Menge hat die Eigenschaft, daß zwei benachbarte Teilmengen durch Ersetzen eines Elements auseinander hervorgehen. Der revolving door Algorithmus läßt sich wie folgt definieren:
A(n,k) = A(n-1,k) , A(n-1,k-1)+n
A(n,k) ist dabei die Folge der k-Teilmengen einer n-elementigen Menge in der Reihenfolge des revolving door Algorithmus. Die Notation bedeutet, daß man diese Folge erhält indem man zuerst die k-Teilmengen der n-1 elementigen Grundmenge nimmt, und daran wird die Folge der k-1 elementigen Teilmengen, erweitert um das Element n, angehängt. Die zweite Folge wird noch umgekehrt bevor sie angehängt wird. Dies wird mit der Unterstreichung angedeutet.
Brendan McKay und Peter Eades haben 1982 die revolving
door Durchlaufreihenfolge wie folgt definiert (natürlich müssen die Basismengen
richtig gewählt werden, d.h. im ersten Teil die Elemente 3,4,...n und im
zweiten Teil die Elemente 2,3,4...n):
B(n,k) = 1+2+B(n-2,k-2) , 1+B(n-2,k-1) , B(n-1,k)
a) Listen Sie die 3-Teilmengen einer 6-elementigen Menge in dieser Reihenfolge
auf.
b) Welche zusätzliche Eigenschaft wird durch zwei benachbarte Teilmengen
erfüllt? Beweis.