Wie viele Wege kann ich im folgenden Diagramm von 1 bis 10 gehen?

Question

Wie viele Wege kann ich im folgenden Diagramm von 1 bis 10 gehen?

Mathematik
Kombinationen
Wettbewerb-Mathematik
Kombinatorik
Binomialsatz
Binomialkoeffizienten

Benutzer3347814

Das ist eine Grundfrage der Kombinatorik mit einem kleinen Trick. Betrachten Sie die folgende dreieckige Anordnung von Zahlen:

Wie viele Wege von einer 1 auf der Diagonale bis zur 10 unten rechts, wo wir nur nach rechts oder unten gehen, gibt es? Hier ist zum Beispiel ein legaler Weg:

Batominovskis Bearbeitung:

Versuch: Es sieht so aus, als ob jeder Pfad mit einer Abfolge von Abwärtsschritten verknüpft ist ( $D$ ) und richtige Schritte ( $R$ ) Länge $9$ . Das obige Beispiel entspricht $DRDDDRRDD$ . Darf es eine beliebige Reihenfolge sein? Was ist eine richtige Antwort?

Benutzer3347814

Hinzufügen der Möglichkeiten für jede Zahl 1. Die erste hat 1, die zweite hat 9 und dann bin ich bei der dritten hängen geblieben und konnte kein Muster finden.

Culver Kwan

Bitte fügen Sie Ihren Versuch in Ihre Frage ein, die Ablehnungen zu entfernen.

Antworten (2)

Wie viele Wege kann ich im folgenden Diagramm von 1 bis 10 gehen?

Hinzufügen der Möglichkeiten für jede Zahl 1. Die erste hat 1, die zweite hat 9 und dann bin ich bei der dritten hängen geblieben und konnte kein Muster finden.
Bitte fügen Sie Ihren Versuch in Ihre Frage ein, die Ablehnungen zu entfernen.

Culver Kwan · Answer 1

Culver Kwan

Sie können denken, das Problem beginne mit dem $10$ und folgen Sie den Nummern der Reihe nach, bis Sie erreichen $1$ .

Dann gibt es zwei Möglichkeiten für jeden Schritt: nach oben oder links. Dann gibt es $2^{10-1}=2^9=512$ Wege. Erledigt!

Benutzer3347814

Ich weiß, dass die Antwort richtig ist. Aber ich kann daraus keinen intuitiven Sinn ableiten. Gibt es eine andere Möglichkeit, dieses Problem zu lösen?

Jyrki Lahtonen

@ user3347814 Eine andere Möglichkeit besteht darin, dies zu beobachten, wenn Sie bei "1" beginnen

n

$n$ Etage (

n = 0

$n=0$ im Erdgeschoss), dann brauchen Sie

9

$9$ Stufen zu erreichen

10

$10$ . Aus diesen neun Schritten,

n

$n$ nach unten gehen, und Sie können frei wählen, wann Sie nach unten gehen, also gibt es insgesamt

(\binom{9}{n})

$\binom 9n$ Pfade ausgehend von diesem bestimmten

1

$1$ . Somit ist die Gesamtzahl der Pfade

\sum_{N = 0}^{9} (\binom{9}{N}) = (1 + 1)^{9} = 2^{9}

$\sum_{n=0}^9\binom 9n=(1+1)^9=2^9$ nach der Binomialformel. Ehrlich gesagt denke ich, dass wir Culver Kwans Antwort in diesem Fall als eleganten Beweis für die Binomialformel betrachten sollten. Ich würde kein anderes Argument für wirklich vorzeigbar halten.

Jyrki Lahtonen

Und wenn das Argument führt

(\binom{9}{n})

$\binom 9n$ ist nicht klar, schau dir das an . Es ist dieselbe Idee.

ToniK

@ user3347814: Diese Antwort ist der Weg, um über das Problem nachzudenken: Verfolgen Sie Ihre Schritte von der

10

$10$ zurück zu a

1

$1$ . Sie werden keine einfachere Lösung finden!

Steven Alexis Gregory · Answer 2

Jedes Quadrat zeigt die Anzahl der (legalen) Wege zu diesem Quadrat.

Die Anzahl der möglichen Wege zum unteren rechten Quadrat beträgt also 512.

Dies könnte konkreter werden, indem darauf hingewiesen wird, dass die Anzahl der Wege, um ein Quadrat zu erreichen, die Summe der Anzahl der Wege ist, um die Quadrate über und links von diesem Quadrat zu erreichen.

Wie viele Wege kann ich im folgenden Diagramm von 1 bis 10 gehen?

Benutzer3347814

Benutzer3347814

Culver Kwan

Antworten (2)

Culver Kwan

Benutzer3347814

Jyrki Lahtonen

Jyrki Lahtonen

ToniK

Steven Alexis Gregory

Bernhard Bärker

Binomial-/Kombinatorik-Summationsbeweisfrage

Beweis interessanter Identität mit Teilsummen von Pascals Dreiecksreihen

Gibt es Machtidentitäten, die nicht auf dieser Liste stehen?

Wie man beweist, dass (nr)(nr)n \choose r = n+1−rrn+1−rr\frac{n+1-r}{r} (nr−1)(nr−1)n \choose r -1 ohne Verwendung der Fakultätserweiterung von (nr)(nr)n \choose r? [geschlossen]

Beweisen Sie, dass ∑k=0r(n+kk)=(n+r+1r)∑k=0r(n+kk)=(n+r+1r)\sum\limits_{k=0}^r\binom{ n+k}k=\binom{n+r+1}r mit kombinatorischen Argumenten. [Duplikat]

Menschen sitzen um dreieckige Tische

Beweis der Identität für den Binomialkoeffizienten mit der Generierungsfunktion

Beweisen Sie, dass ∑n−rk=0(r+kr)=(n+1r+1)∑k=0n−r(r+kr)=(n+1r+1)\sum_{k=0}^{nr } \binom{r+k}{r} = \binom{n+1}{r+1}

Wege durch ein Schachbrett zählen (nur diagonal bewegen)

Kombinatorische Identität durch Quadrieren der Binomialentwicklung