State of the Nation

II-8 Informationstheorie (3 Pkte)

Ein Kaktus ist eine zusammenhängende einstellige Funktion, bei der die in den Zyklus mündenden Bäume höchstens Gebüsche der Höhe 1 sind, also Bouquets von Stacheln. Auf einer endlichen Menge X, wie lang muss der Zyklus mindestens sein, damit der Kaktus moch starr, d.h. seine Symmetriegruppe die 1, werden kann?

(Aus: Prüfungs-Abschrift “Einführung in die theoretische Informatik” vom 16.09.2003, Aufgabe von Prof. Leeb)