Herr Chomsky, Chefkoch im „Hilbert Gold“, einem exclusiven Hotel mit internationaler Küche, bereitet sich auf die nächste Grillsaison vor. Als Spezialität sollen diesmal Schaschlik-Spieße serviert werden, mit Fleisch, Zwiebeln, Paprika und Pilzen. Die von unserem Chefkoch erstellten Spieße (die er gerne „Chomsky-Spieße“ nennt) zeichnen sich dabei aber durch eine ganz bestimmte Reihenfolge der Zutaten aus. Chefkoch Chomsky beschreibt dies wie folgt:

„Chomksy-Spieße gibt es in einfachen und komplexen Varianten. Bereits ein einzelnes Stück Fleisch auf einem Spieß ist ein Chomsky-Spieß (der Genuss beruht hier auf der richtigen Wahl der Marinade). Nimmt man einen Chomsky-Spieß und erweitert ihn auf beiden Seiten mit einem Stück Zwiebel, erhält man wieder einen Chomsky-Spieß. Genauso kann man einen Chomsky-Spieß auch um einen Pilz auf der einen Seite und ein Stück Paprika auf der anderen Seite erweitern, um wieder einen Chomsky-Spieß zu erhalten. Oder man nimmt den kompletten Inhalt eines Chomsky-Spießes und fügt ihn, unter Beibehaltung der Reihenfolge, einem anderen Chomsky-Spieß hinzu. Was nicht durch diese Regeln aufgespießt werden kann, ist auch kein Chomsky-Spieß und hat in meiner Küche nichts verloren.“

Die Chomsky-Spieße sollen Ihnen einen kleinen Einblick in die Welt der Computersprachen bieten. Jede Computersprache, wie z.B. die Programmiersprache Java oder die Beschreibungssprache HTML, regelt genau, wie ein Ausdruck in dieser Sprache aussehen muss – also beispielsweise, dass am Ende jeder Anweisung ein Semikolon stehen muss, oder dass jede öffnende Klammer eine korrespondierende schließende Klammer haben muss.

Das Hilbert-Hotel hat ein neues Schließsystem einbauen lassen. Die Schlüsselkarten sind quadratisch, jede Schlüsselkarte hat 64 Felder. In jedem dieser Felder kann dabei ein Loch eingestanzt sein. Jede Schlüsselkarte weist auch nach einer Drehung wieder dasselbe Muster auf, kann also nie „falschherum“ ins Schloss gesteckt werden.

Hier ein Beispiel (Abb. 13).

Die Frage „Wie viele Objekte dieser Art gibt es?“ bildet den Kern der Kombinatorik, spielt jedoch auch in der Theoretischen Informatik eine entscheidende Rolle. Die Antwort auf diese Frage gibt zum Beispiel Aufschluss darüber, wie schnell man diese Objekte aufzählen kann oder wie viel Speicherplatz diese belegen. Im obigen Beispiel könnte man daraus zum Beispiel ableiten, wie schnell ein Einbrecher wohl alle möglichen Schlüsselkombinationen ausprobieren könnte oder wie viele verschiedene Schlüssel man herstellen könnte (und damit auch, wie viele Hotelzimmer man maximal haben könnte, ohne dass bei zwei Zimmern derselbe Schlüssel passt).