fahren aber niemals Umwege, immer nur den kürzesten Weg. Den kürzesten Weg stimmt eigentlich nicht, weil es gibt ja meist mehrere verschiedene kürzeste Wege. Also zwischen diesem Punkt hier und diesem Punkt kann ich so fahren als Taxi, oder so fahren, oder so fahren.

Also es gibt unterschiedliche Wege, ich zeige vielleicht mal zwei Punkte ein. Also von Punkt A wollen wir vielleicht zum Punkt B gelangen, zu dem hier. Oder kann ich also hier runterfahren und nach rechts, also 3, 4, 5, 6, 7, Weglänge 7.

Oder ich fahre 1, 2, 3, 4, 5, 6, 7 und so weiter und so weiter. Wird nicht kein Wegfahren länger als 7, Taxifahrer und Taxifahrerinnen haben so einen Ehrenkodex. Die fahren jetzt nicht so den Umweg hier rum oder so. Okay, also und die Aufgabe ist jetzt die Frage, wie viele verschiedene Möglichkeiten gibt es,

um von A nach B auf den kürzesten Weg zu kommen. Das ist ein bisschen eine andere Aufgabe. Ich kriege jetzt nicht das komplette Netz von dem, was ihr hier machen solltet, hin. Aber das ist eine analoge Aufgabe, das passt schon nach.

Können wir uns das ein bisschen erklären? Okay, jetzt überlegen wir uns mal sukzessive, wie wir uns da ran tasten können. Frage an euch, wie viele verschiedene Wege gibt es von A zu diesem Punkt?

Einen, ne? Ich kann eigentlich nur den geraden Weg fahren hier. Also von da nach da gibt es einen Weg. Und nach da, von A zu diesem Punkt hier?

Auch nur einen, oder? Also hier oben kann ich eigentlich nur geradeaus fahren. Das ist bei allen Punkten so. Weil sobald ich mal diese gerade hier verlasse, fahre ich schon einen Umweg. Okay, wie viele Wege gibt es von A hier hin?

Einen und so weiter. Also hier unten das Gleiche, wenn ich jetzt nach unten fahre, sobald ich diese gerade verlasse, fahre ich einen Umweg. Darf ich nicht machen. Okay, wie viele verschiedene Wege gibt es hier hin? Zwei. Wie kommst du da drauf?

Ja, einmal so rum, einmal so rum. Jetzt wird es spannend. Das konnte man noch sehen. Wie viele verschiedene Wege gibt es hier hin?

Drei. Wieso? Genau, du hast die drei Wege nochmal gezählt. Also einmal hier rechts rum, einmal unten rum und einmal quasi durch die Mitte.

Okay. Stimmt, genau. Das sind drei Wege. Machen wir es nochmal hier. Wie viele Wege gibt es hier hin zu diesem Weg? Drei. Das ist gerade gespiegelt. Das ist dieselbe Situation, nur gespiegelt an dieser Achse hier.

Das können wir uns vielleicht erst schon mal merken. Wenn wir jetzt hier zu dem Punkt fahren, ist es das Gleiche, als wenn wir zu dem Punkt fahren würden. Einmal fahre ich die Strecke hier nach unten und nach rechts. Einmal fahre ich die Strecke entlang und nach unten. Okay. Wie viele verschiedene Wege, dann wird es jetzt spannend.

Wie viele verschiedene Wege gibt es zu diesem Punkt hier? Ohne sie zu zählen. Ich will erst die anfangen zu zählen. Ohne sie zu zählen. Wie viele verschiedene Wege gibt es zu diesem Punkt? Das kann man sich ganz einfach überlegen. Also es ist nicht ganz einfach. Wenn man es weiß, ist es ganz einfach.

Wenn man es nicht weiß, ist es nicht so einfach. Ja? Genau. Das sind sechs. Weil, um zu diesem Punkt zu kommen, von hier aus, muss ich entweder über diesen oder über diesen fahren. Es gibt keine andere Möglichkeit.

Entweder ich komme über diesen Punkt und muss nur noch nach rechts fahren. Oder ich komme über diesen Punkt und muss nur noch nach unten fahren. Über den kann ich nicht kommen, über den nicht, über den nicht, über den nicht und über den nicht. Also es gibt eigentlich nur zwei Zugangswege zu diesem Punkt, nämlich über diesen und über diesen. Zu diesem Punkt hier gibt es drei verschiedene Wege.

Und an jedem von den drei muss ich noch dieses Stück anhängen. Also wenn ich über diesen Punkt zu dem hier komme, gibt es drei verschiedene Wege. Nämlich die drei zu diesem Punkt, jeweils verlängert um diese Strecke. Dadurch gibt es ja keinen neuen Weg. Es gibt drei Wege hier hin. Also den hier verlängert oder den hier verlängert oder den hier verlängert.

Es gibt nur drei Wege hier hin, damit drei Wege hier hin, wenn ich über diesen Punkt komme. Genauso gibt es hier hin drei Wege, wenn ich über diesen Punkt komme. Hier nach rechts verlängert, so rum verlängert und quasi durch die Mitte verlängert.

Also muss ich einfach nur die beiden Zahlen addieren, um auf den nächsten Wert zu kommen. Die Anzahl der Möglichkeiten, zu den beiden Vorgängertaxipunkten zu kommen, addieren. Das alles.

Wie komme ich zu diesem Punkt? Über den oder über den? Also wie viele Möglichkeiten? Hier. Und jetzt können wir es nochmal ausfüllen. Da habe ich auch vier. Dann hier gibt es fünf. Da sind es fünf. Wie viele Möglichkeiten gibt es hier hin?

Zehn. Da hin. Auch zehn. Dann sind es hier fünfzehn. Und da sind es fünfzehn. Und hier hin sind es zwanzig. Und hier hin 35. Jetzt haben wir unsere Aufgabe gelöst, von A nach B zu kommen.

Es gibt auf 35 verschiedene Wege. 35 verschiedene Möglichkeiten. Gibt es da zu fragen? Wieso kann ich die beiden Vorgängerknoten addieren? Das ist klar geworden.

Das ist der Aufbau vom paskalischen Dreieck. Das kennt man. Wenn man hier oben die Spitze nimmt. Wie viele Möglichkeiten gibt es von A nach A zu kommen? Eine. Von der Spitze.

Wenn man sich jetzt alle den Kopf 45 Grad nach links legt. Das ist das paskalische Dreieck. Man kann sich also so vorarbeiten.

Umständlich wird es nur, wenn Punkt A und Punkt B 10768 Wegstrecken auseinander liegen. Dann muss ich halt ein richtig großes paskalisches Dreieck zeichnen.

Und immer wieder addieren und addieren und addieren und so weiter. Bis ich da hinten ankomme. Das geht schneller. Das ist ja irgendwie so etwas Rekursives. Ich muss echt, um auf hier hinten zu kommen. Muss ich alles vorher aufaddieren. Alles aufaddieren, bis ich da hinten rauskomme.

Es gibt aber auch so etwas wie eine explizite Formel. Um auf ein Element zu kommen. Weiß jemand, wie ich ein bestimmtes Element berechnen kann?

N über K. Genau. Die Frage ist nur, warum? Hä? N über K? Also irgendwie, wenn man N über K so ein paar ausrechnet, stellt man fest, die Zahlen kommen da alle vor.

Also das hier ist 2 über 1. Und dieses Element hier ist 3 über 1. Und das ist 4 über 1. Das ist 5 über 1.

Weiß jemand noch, welche kann ich da hinschreiben? Sieht jemand das Muster? Weiß jemand, was ich hinschreiben muss?

Also wir füllen das jetzt mal aus und später machen wir uns klar, warum das so ist. 2 über 0, genau. Hier ist 2 über 0. Hier ist 3 über 0. 4 über 0. 5 über 0 und so weiter. Dann ist das hier 1 über 1.

2 über 1, 3 über 1 und so weiter. Genau. Weiß jemand, was ich hier hinschreiben muss?

Genau, 2 über 2, 2 über 3, 2 über 4. Nein, Quatsch. Was habe ich denn hier gemacht für ein Quatsch? Oh Mann, das ist jetzt auf der Aufzeichnung drauf. Viel peinlich. 4 über 4 und so weiter. Wenn man jetzt mal so schräg schaut, fehlt noch der hier.

Was könnte das sein, wenn ich von 2 über 0 hier nach oben gehe oder von 1 über 1 nach links?

Warte, da stimmt was nicht. Hier haben wir uns vertan. Oh, hier haben wir uns vertan. Das ist 2 über 0. Also 2 über 0, 2 über 1, 2 über 2.

Das ist 1 über 0. 1 über 1. Und hier ist 3 über 0 und hier ist 4 über 0. Genau, so. Und dann ist hier oben 0 über 0, genau. So, jetzt ist es richtig.

Okay. Also wenn wir die Zeilen im paschalischen Dreieck betrachten, nimmt es von Zeile zu Zeile die Zahl oben um 1 zu. Wenn ich von links nach rechts laufe, nimmt die Zahl unten um 1 zu.

Das heißt, was muss hier hin? 3 über 2. Genau, 3 über 2. Und dann machen wir vielleicht die vierte Nummer fertig. Das ist 4 über 2, 4 über 3 und 4 über 4. Okay, gehen wir nochmal einen Schritt zurück.

Wir wissen, wie die einzelnen roten Zahlen zustande kommen. Das war relativ easy. Immer addieren die beiden Zahlen vorher, um auf die Anzahl der Möglichkeiten zu kommen. Auf die Anzahl der Möglichkeiten zu kommen. Hat irgendwas mit Kombinatorik zu tun. Wir wissen irgendwo her, vielleicht mal gelernt, in der Schule oder so, dass es mit binomialkoeffizienten auch aufgebaut werden kann, das paschalische Dreieck.

Das hat ja auch irgendwas mit Möglichkeiten zu tun. Okay? Was hat jetzt das eine mit dem anderen zu tun? Wieso sind das die binomialkoeffizienten? Was besagt denn ein binomialkoeffizient? Wenn ich n über k schreibe, was bedeutet das denn Inhalt nicht?

Wann verwendet man n über k in der Kombinatorik?

Richtig, genau. Beim Lotto ziehen 6 aus 49. Ich habe 49 Kugeln und von denen ziehe ich 6.

Wie viele Möglichkeiten gibt es? 49 über 6. Also ich ziehe aus 49 ohne Zurücklegen. Und die Reihenfolge ist egal.

Sehr gut, genau. Die Reihenfolge ist egal. Es ist egal. Erst mal wird die Kugel nicht mehr zurückgelegt. Eine Kugel kann nicht mehrfach beim Lotto gezogen werden. Wenn eine Kugel draußen ist, ist sie draußen. Und dann, wenn ich mal 6 Kugeln gezogen habe, ist es vollkommen egal,

in welcher Reihenfolge ich die gezogen habe. Ich habe gewonnen, wenn ich diese 6 Zahlen angekreuzt habe. Egal in welcher Reihenfolge. Um mal ein anderes Beispiel zu nehmen, vielleicht mit etwas kleineren Zahlen. Ich habe 5 Bücher und aus denen möchte ich, ich habe mehr als 5 Bücher, aber tun wir mal so. Ich habe 5 Bücher und aus denen möchte ich 2 mit auf die Reise nehmen.

Also Harry Potter 1 bis 5. Und ich möchte 2 Bücher mit auf eine Reise nehmen. Auf eine Zugfahrt oder so. 5 über 2 bedeutet ich wähle aus 5 Büchern 2 aus. Ohne Zurücklegen. Also wenn ich ein Harry Potter Band gezogen habe, lege ich den nicht nur mal zurück, um ihn nochmal zu ziehen.

Sondern ich will ja 2 Bücher aus dem Schrank holen. Und wenn ich 2 rausgeholt habe, ist die Reihenfolge egal. Denn, ob ich jetzt Band 2 und Band 4 ziehe oder Band 4 und Band 2, ich nehme am Ende immer beide mit auf die Fahrt. Okay. 5 über 2 heißt, ich wähle aus 5, 2 aus.

Ohne Zurücklegen, Reihenfolge egal. Wenn ihr nochmal die Formel sehen wollt, aber das ist eigentlich, brauchen wir an der Stelle eigentlich nicht. Aber ich schreibe es doch nochmal auf. Das ist N Fakultät durch N minus K Fakultät mal K Fakultät.

Das ist nur mal, falls ihr nochmal wissen wollt, wie waren nochmal die Formel und so weiter. Aber eigentlich brauchen wir es nicht. Okay, wir wählen aus 5, 2 aus. Man braucht es natürlich dann später, um es auszurechnen. Also wenn ich 5 über 2 rechne, dann muss ich 5 mal 4 mal 3 mal 2 mal 1 rechnen.

5 Fakultät durch 5 minus 2 Fakultät. Das ist 3 mal 2 mal 1. Und deswegen kann ich das hier wegstreichen.

Ich muss nur 5 mal 4 rechnen. Also N Fakultät durch N minus K Fakultät besagt, arbeite die Fakultät von vorne ab. Und zwar nimm so viele Zahlen, wie du auswählen willst. 5 mal 4, fertig. Und dann noch durch 2 Fakultät, also durch 2 mal 1,

um die vielenfältigen Möglichkeiten, wie ich zwei Bücher gezogen haben kann, rauszurechnen. Es gibt immer zwei Möglichkeiten. Entweder ich ziehe Harry Potter Band 3 als erstes und 4 als zweites. Oder 4 als erstes und 3 als zweites. Es gibt zwei Möglichkeiten. Das heißt, ich habe jede Möglichkeit doppelt gezählt. Also muss ich nochmal durch 2 teilen.

Dann komme ich insgesamt auf 10 Möglichkeiten. Ich kann mir aus 5 Harry Potter Bänden 10 Bücher mitnehmen. Und das nochmal, wie rechne man den Binomial-Koeffizienten aus? Okay. Aber das Entscheidende ist, wir wollen ja verstehen, was hat das hier mit den Binomial-Koeffizienten zu tun.

Ich wähle 2 aus 5 aus. Wo haben wir hier die 5 über 2? Die steckt hier. Sieht jemand von euch, was bedeutet die 5 und was bedeutet die 2? In dem Fall.

Sieht jemand? 2 was wähle ich aus 5 was aus. Ich will von da nach da. Wo kommt die 5 vor? Wo kommt die 2 vor?

Ja? Genau. Ich habe insgesamt 5 Wegstrecken zu laufen.

1, 2, 3, 4, 5. Und ich habe 2 Möglichkeiten. Entweder ich laufe nach unten oder nach rechts. An jeder Stelle. Ich kann nach unten laufen. Unten, unten, unten, unten. Rechts, rechts, rechts, rechts.

Und von hier nach da zu kommen, muss ich 3 mal nach unten laufen und 2 mal nach rechts. Also ich könnte zum Beispiel nach unten laufen und 2 mal nach rechts. Was wäre dieser Weg hier? Der da. Was wäre der Weg?

Wenn ich jetzt hier lang laufe, da lang erst und dann so. Rechts, rechts, unten, unten, unten. Was ist dieser Weg? Hm, hm, hm, hm, hm.

Rechts, unten, unten, rechts, unten. Was ist dieser Weg? Hm, hm, hm, hm, hm. Unten, unten, rechts, rechts, unten und so weiter und so weiter.

Ich habe 5 Wegstrecken und ich muss mir aussuchen, an welchen 2 von den 5 laufe ich nach rechts. Das sind die unterschiedlichen Möglichkeiten, die ich habe. 5 über 2. Ich muss 5 Wegstrecken laufen und innerhalb dieser 5 Wegstrecken 2 mal nach rechts.

Und ich weiß nicht genau ob an der ersten, zweiten, dritten, vierten oder fünften Stelle. Ich muss 2 aus 5 Stellen auswählen, an denen ich sage, ich laufe nach rechts. Wie viele Möglichkeiten gibt es? 5 über 2. Endlich verstanden. Endlich verstanden, dieses blöde paskalische Dreieck mit den Minimalkoeffizienzen. Und hier, genau, wenn wir jetzt hier hin wollen, was müssen wir rechnen zu unserem B?

Wir wollen von A nach B. Wie lang ist der Weg insgesamt?

7, also muss ich aus 7 Wegstrecken wie oft nach rechts laufen? Vorsicht, eins. Vier mal, genau. Hier ist 7 über 4, genau, weil hier ist 6 über 3. Und so weiter, also hier ist tatsächlich 7 über 4. 7 Wegstrecken, 4 nach rechts.

Rechnen wir das mal aus. Wir wollen rechnen 7 über 4. Also N über K, N ist 7, 4 ist K. Was muss ich rechnen? Trau dich.

Ja, genau. Und 7 minus 4 Fakultät ist?

3 Fakultät. Genau. Das ist ja 7 mal 6 mal 5 mal 4 mal 3 mal 2 mal 1. Durch 3 mal 2 mal 1, dann kann ich das weglassen und schreibe einfach in 7 mal 6 mal 5 mal 4.

Mal 3 mal 2 mal 1 lasse ich weg. Also das teile ich ja nochmal. Und dann durch 4 Fakultät, 4 mal 3 mal 2 mal 1. Weiter, wie geht es weiter?

Kürzt mal ein bisschen was. Die 4 fällt weg, okay. Die 1 ist sowieso Schwachsinn hier unten, genau. Jetzt habe ich noch 3 mal 2 da unten stehen. Und es bleibt übrig 7 mal 5 und das ist?

5 und 30. Genau. 5 und 30. Auf wie viele Arten kann ich bei 7 Wegstrecken hier mal nach rechts laufen? Okay, ja, genau.

Sehr gute Bemerkung. Man könnte ja auch sagen, er fängt jetzt ja an zu saugen.

Okay. Ich habe insgesamt 7 Wegstrecken zu laufen und ich muss 3 nach unten. Also, auf wie viele Arten kann ich 3 aus 7 auswählen? Das wäre 7 über 3. Muss das gleiche rauskommen? Klar, 7 über 3 ist das gleiche wie 7 über 4.

Das ist die Symmetrie von dem Pascalischen Dreieck. Ob ich zum Beispiel aus 4 Elementen 3 auswähle oder aus 4 Elementen 1 auswähle, ist egal. Das ist die komplementäre Frage. Wenn ich 3 ausgewählt habe, habe ich auch gleichzeitig 1 ausgewählt, nämlich dass das übrig geblieben ist und umgedreht.

Das heißt, klar, wäre vielleicht einfacher, wenn ich, keine Ahnung, 1.000 über 998 ausrechnen möchte, rechne ich 1.000 über 2 aus. Weil ich bin nicht blöd, ich will nicht so viel rechnen und es ist ein symmetrisches Problem. 1.000 über 998 könnte umständlich werden.

1.000 über 2 ist easy. 1.000 bei 999 durch 2, fertig.

Du hast ja das Netz vorgegeben. Taxigeometrie hast du irgendwie den Stadtplan von Manhattan und du willst vom Supermarkt zum Kino. Die liegen irgendwo im Stadtplan. Du weißt, die haben 40 Abstand und du siehst am Stadtplan, das Kino liegt 15 Straßen unterhalb.

Dann hast du sofort die Zahl, 40 und 15. Ja, genau. Du musst 2 Punkte vorgegeben haben im Netz, damit kannst du beide n und k bestimmen und damit kannst du es ausrechnen.

Okay, gibt es noch Fragen dazu? Okay, sehr schön, ich wollte unbedingt das mal als Video haben.