Lösungen zur Übung 5.3-1

1. Wieviel 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) · .... · (N – k + 1)} · {(N – k) · (N – k – 1) · ... · 1}
{(N – k) · (N – k – 1) · ... · 1}      
           
   =  N!
(N – k)!		        
   
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 - 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. Wieviel 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. Wieviel 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!
(N – k)! · 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. Wieviel 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 sotieren, 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 kmax1 = 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 = (N – 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 jetzt k2 = (2N – 3)/2 Arbeitsschritte machen.
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)  =  i = N
S
i = 1		 ki   =   1
2		   ·  i = 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 in einer graphischen Darstellung schlicht die entsprechende Fläche unter der Winkelhalbierenden zwischen den gegebenen Grenzen ist.
Das erledigen wir mit einem Integral; wir haben
 
 
K(N)  =  ½ ·   x = 2N – 2
ó
õ
x = N – 1
x · dx  =   ¼ · x2  ç
ç
 2N – 2

N – 1		   =  ¼(2N – 2)2 – ¼(N – 1)2   
                 
   =  3N2/4 –  N/2  +  3/4 
 
Wie ist das nun mit den Zeiten?
Vergleichen wir einfach den Aufwand a · N Socken zu sortieren mit dem Aufwand a mal N Socken zu sortieren; das ist natürlich einfach a · K(N)
Für das Aufwandsverhältnis K(a·N)/a · K(N) = A haben wir
 
A   =   K(aN)
a · K(N)		  =  3a2N2/4 –  aN/2  +  3/4 
3aN2/4 –  aN/2  +  3a/4 		  =  3a2N2 –  2aN  +  3 
3aN2 –  2aN  +  3a  		 »  a
 
Dabei unterstellen wir, dass die quadratischen Terme den Bruch dominieren.
Damit haben wir eine wesentliche haushaltstechnische Erkenntnis gewonnen: 100 Paar Socken zu sortiern dauert etwa 10 mal länger als 10 mal 10 Paar durchzugehen!
Oder, um es zu verallgemeinern: Ordnung wieder herzustellen wird quadratisch schwieriger, je länger man die Unordnung wachsen läßt.
 

Zum Index Zum Index

gehe zu Combinatorics

gehe zu Übung 5-1 Anordnungsmöglichkeiten

© H. Föll