30 Tage kostenlos testen:
Mehr Spaß am Lernen.

Überzeugen Sie sich von der Qualität unserer Inhalte.

Ziehen ohne Zurücklegen und mit Beachtung Reihenfolge – Einführung 08:05 min

Textversion des Videos

Transkript Ziehen ohne Zurücklegen und mit Beachtung Reihenfolge – Einführung

Eagle und sein kleiner Bruder Quentin. Die gefährlichsten Brüder in Bad Fallingbostel. Allein der Klang ihrer Namen versetzt die Unterwelt in Angst und Schrecken. Eagle und Quentin liefern sich ein erbittertes Duell. Sie spielen drei gewinnt! Viele halten es für ein Glücksspiel aber nicht Quentin. Er weiß, dass man frühestens im fünften Zug gewinnen kann. Und um seine Chancen zu verbessern, hat er alle möglichen Spielanfänge bis einschließlich dem vierten Zug auswendig gelernt. Aber wie viele sind das? Um das herauszufinden, betrachten wir die Tabelle mit den vier Möglichkeiten, aus n Elementen k mal zu ziehen: Du kannst mit oder ohne Zurücklegen ziehen und jeweils mit oder ohne Beachtung der Reihenfolge. Um welchen Fall handelt es sich beim Drei Gewinnt? Wir übersetzen das Problem dafür mal in das Urnenmodell. Das gesamte Spielbrett entspricht der Urne. Die einzelnen Felder auf dem Spielbrett spielen die Rolle der Kugeln. Und das Auswählen eines Feldes für den jeweiligen Zug entspricht dem Ziehen der Kugeln aus der Urne. Beim Drei Gewinnt kann man jedes Feld nur einmal belegen. Also wird ein einmal gewähltes Feld nicht wieder frei es handelt sich also auf jeden Fall um 'ziehen ohne Zurücklegen'. Ein 'Ziehen mit Zurücklegen' wäre es dagegen, wenn man jedes Feld mehrmals belegen könnte. Die Reihenfolge der Spielzüge macht natürlich einen Unterschied, denn es ist wichtig, ob Quentin oder Eagle einen Stein gesetzt hat. Wäre die Reihenfolge nicht wichtig, wäre es auch völlig egal wer welchen Stein setzt. Also wissen wir, dass es sich um 'Ziehen ohne Zurücklegen und mit Beachtung der Reihenfolge' handelt. Aus der Tabelle lesen wir ab, dass es 'n über k mal k Fakultät' viele Möglichkeiten gibt, aus n Elementen k-mal ohne Zurücklegen und mit Beachtung der Reihenfolge zu ziehen. Na, dann rechnen wir mal aus, wie viele Spielzüge Quentin im Kopf haben muss. Zuerst wandeln wir 'n über k' in einen Bruch um. 'n über k' ist gleich 'n Fakultät geteilt durch k Fakultät mal (n minus k) Fakultät'. Also können wir 'k Fakultät' kürzen und übrig bleibt 'n Fakultät durch (n minus k) Fakultät'. Aber was sind n und k? n ist die Anzahl der möglichen Felder, die man belegen kann – also 9. Und k ist die Anzahl der Spielzüge. Quentin hat sich alle Spiele bis einschließlich Zug 4 gemerkt – also ist k gleich 4. Setzen wir 9 und 4 in die Formel ein können wir im Nenner vereinfachen und dann die Fakultäten berechnen. Fällt dir etwas auf? Im Zähler und im Nenner steht das Produkt '5 mal 4 mal 3 mal 2 mal 1' – das können wir kürzen! Damit bleibt 9 mal 8 mal 7 mal 6. Und das ergibt 3024. Also muss sich Quentin insgesamt 3024 Spielanfänge merken! Da kracht es sicher schon im Gangsterhirn! Aber wie kommt diese Formel denn zustande? Im ersten Zug gibt es 9 freie Felder, also 9 Möglichkeiten. Egal, welches Feld man belegt, im nächsten Schritt gibt es dann noch 8 freie Felder. Und so geht es weiter – würden wir also alle Felder belegen, hätten wir 9 Fakultät viele Möglichkeiten. Aber Quentin merkt sich nur die ersten 4 Schritte. Also gibt es 9 mal 8 mal 7 mal 6 viele Möglichkeiten. Und das ist das gleiche wie '9 Fakultät durch 5 Fakultät' und das ist dann das gleiche wie (9 minus 4) Fakultät', also genau unsere Formel. Übrigens kannst du dir den Ausdruck auch so merken: Wenn du aus n Elementen k mal ohne Zurücklegen und mit Beachtung der Reihenfolge ziehst, schreibst du 'n Fakultät' als Produkt auf und streichst alles, bis auf die größten k Faktoren weg. Eagle unterdessen kennt seinen jüngeren Bruder zu gut für solche Späße. Und statt in die Falle mit den vorbereiteten Spielzügen zu tappen macht er aus Drei Gewinnt Vier Gewinnt! Ob Quentin auch hier schon alle Eröffnungszüge auswendig gelernt hat? Wie viele können das wohl sein? Die Formel ist wieder die gleiche – n Fakultät durch 'n Minus k' Fakultät. Aber jetzt gibt es 16 mögliche Spielfelder – also ist n gleich 16! Und gewinnen kann man erst ab dem siebten Zug! Quentin müsste sich also alle möglichen Spielzüge bis einschließlich Zug Nummer 6 merken. Dann rechnen wir mal: Wir setzen für n 16 ein und für k 6 schreiben die Fakultät aus kürzen und kommen damit auf 5.765.760 Züge! Niemals kann Quentin so viele Eröffnungen im Kopf haben! Und während Quentin noch überlegt, ob er die Niederlage irgendwie abwenden kann, fassen wir zusammen. Bei Kombinatorikaufgaben, also wenn du Möglichkeiten bei vertrackten Ziehverfahren bestimmen sollst überlegst du immer, ob die Reihenfolge beim Ziehen eine Rolle spielt und ob zurückgelegt wird. Wenn nicht zurückgelegt wird, aber die Reihenfolge eine Rolle spielt gibt es 'n über k mal k Fakultät' viele Möglichkeiten, aus n Elementen k mal zu ziehen. Das kannst du dir auch als Bruch merken oder als die größten k Faktoren von n Fakultät. Ein anderes Beispiel ist die Rangliste der Teilnehmer eines Wettbewerbs. Da jede Platzierung nur einmal vergeben wird, handelt es sich dabei um Ziehen ohne Zurücklegen. Und die Reihenfolge der Siegerplätze ist natürlich von Bedeutung. Wie steht es wohl um Quentins Chancen? Nicht so gut. Aber worum können Eagle und Quentin nur gespielt haben? Um die zweifelhafte Ehre ihrer alten Oma im Altersheim ein Geburtstagsständchen darbieten zu dürfen. Und Eagle kann sich entspannt zurücklegen.