Lösungen zur Übung 5.3-1

1. Wieviele Möglichkeiten gibt es, k = 10 unterscheidbare Socken auf N = 20 Plätze zu verteilen? Dabei darf auf jedem Platz nur ein Socken liegen!
Das ist noch einfach; wir müssen nur die Zahl der Möglichkeiten "durchdeklinieren".
Für den ersten Socken haben wir N = 20 Möglichkeiten. Für den zweiten Socken gibt es aber nur noch N – 1 = 19 Möglichkeiten, da der vom ersten Socken belegte Platz nicht mehr verfügbar ist.
Wir haben also z.B. den 1. Socken auf Platz 17, und den zweiten Socken auf Platz 4, also die Anordnung (1/17), (2/4). Da die Socken unterscheidbar sind, sind die vertauschten Anordnungen (1/4) und (2/17) verschieden und werden extra gezählt.
Für Socken Nr. 10 bleiben also noch N – 9 = 11 Möglichkeiten.
Insgesamt haben wir
 
P1 (10, 20)  =    20 · 19 · 18 · .... · 11 =  6,70 · 1011   
 
Schon verblüffend, wieviel Unordnung man mit nur 10 Socken in einem kleinen Zimmer erzeugen kann!
Das Problem läßt sich sehr einfach verallgemeinern:
 
 
P1(k,N)  =   N · (N – 1) · .... · (N – (k – 1)) 
           
   =  {N · (N – 1) · .... · (Nk + 1)} · {(Nk) · (Nk – 1) · ... · 1}
{(Nk) · (Nk – 1) · ... · 1}      
           
   =  N!
(Nk)!
       
   
Wenn wir in den Kombinatorik-Modul schauen, stellen wir fest, dass das die Formel zum folgendem formalisierten Problem ist:
"We must select different elements", and "Different arrangements of the same elements count"
Relativ zum Beispiel im Kombinatorik-Modul, hätten wir die Frage auch so stellen können: "Gegeben sind die natürlichen Zahlen 1 bis 20. Wieviel Zahlen kann man durch 10 verschiedene Elemente dieser Menge bilden?
Das Selektieren einer Zahl aus den gebenenen 20 entspricht dann der Platzierung eines Sockens auf einen Platz, der dann für andere nicht mehr verfügbar ist. Der Socken trägt die herausgegriffene Zahl, ist also von den anderen unterscheidbar.
Noch einfacher gelingt die "Übersetzung" von der Sockenfrage zum Zahlenbeispiel im Kombinatorikmodul, wenn wir nur 3 Socken auf 10 Plätze verteilen.
Die im Beispiel aufgeführten 3-stelligen Zahlen sind dann "Belegungspläne". Der Zahl 153, zum Beispiel, entspricht dann je ein Socken auf Platz 1, 5, und 3.
Dass auch 531 oder 351 als unterscheidbare Fälle zugelassen sind, kommt von der postulierten Unterscheidbarkeit der Socken.
 
2. Wieviele Möglichkeiten gibt es, k = 10 unterscheidbare Socken auf N = 20 Plätze zu verteilen? Dabei dürfen auf jedem Platz beliebig viele Socken liegen!
Das ist sehr einfach:
Für den 1. Socken gibt es 20 Möglichkeiten, für den 2. Socken auch, usw.
Insgesamt haben wir
   
P(10, 20)    =   2010 =  210 · 1010 =  1,024 · 1013 
 
Die Verallgemeinerung ist klar, wir haben
 
 
P(k, N)    =   Nk 
 
Im Kombinatorik-Modul entspricht das dem Fall "Identical elements, different arrangements count"
Die "Übersetzung" in das Beispiel des Kombinatorikmoduls kann man wie oben machen:
Den Zahlen 455, 545, 554 entsprechen dann zwei Socken auf Platz 5 und einer auf Platz 4. Dass wir diese drei Variationen zulassen, kommt wiederum von der Unterscheidbarikeit der Socken.
     
3. Wieviele Möglichkeiten gibt es, 10 "identische" Socken auf 20 Plätze zu verteilen? Dabei darf auf jedem Platz nur ein Socken liegen!
Für den 1. Socken haben wir 20 Möglichkeiten. Für den 2. noch 19.
Allerdings sind für jede mögliche Anordnung der beide Socken jetzt 2 Anordnungen ununterscheidbar. Falls wir z.B. den 1. Socken auf Platz 15 legen und den 2. Socken auf Platz 3, ist diese Anordnung identisch oder ununterscheidbar vom Fall 1. Socken auf Platz 3 und 2. Socken auf Platz 15.
Wir haben also nur (20 · 19)/2 Möglichkeiten für die ersten beiden Socken.
Das müßte uns jetzt bekannt vorkommen! Dieses Gesocks entspricht der Grundaufgabe bei der Verteilung von Leerstellen.
Damit haben wir im Speziellen und im Allgemeinen:
 
P3(10, 20)   =   20 · 19 · .... · 11
1 · 2 · 3 · ..... · 10
  =  1,84 · 105 

P3(k, N)    =  N!
(Nk)! · k!
 =  æ
è
N
k
ö
ø
 
Im Kombinatorik-Modul entspricht das klar dem Fall "Identical elements, different arrangements do not count"
Die "Übersetzung" in das Beispiel des Kombinatorikmoduls läuft wie in den vorherigen Fällen und sollte jetzt klar sein.
 
4. Wieviele Möglichkeiten gibt es, 10 "identische" Socken auf 20 Plätze zu verteilen? Dabei dürfen auf jedem Platz beliebig viele Socken liegen!
Das ist die schwierigste Frage. Offenbar haben wir den Fall "Identical elements, different arrangements do not count"
Am besten startet man mit der "Übersetzung" wie in den drei vorherigen Fällen. Dann ist klar, dass der Identical elements, different arrangements do not count Fall der richtige ist.
Die allgemeine Formel ist dann
 
P4(k, N)  =  (N + k – 1)!
(N – 1)! · k!
 
       
P4(10, 20)  =  29!
9! · 10!
  =  6,71 · 1018
 
Das sind schon eine Menge Möglichkeiten!
 
5. Was erfordert weniger Zeit: N = 10 Paar Socken (= 20 Einzelsocken) gleich nach der Wäsche zu sortieren, oder zu warten, bis 100 Paare zusammenkommen?
Wir schaffen jetzt nicht mehr Unordung, sondern Ordnung. Dazu gehen wir systematisch vor. Wir schauen also nicht auf den Sockenhaufen und versuchen, die passenden Socken direkt zu erkennen, sondern:
Wir nehmen einen beliebigen 1. Socken und vergleichen ihn mit allen anderen. Falls wir mit N = 10 Paaren starten, müssen wir dazu maximal k1max = 2N – 1 = 19 Arbeitsschritte machen.
Es könnte nun natürlich sein, dass der gesuchte Kollege schon beim 3. oder 17. Vergleich auftaucht, wir also nicht alle 19 durchklappern müssen. Im Mittel müssen wir wohl nur die Hälfte der verbliebenen Socken checken. Die Zahl der ersten Arbeitsschritte ist im Mittel also nur k1 = (2N – 1)/2 » 2N/2 = N.
OK. Nach k1 = (2N – 1)/2 Arbeitsschritten im 1. Durchgang haben wir dann noch 2N – 2 Socken übrig.
Wir nehmen wieder einen Socken und vergleichen ihn mit allen anderen. In diesem 2. Durchgang müssen wir ihn im schlechtesten Fall mit k2max = 2N – 3 = 17 anderen vergleichen, d. h. es fallen im Mittel k2 = (2N – 3)/2 Arbeitsschritte an.
Das Bildungsgsgesetz ist klar:
Im i-ten Durchgang sind ki = (2N – (i + 1))/2 Arbeitschritte nötig.
In jedem Durchgang werden 2 Socken entfernt, insgesamt brauchen wir also N Durchgänge.
Die Gesamtzahl der Arbeitschritte K(N) ist damit
 
K(N)  =  N
S
i = 1
ki   =   1
2
  ·  N
S
i = 1
   2N – i – 1
 
Kann man die Summe vereinfachen? Man kann! Für N = 10 oder = 100, haben wir z.B.
 
K(10)  =  ½{(20 – 2) + (20 – 3) + .... +(20 – 11)}  =   ½{18 + 17 + ... + 9}  =  67,5
           
K(100)   =   ½{(200 – 2) + ... + (200 – 101)}  =   ½{198 + 197 + ... + 99}   =  ?
 
Nach kurzem Nachdenken kommt man darauf, dass die gesuchte Summe recht ähnlich ist zu dem Problem, das der junge Gauss mit Bravour gelöst hat 1). Die kleinste Zahl in der Summe ist 2N – N – 1, die größte ist 2N – 2. Addiert man sie, erhält man 3N – 3. Genau das erhält man auch, wenn man die Zweitkleinste mit der Zweitgrößten addiert und so weiter. Alles in allem hat man N/2-mal diese Summe. Damit erhalten wir eine einfache Formel:
   
 
K(N)  =   N
2
  ·  3N – 3
2
 =  3N2 – 3N
4
     
Vergleichen wir nun den Aufwand, a · N Socken auf einmal zu sortieren, mit dem Aufwand, a-mal portionsweise jeweils N Socken zu sortieren [das ist natürlich einfach a · K(N)], dann erhalten wir für das Aufwandsverhältnis A = K(a·N) / [a · K(N)]:
     
   
A   =   K(aN)
a · K(N)
 =  3a2N2 – 3aN
3aN2 – 3aN
 =  aN – 1
N – 1
 »  a
     
Dabei unterstellen wir, daß N >> 1, so daß die quadratischen Terme den Bruch dominieren.
Damit haben wir eine wesentliche haushaltstechnische Erkenntnis gewonnen: 100 Paar Socken zu sortieren dauert etwa 10-mal länger, als 10-mal 10 Paar durchzugehen!
Und für den Aufwand bei Anwachsen der von Unordnung betroffenen Menge von Elementen (hier: Socken) erhält man K(aN) / K(N) = a · A » a2, d. h. Ordnung wieder herzustellen wird quadratisch schwieriger, je länger man die Unordnung wachsen läßt.
 

1) Als Gauß noch in der Grundschule war, wollte sein Lehrer sich eine Ruhepause verschaffen. Er gab seinen Schülern die Aufgabe die Zahlen von 1-100 zu addieren (1+2+3+ ... +100 = ?). Aus der Verschnaufpause wurde nichts, denn prompt meldete sich der junge Gauß mit der richtigen Antwort: 5050! Misstrauisch fragte nun der Lehrer wie er dies so schnell herausgefunden haben wolle.
Na ganz einfach! Gauß erkannte, dass 1+100=101, 2+99=101, 3+98=101 usw ist. Die Summe der ersten und letzten Zahl ergibt immer 101. Es gibt 50 solcher Zahlenpaare, und somit ist die Summe aller Zahlen 50-mal 101 = 5050.
(Aus dem Internet)
Den Hinweis auf Gauss in diesem Zusammenhang verdanke ich Herrn Raymund Roth.
   

Mit Frame Mit Frame as PDF

gehe zu Combinatorics

gehe zu Übung 5-1 Anordnungsmöglichkeiten

© H. Föll (MaWi 1 Skript)