Curso de alemán nivel medio con audio/Lección 069c

índice

Lección 068c ← Lección 069c → Lección 070c

Mathematik von A bis Z (Teil 6)

6

Sechstes Kapitel

---

Permutation

---

Eine biedere Familie einer leider längst vergangenen Zeit besteht aus den beiden Eltern und zwölf wohlgeratenen, gesunden Kindern. Die Familie sitzt zufrieden um den Mittagstisch. Plötzlich wird ein Junge vorlaut. Er behauptet, stets nur den Rest der Suppe zu bekommen, da sein Platz bei Tisch ein ungünstiger sei. Die Familie ist verträglich und ist gewöhnt, Meinungsverschiedenheiten im Kompromißwege beizulegen. Kurz, es wird beschlossen, von nun an die Tischordnung jeden Tag zu verändern, da das Dienstmädchen nicht dazu zu bringen ist, ihren Rundgang beim Servieren irgendwie anders als seit jeher vorzunehmen. Aus dem Ereignis entwickelt sich ein allgemeines Gespräch und man schätzt die Zeit, die es dauern kann, bis alle möglichen Tischordnungen erschöpft sind. „Nun, einige Tage“, meint der eine Junge. „Sagen wir lieber einige Wochen“, wirft ein Mädchen überlegen ein. Schließlich einigt man sich auf ein Jahr. „Es gibt doch dafür eine Formel“, läßt sich der älteste Sohn vernehmen. „Nun, und wofür hältst du unseren Fall, mathematisch gesprochen?“ prüft schmunzelnd der Vater. Der älteste Sohn sinnt eine kurze Weile. Dann sagt er: „Da es sich um die Umstellung einer Tischordnung handelt, ist es nicht gleichgültig, ob Eva neben Alphons oder ob Alphons neben Eva sitzt. Das sind hier zwei verschiedene Fälle. Außerdem werden keine Gruppen gebildet. Wir alle, wir vierzehn Personen, werden jedesmal in eine andere Reihenfolge gesetzt. Es ist dasselbe, als wenn ich vierzehn Dinge, vierzehn Elemente, wie man in der Mathematik sagt, nacheinander in alle möglichen Reihenfolgen bringen sollte. Diese Art der Durcheinanderwechslung heißt Permutation. Und ihre Formel lautet: Die Zahl der Elemente als Fakultät. In unserem Falle also die Vierzehn mit einein Rufzeichen. Vierzehn-Fakultät!“ Der Vater nickt befriedigt. Papier und Bleistift werden in der Pause zwischen Suppe und Fleischgericht geholt und die älteren Kinder rechnen mit roLen Köpfen. Wie groß ist diese 14!, diese Hexenzahl? Ein furchtbares Ergebnis 1 Die Zahl lautet: 87.178.291.200. Was soll man mit diesen Milliarden Möglichkeiten beginnen? Wie lang braucht man dazu? Ach, das Jahr hat ja 365 Tage! Dividieren wir also durch 365. Wieder wird gerechnet. Und ahnungslos, rein dem neuen „Algorithmus“ folgend, verkündet Alphons, der Schnellrechner unter den Geschwistern: „Ich erhalte als Quotienten die Zahl 238.844.633.“ „Weißt du, was das heißt?“ ruft entsetzt der Philosoph unter den Söhnen. „Es heißt, daß wir mit unserer Tischordnung erst in fast 239 Millionen Jahren fertig sind, wenn wir alle Möglichkeiten erschöpfen wollen. Und daß wir über 119 Millionen Jahre brauchen, wenn wir täglich zweimal und noch immer fast 60 Millionen Jahre, wenn wir bei Frühstück, Mittagmahl, Vesper und Abendessen die Tischordnung verändern?“ „Und ich werde sterben, bevor ich eine anständige Suppe bekomme“, jammert hilflos der Jüngste.

Wir haben an diesem Beispiel zugleich die geradezu dämonische Vielfalt der Vertauschungsmöglichkeiten, die Zauberkraft des „Fakultäts“-Befehls und die erste Art einer möglichen Kombinatorik darstellen wollen. Nun haben wir wieder neues „Material“ und wollen es systematisch durchforschen.

Zuerst noch zur Beschwichtigung des Lesers: Unsere biedere Familie, abgeschreckt durch die Kombinatorik, ist auf einen einfacheren Ausweg verfallen, die berechtigte Klage des jüngsten Sohnes zu berücksichtigen. Das Dienstmädchen erhielt den Auftrag, ohne Rücksicht auf den Platzinhaher, mit dem Servieren stets bei einem und demselben Sessel zu beginnen. Die ganze Familie aber „versetzte“ sich jeden Tag um einen Sessel, und zwar im Sinne der Drehung des Uhrzeigers. In bezug aufeinander, auf die jeweiligen Sitznachbarn, war also die Tischordnung unverändert. Wurde aber der Tisch als Bezugssystem betrachtet, dann änderte sie sich jeden Tag. Durch diese Lösung war jeder Tischgenossc alle fünfzehn Tage einmal der Erste, der die Suppe erhielt.

Mathematisch betrachtet liegen auch bei dieser Anordnung vierzehn einzelne Permutationsfälle vor, von denen wir einige aufschreiben wollen:

1, 2, 3, 4, 5, G, 7,  8,  9, 10, 11, 12, 13, 14 (erster Tag) 
2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 12, 13, 14,  1 zweiter Tag) 
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,  1,  2 (dritter Tag)

usw.

14, 1, 2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 12, 13 (vierzehnter Tag)
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 (fünfzehnter Tag) 

Nur sind die angedeuteten vierzehn Fälle (der erste und fünfzehnte sind ja gleich) nach einem anderen Prinzip, nämlich dem der sogenannten Kreisvertauschung oder zyklischen Vertauschung aus der Gesamtmenge der möglichen 87.178.291.200 Permutationsfälle künstlich herausgegriffen, weil die weitere Nebenbedingung der relativen Unveränderlichkeit der Tischordnung hinzugekommen ist.

Wir haben im obigen Beispiel die zu vertauschenden Sitzplätze mit Ziffern bezeichnet. Man könnte sie auch mit Buchstaben nach der Reihenfolge des Alphabets bezeichnen. Natürlich bedeutet an sich eine solche Numerierung ebensowenig eine größenmäßige Rangordnung wie etwa die Numerierung der Sitze einer Sitzreihe im Theater. Ich könnte die zu vertauschenden Dinge ebensogut durch Farben, durch Namen, durch irgendwelche Unterscheidungszeichen charakterisieren. Deshalb spricht man bei solchen „Anzeigern“, bei solchen Markierungen der Unterscheidung sonst vollkommen gleichwertiger Dinge, von „Indizes“ (Einzahl: „Index“ oder auf deutsch „Anzeiger“). Dieser pure Anordnungszwcck von Zahlen oder Buchstaben spielt, besonders seit Leibniz, dessen Genie auch diesen „Algorithmus der Ordnung“ einführte, eine zunehmend bedeutungsvolle Rolle in der Mathematik. Nun wollen wir uns etwas nicht ganz leichtes verdeutlichen. Wir behaupteten apodiktisch, die Dinge seien gleichwertig und die Nummern oder Indizes, oder wie wir sie sonst nennen wollen, hätten keine Größenbedeutung. Gleichwohl spricht man ruhig davon, daß etwa das mit zwei bezeichnete Ding „höher“ oder das „höhere Element“ sei als das mit eins bezeichnete Ding. Man sollte korrekter sagen: Ding 2 ist das mit dem „höheren Index“ bezeichnete Ding gegenüber dein Ding 1. Ansonst sind Ding 1 und Ding 2 gleich, vor allem gleich groß.

(Es ist auch denkbar, daß die Dinge verschieden groß sind, ohne daß ich auf die Größe achte. Es interessiert mich lediglich ihr „Dingsein“, ihr Einheitscharakter.)

Es handelt sich hier wieder um eine Kabbala. Nämlich die Kabbala der Anordnung oder Zuordnung. Ich könnte einfach nicht sprechen, nicht schreiben, wenn ich die Indizes nicht nach einem Größenprinzip anreihen dürfte. Das Alphabet ist da vielleicht korrekter und weniger zweideutig als die Indizierung durch Ziffern, die ja ihre Größenbedeutung irgendwie unbewußt mitschleppen. Der Buchstabe d steht im Alphabet „höher“ als der Buchstabe b. Folglich ist das Ding d in der Kombinationslehre „höher“ gereiht als das Ding.

(Man nennt diese Anordnung auch die „lexikographische“. [Wie in einem Lexikon!])

Durch diese Festlegung des „Platzranges“ ergibt sich der für alle kombinatorischen Überlegungen grundlegende Begriff der „guten Ordnung“ oder der „Wohlordnung“. Eine Wohlordnung liegt dann vor, wenn ich z. B. bei der Permutation in folgender Art fortschreite:

abc, acb, bac, bca, cab, cba, oder in Ziffern

123, 132, 213, 231, 312, 321.

Durch diese Art des Fortschreitens, wobei stets das „tiefere“ Element solange als nur irgend möglich an seinem Platz gehalten wird, kann uns kein kombinatorischer Fall entgehen, wir steigen, wie man sagt, von der „niedersten“ zur „höchsten“ Permutation in „guter Ordnung“ auf und erhalten als Beweis der Beendigung unserer Bemühung am Schluß die Umkehrung der Ausgangspermutation. Während in der „niedersten“ Permutation kein Element vor einem niedereren stand, stellt in der „höchsten“ Permutation jedes Element vor einem niedereren. Ich will nicht allzusehr verwirren, kann aber doch nicht umhin, zu bemerken, daß bei einer Auffassung der Permutationen als wirkliche Zahlen tatsächlich auch die niederste Permutation die niederste Zahl und die höchste Permutation die höchste Zahl darstellt (123 ... 321). Dazwischen liegen, größenmäßig wohlgeordnet, alle anderen Zahlen, die sich aus 1, 2 und 3 bilden lassen.

Doch wir wollen energisch von diesem letzten Zusammenhang wegdenken und wieder zu unseren größenfremden Indizes zurückkehren. 123 bedeutet für uns jetzt dasselbe wie 321 oder 231, nämlich irgendeine beliebige Permutation der drei erwähnten Indizes.

Nun wollen wir das Problem lösen, wieso unser rätselhafter „Befehl“, unsere „Fakultät“, unsere 3 mit dem Rufzeichen, so treffsicher die Gesamtzahl möglicher Permutationen angibt. Zuerst behaupten wir der Vollständigkeit halber oder, wie man heute sagt, „zur Aufrechterhaltung des Systems“ einen logischen Unsinn. Wir haben Ähnliches schon bei den Potenzen, und zwar bei der nullten und ersten Potenz kennen gelernt. Wir verlangen also zu wissen, wie groß die Permutationszahl ist, wenn wir nur ein Element besitzen. Deutlicher: „Stelle ein Element in Wohlordnung solange um, bis du alle Möglichkeiten erschöpft hast.“ Nach gehöriger Überlegung formulieren wir den einen Unsinn mathematisch durch einen zweiten, womöglich noch größeren. Wir schreiben stolz hin: Zahl der Permutationen ist gleich 1! (Eins Fakultät.) Oder in Worten: Um das Resultat zu erhalten, soll man 1, von 1 beginnend, solange mit den nächsthöheren Ziffern multiplizieren, bis man endlich zur Eins gelangt! Daß sich dabei wieder die Zahl Eins ergibt, ist kaum unklar.

Nach diesem logischen Exzeß wollen wir vorsichtig weiterkalkulieren. Was geschieht bei zwei Elementen? Schreiben wir in Wohlordnung an:

      ab     ba 

Kein Zweifel: Wir haben die Zahl aller möglichen Permutationen von der niedersten zur höchsten durchlaufen. Und nun wollen wir messerscharf denken, um einen Übergang zu der uns schon als Behauptung bekannten Formel zu finden. Was haben wir gemacht? Wir haben a solange als möglich an seinem Platz gehalten und inzwischen gleichsam b permutiert. Als wir damit fertig waren, haben wir b an erste Stelle gerückt und a permutiert. Wir haben also die Permutation der Einzelelemente zweimal vorgenommen. Ein Einzclelement hat aber bloß eine Permutation, folglich ist die Permutationszahl aus zwei Elementen 1•2, oder in unserer Form geschrieben 2!, also gleich der Fakultät von zwei, was als Ergebnis die Zahl 2 liefert. Bei drei Elementen ergibt sich:

    abc     bac     cab 
    acb     bca     cba 

Wenn wir wieder unsere Methode anwenden, können wir behaupten, daß wir dreimal das uns jeweils noch zur Verfügung stehende erste Element möglichst lange festgehalten und inzwischen die zwei anderen Elemente permuliert haben. Da aber die Permutationszalil zweier Elemente gleich ist 1•2, so muß ich diese Zahl jetzt noch mit 3 multiplizieren. Also für 3 Elemente: Permutationszahl ist 1•2•3 oder 3! oder drei Fakultät oder die Anzahl 6. Für 4 Elemente ergibt sich:

     abcd      bacd      cabd      dabc
     abdc      badc      cadb      dacb
     acbd      bcad      cbad      dbac
     acdb      bcda      cbda      dbca
     adbc      bdac      cdab      dcab
     adcb      bdca      cdba      dcba  

Wir wollen jetzt nicht mehr den ganzen Vorgang wiederholen. Wir haben, kurz gesagt, das erste Element jeweils solange festgehalten, bis die Permutation der drei übrigen Elemente vollzogen war. Da ich aber vier Elemente habe, also vier Elemente an erste Stelle setzen konnte, muß ich die Permutationszahl von drei Elementen mit vier multiplizieren. Also 4mal 1•2•3 oder 1•2•3•4 oder 4! oder vier Fakultät oder 24.

Wenn wir jetzt weitergehen, müssen wir analog finden, daß jede Permutation aus verschieden indizierten Elementen soviel Umstellungsmöglichkeiten aufweist, als die Zahl der Elemente beträgt, zu welcher Zahl ich aber außerdem noch das Rufzeichen setze. Also Zahl der Permutationen aus 10 Elementen ist gleich 10!, aus 75 Elementen ist gleich 75!, aus 3124 Elementen ist gleich 3124! usw. bis ins Unendliche.

Nun könnte es aber vorkommen, daß nicht lauter verschiedene Elemente oder Indizes gegeben sind, sondern daß einige davon gleich sind. Ich soll, grob gesprochen, etwa drei Äpfel, zwei Birnen und eine Kirsche so vertauschen, daß alle möglichen Gruppierungen dieser drei Obstsorten auftreten, wobei ich aber nicht darauf achten muß, ob ich die Birne 1 oder die Birne 2 nehme. Das heißt: der Permutationsfall

„Birne 1, Birne 2, Birne 3, Apfel 1, Kirsche, Apfel 2“ gilt als gleich mit dem Fall „Birne 3, Birne 1, Birne 2, Apfel 2, Kirsche, Apfel 1“ und mit dem Fall „Birne 2, Birne 1, Birne 3, Apfel 2, Kirsche, Apfel 1“ usw. Nennen wir der Einfachheit halber die Äpfel alle a, die Birnen b und die Kirsche c, dann hätten wir „wohlgeordnet“ als erste Permutation

       a a b b b c und als letzte c b b b a a. 

Es ist zu zeitraubend, die Formel für solche Fälle, genannt „Permutationen mit mehrfachem Auftreten einzelner Elemente“, abzuleiten. Ich bitte also um Kredit, wenn ich die Formel einfach anführe. Sie lautet in unserem Falle: Gesamtzahl der Permutationen, also 6!, dividiert durch die Fakultäten der wiederholten Elemente, die miteinander zu multiplizieren sind. Also 6! dividiert durch das Produkt von 2!, 3! und 1!, was als Bruch geschrieben gleich ist

${\frac {6!}{2!\;3!\;1!}}={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6}{1\cdot 2\times 1\cdot 2\cdot 3\times 1}}=60$

Ich werde unsere Obstarten also in 60 verschiedene Gruppierungen bringen können. Für mathematisch agilere Leser sei noch beigefügt, daß diese Formel eigentlich die allgemeinere ist. Ich könnte bei jeder Permutation fragen, wie oft jedes Element auftritt. Und dann etwa bei fünf verschiedenen Elementen beherzt schreiben:

Zahl der Permutationen $\textstyle {\frac {1\cdot 2\cdot 3\cdot 4\cdot 5}{1!\;1!\;1!\;1!\;1!}}$, da ja jedes Element nur einmal auftritt. Wie man sieht, ergibt sich ein richtiges Resultat. Und unsere erste Formel wird, wie man sagt, zu einem Spezialfall der zweiten, allgemeineren.

Zum Abschluß der Permutationsbetrachtung noch ein Beispiel. Wie hoch ist die Anzahl der Permutationen aus abbbbc? Natürlich

${\frac {6!}{1!\;4!\;1!}}={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6}{1\times 1\cdot 2\cdot 3\cdot 4\times 1}}=30$.

Der blicksichere Leser wird dabei noch merken, daß wenn ich die Rufzeichen wegdenke, die Ziffernsummen oberhalb und unterhalb des Bruchstrichs stets gleich sein müssen; was ja klar ist, da ich zuerst die Fakultät der ganzen Elementenzahl als Bruchzähler und dann die Fakultäten der diese Elementenzahl zusammensetzenden Elementengruppen als Bruchnenner anschreibe.

Natürlich ließe sich über die Permutation noch viel sagen. Es gäbe auch noch eine große Anzahl von Problemen, die wir erörtern könnten. Da es sich aber bei der Permutation durchaus nicht um die für die Mathematik im allgemeinen und für unsere Absichten im besonderen wichtigste Form der Kombinatorik handelt, wollen wir mit der Feststellung schließen, daß bei der Perinutation stets alle Elemente verwendet werden müssen und daß diese Elemente umgestellt werden, daß also die verschiedene Reihenfolge der Elemente dafür entscheidend ist, ob verschiedene Permutationsfälle vorliegen. Es gäbe ja stets nur einen einzigen Fall aus so und soviel Elementen, wenn ich nur die Mischung und nicht die Reihenfolge beachten würde. Die. Permutation ist also nichts als ein Umstellen der Reihenfolge, ein Durcheinandermischen.

índice

Lección 068c ← Lección 069c → Lección 070c