Von der Kneipenrunde zum Weltrekord: Permutieren für Fortgeschrittene

Posted on by

Stellt euch vor, ihr sitzt mit ein paar Kumpels in eurer Lieblingskneipe. Ihr sitzt, stammtischmäßig wie immer, an demselben Platz neben derselben Person. Auf einmal beschließt ihr, dass ihr einmal ausprobieren wollt, wie es sich anfühlt, an einer anderen Stelle am Tisch zu sitzen – neben einer anderen Person. Natürlich stellt sich sofort die Frage, wie viele Möglichkeiten es denn gibt und wie lange es dauern würde, sie alle auszuprobieren.

Eine gute Frage mit einer einfachen Antwort.

Fangen wir einfach an: Ihr seid alleine – dann gibt es genau eine mögliche Anordnung. Jetzt kommt der erste Kumpel vorbei, und schon sind zwei Sitzplätze belegt. Jetzt gibt es genau zwei Möglichkeiten, wie ihr euch hinsetzen könnt. Das ist noch einfach, oder?

Wenn wir für die Personen einfach mal die Buchstaben A und B verwenden, dann ergeben sich folgende zwei möglichen Anordnungen:

AB und BA

Jetzt kommt noch ein Kumpel, und ihr seid zu dritt. Dann ergeben sich folgende mögliche Anordnungen (Permutationen):

ABC, BAC, ACB, BCA, CAB und CBA

Schon sind es sechs mögliche Anordnungen am Tisch. Wenn ihr sagt, dass ihr jede Position ausprobieren wollt und euch eine Minute Zeit nehmt, um zu schauen, wie es sich anfühlt, dann braucht ihr gerade einmal sechs Minuten. Also problemlos machbar.

Die Mathematik dahinter: Permutationen und Fakultät

Sagen wir, die Anzahl der Personen ist n, dann ist die Anzahl der Permutationen P(n).

  • Seid ihr alleine, dann ist P(1) = 1.
  • Zu zweit ergeben sich P(2) = 2 Möglichkeiten.
  • Wenn jetzt eine dritte Person dazu kommt, dann müssen diese zwei Möglichkeiten dreimal ausprobiert werden – mit der dritten Person an jeder Position. Das ergibt P(3) = 6.

Soweit klar?

Jetzt kommt eine vierte Person hinzu. Dann müssen diese sechs Möglichkeiten viermal ausprobiert werden – mit der vierten Person an jeder Position.

Dann ergeben sich folgende mögliche Permutationen:

ABCD, BACD, ACBD, BCAD, CABD, CBAD, ABDC, BADC, ACDB, BCDA, CADB, CBDA, ADBC, BDAC, ADCB, BDCA, CDAB, CDBA, DABC, DBAC, DACB, DBCA, DCAB und DCBA

Da steckt doch bestimmt ein System dahinter? Klar, schauen wir es uns mal bis hierher an:

  • P(1) = 1
  • P(2) = 1 × 2
  • P(3) = 1 × 2 × 3
  • P(4) = 1 × 2 × 3 × 4

Ja, genau! Das ist das Produkt aller positiven ganzen Zahlen von 1 bis zur Anzahl der Personen. Und das nennt man Fakultät, dargestellt durch ein Ausrufezeichen:

P(4) = 4! = 24

Um alle Möglichkeiten auszuprobieren, braucht ihr zu viert schon 24 Minuten – also ungefähr die Dauer eines guten Bieres, wenn man es genießt.

Was passiert, wenn mehr Freunde dazukommen?

Wenn jetzt die Tür der Kneipe auf geht, und noch ein Kumpel reinkommt, dann seid ihr zu fünft, und auf einmal gibt es P(5) = 120 Möglichkeiten. Das sind zwei Stunden oder gut sechs Biere. Da freut sich der Wirt, und eine Sache ist klar: Die anderen Gäste werden euch ganz schön komisch anschauen.

Eine fast endlose Aufgabe.

Und dann wird es unangenehm, denn kurz vor Ladenschluss kommen auf ein letztes Bier noch fünf Kumpels in die Kneipe. Am Tisch ist genug Platz. Kaum dass die Neuen Platz genommen haben, berichtet ihr von eurem Experiment. Und sofort schlagen die neuen Kumpels vor, den Wirt zu überreden, die Kneipe so lange geöffnet zu lassen, bis ihr das zu zehnt ausprobiert habt. Noch bevor du Einwände und ernsthafte Bedenken äußern kannst, sagt der Wirt grinsend zu – mit der Bedingung es auch wirklich durchzuziehen. Er hat nämlich drei Semester Mathematik studiert und wittert ein gutes Geschäft.

Zehn Personen: Ein Mammutprojekt

Zehn Personen sind nicht viele, und die neu dazugekommenen Kumpels haben damit gerechnet, das bis zum nächsten Morgen durchziehen zu können. Weit gefehlt: Ohne Pause würdet ihr fast sieben Jahre brauchen, um das durchzuziehen:

P(10) = 10! = 3.628.800 Möglichkeiten

Das sind 60.480 Stunden oder 2.520 Tage, also 6,9 Jahre.

Wie gesagt, ein gutes Geschäft für den Wirt. Und die mediale Aufmerksamkeit sowie ein Eintrag in das Guinness-Buch der Rekorde wären euch auch sicher. Und bestimmt würden die lokalen Brauereien sich streiten, wer euch sponsern darf.

In diesem Sinne: Prost!