Wegezählung in einem Raster - wie lässt sich dieser Ansatz beweisen?

Ich habe mir kürzlich ein Video über die Khan-Akademie angesehen, in dem er ein Problem durcharbeitet, bei dem es darum geht, alle möglichen Pfade in einem n X n-Raster von der oberen linken Position zur unteren rechten Position zu finden, indem er nur nach unten oder rechts geht.

Im Grunde basiert sein Ansatz darauf, das Pascal-Dreieck zu verwenden und die Wege zu zählen, um eine bestimmte Position zu erreichen, und sie zu der Anzahl der bisherigen Wege hinzuzufügen.

Ich begann mich dafür zu interessieren und versuchte, eine Formel zu verallgemeinern, um die Anzahl möglicher Pfade in einem X-m-Gitter zu finden.

Meine Idee ist folgende: Nehmen wir ein 2 x 3 Raster an. Wir beginnen oben links und müssen nach unten rechts gehen (vorausgesetzt, wir können uns nur nach rechts / unten bewegen). Ein möglicher Weg wäre

  1. runter
  2. runter
  3. Rechts
  4. Rechts
  5. Rechts

Wie sich herausstellt, haben in diesem Fall alle möglichen Pfade in einem 2 x 3-Gitter eine Länge von n + m = 5.

Wenn wir die Bewegung durch das Raster als eine Art Befehlsfolge (unten/rechts) sehen, können wir alle möglichen Permutationen von unten/rechts durch Berechnung finden ( N + M ) ! Zum Beispiel rechnen wir im 2 x 3-Raster 5 ! , das würde uns alle möglichen Permutationen von geben

  1. runter 1
  2. runter 2
  3. richtig 1
  4. rechts 2
  5. rechts 3

Allerdings würde das auch runter2, runter1, ... als gültige Kombination zählen, was es nicht ist, man darf höchstens 2 mal runter gehen, muss aber mit runter1 von der Startposition aus starten. Die verfeinerte Formel sieht folgendermaßen aus (um einzigartige Befehlskombinationen zu erhalten):

( N + M ) ! ÷ ( N ! M ! )

In einem quadratischen 5 x 5-Raster würde das Obige 252 ergeben, in einem 2 x 3-Raster wären es 10 Pfade. Soweit ich sehen kann, scheint das ein richtiger Ansatz zu sein, zumindest anhand einiger Beispiele, die ich ausprobiert habe.

Mein nächster Schritt war, zu versuchen, einen Beweis dafür zu schreiben, ich dachte, vielleicht wäre ein Beweis durch Induktion möglich? Aber meine Frage Frage ist, was ist N in diesem Fall (Schritte? Rastergröße?), ob ich dafür einen Beweis schreiben möchte? Oder ist in diesem Fall keine Induktion möglich?

Ich vermute, Sie werden für diesen Beweis die strukturelle Induktion verwenden wollen.
Induktion ist hier nicht der natürliche Weg. Merke das einfach ab N + M Schritte genau N muss das Label "unten" bekommen. Es gibt ( N + M N ) Wege zu wählen N aus N + M .

Antworten (2)

Vielleicht erfüllt dieses Beispiel Ihren Bedarf.

Nehme an, dass 3 aus den Zahlen drin { 1 , … , 5 } muss ausgewählt werden.

Wir können damit beginnen, die Zahlen in allen möglichen Reihenfolgen zu schreiben und dann die auszuwählen 3 ganz links als die Ausgewählten. Es gibt 5 ! = 120 Bestellungen und wir bekommen so etwas wie:

  • 123|45
  • 123|54
  • ...
  • 543|21

Beachten Sie nun, dass zB die Ordnungen 12345 und 12354 beide zur Auswahl 123 führen. Fragen Sie sich nun, wie viele Ordnungen gefunden werden können, die die Auswahl 123 ergeben. Für die Ordnung der Zahlen 1,2,3 gibt es 3 ! = 6 Möglichkeiten und für die Reihenfolge der Nummern 4,5 gibt es 2 ! = 2 Möglichkeiten. Das bedeutet, dass die Auswahl 123 das Ergebnis von ist 3 ! 2 ! des 5 ! Anordnungen. Um dieses Überzählen zu beheben, dividieren wir durch 3 ! 2 ! und wir enden mit 5 ! 3 ! 2 ! unterschiedliche Auswahlen.

Oh wow, jetzt hat es geklickt, warum ich die Teilung eigentlich brauche. Ich habe es gerade in der Gliederung meiner Formel getan, weil ich mich erinnere, dass Sie das tun, um "Duplikate zu entfernen", aber jetzt macht es tatsächlich Sinn. Danke! Da der Beweis durch Induktion nicht anwendbar ist, würde Ihre Erklärung in dieser Form formaler als "Beweis" akzeptiert (nur gefragt, ich bin wirklich neu und unerfahren).
Froh, dass ich Helfen kann. Dies wird als "Beweis" akzeptiert. Ich persönlich würde sagen: N des M + N Schritte müssen ausgewählt werden und es gibt ( N + M N ) = ( N + M ) ! N ! M ! Möglichkeiten, das zu tun, Punkt. Das reicht meiner Meinung nach schon. Wenn "sie" mehr wollen und fragen, wie sie das bekommen, dann würde ich dieses Beispiel verwenden, um es zu erklären.

Hinweise für Ihren Nachweis:

  1. Sie haben richtig erkannt, dass jeder Pfad aus ( 0 , 0 ) durch ( N , M ) kann als Permutation von ausgedrückt werden N rightsUnd M lefts.
  2. Was Sie jedoch nicht richtig verstanden haben, ist die Tatsache, dass alle gleichwertigrights sind und alle gleichwertig sind , dh gleich sinddownsdown1down2
  3. Auf wie viele Arten können Sie permutieren M + N Gegenstände aus denen M sind von einer Art und N sind von einem anderen?
Wegezählung in einem Raster - wie lässt sich dieser Ansatz beweisen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v