Editing TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS13/Beispiel 202

Jump to navigation Jump to search

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision Your text
Line 13: Line 13:
 
Um dieses Beispiel zu lösen, muss man zuerst verstehen, um welches Abzählproblem es sich handelt. Für die Vorstellung ist es hilfreich, wenn man sich das Schachbrettmuster als Tabelle mit <math>m = 6</math> Spalten und <math>n = 4</math> Zeilen vorstellt. Jede Zelle in dieser Tabelle hat dabei die Seitenlänge 1. (Mathematischer wäre die Vorstellung von <math>m \cdot n = 6 \cdot 4 = 24</math> Quadraten mit Seitenlänge 1, die ein Rechteck bilden, was aber auf das Gleiche hinausläuft.) Gesucht ist nun die Anzahl der Wege entlang der Ränder von links unten bis rechts oben. Dazu überlegen wir uns zuerst, wie man so einen Weg beschreiben könnte. Da wir den kürzesten Weg suchen, dürfen wir uns nur nach oben und nach rechts bewegen, es bietet sich also an die Buchstaben ''o'' für die Bewegung nach oben und den Buchstaben ''r'' für die Bewegung nach rechts zu verwenden. Ein kürzerster Weg wäre dann z. B. <math>\{ r, o, r, r, o, o, o, r, r, r \}</math>. Wie man sieht bzw. aus der Angabe entnehmen kann, müssen wir immer <math>n</math> Mal nach oben gehen und <math>m</math> Mal nach rechts. Das heißt also, dass die Menge '''immer''' <math>n</math> Mal <math>o</math> enthält und <math>m</math> Mal <math>r</math>. Im Fall (a) also beispielsweise <math>\{ r, r, r, r, r, r, o, o, o, o \}</math>.
 
Um dieses Beispiel zu lösen, muss man zuerst verstehen, um welches Abzählproblem es sich handelt. Für die Vorstellung ist es hilfreich, wenn man sich das Schachbrettmuster als Tabelle mit <math>m = 6</math> Spalten und <math>n = 4</math> Zeilen vorstellt. Jede Zelle in dieser Tabelle hat dabei die Seitenlänge 1. (Mathematischer wäre die Vorstellung von <math>m \cdot n = 6 \cdot 4 = 24</math> Quadraten mit Seitenlänge 1, die ein Rechteck bilden, was aber auf das Gleiche hinausläuft.) Gesucht ist nun die Anzahl der Wege entlang der Ränder von links unten bis rechts oben. Dazu überlegen wir uns zuerst, wie man so einen Weg beschreiben könnte. Da wir den kürzesten Weg suchen, dürfen wir uns nur nach oben und nach rechts bewegen, es bietet sich also an die Buchstaben ''o'' für die Bewegung nach oben und den Buchstaben ''r'' für die Bewegung nach rechts zu verwenden. Ein kürzerster Weg wäre dann z. B. <math>\{ r, o, r, r, o, o, o, r, r, r \}</math>. Wie man sieht bzw. aus der Angabe entnehmen kann, müssen wir immer <math>n</math> Mal nach oben gehen und <math>m</math> Mal nach rechts. Das heißt also, dass die Menge '''immer''' <math>n</math> Mal <math>o</math> enthält und <math>m</math> Mal <math>r</math>. Im Fall (a) also beispielsweise <math>\{ r, r, r, r, r, r, o, o, o, o \}</math>.
  
Dass die Menge für alle Lösungen ''immer'' die gleiche Anzahl an ''o'' (<math>n</math>) und ''r'' (<math>m</math>) enthält, sagt uns, dass es sich bei dem Abzählproblem um eine '''Permutation''' handelt. Warum eine Permutation? Wir entnehmen keine Elemente aus der Menge (und bilden damit eine neue Menge) sondern wollen nur alle möglichen Anordnungen der Elemente (''Permutationen'') berechnen. Nun müssen wir uns noch überlegen, ob sich alle Elemente voneinander unterscheiden (''Permutation ohne Wiederholung'') oder ob nicht-unterscheidbare (gleichartige) Elemente in der Menge sind (''Permutation mit Wiederholung''). Die einzelnen Elemente des Weges (die ''r'' bzw. ''o'') unterscheiden sich nicht, sie wiederholen sich also. Es handelt es sich also um eine '''Permutation mit Wiederholung'''. Eine Permutation mit Wiederholung ist wie folgt definiert:
+
Dass die Menge für alle Lösungen ''immer'' die gleiche Anzahl an ''o'' (<math>n</math>) und ''r'' (<math>m</math>) enthält, sagt uns, dass es sich bei dem Abzählproblem um eine '''Permutation''' handelt. Warum eine Permutation? Wir entnehmen keine Elemente aus der Menge (und bilden damit eine neue Menge) sondern wollen nur alle möglichen Anordnungen der Elemente ('''Permutationen''') berechnen. Nun müssen wir uns noch überlegen, ob sich alle Elemente voneinander unterscheiden (''Permutation ohne Wiederholung'') oder ob nicht-unterscheidbare (gleichartige) Elemente in der Menge sind (''Permutation mit Wiederholung''). Die einzelnen Elemente des Weges (die ''r'' bzw. ''o'') unterscheiden sich nicht. Es handelt es sich also um eine '''Permutation mit Wiederholung'''. Eine Permutation mit Wiederholung ist wie folgt definiert:
  
 
<div {{Definition}}>
 
<div {{Definition}}>

Please note that all contributions to VoWi are considered to be released under the GNU Free Documentation License 1.3 (see VoWi:Urheberrechte for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel Editing help (opens in new window)

Templates used on this page: