WEBVTT 00:01.260 --> 00:04.440 Ganz herzlich willkommen zu einem weiteren Video über 00:04.440 --> 00:06.040 Binomialkoeffizienten. 00:06.220 --> 00:10.980 Bei diesem Thema ist es ja so, dass man in erster Linie das Konzept 00:10.980 --> 00:12.260 verstanden haben muss. 00:12.660 --> 00:15.780 Rechnen können Computer nämlich viel besser als wir. 00:16.520 --> 00:20.920 Hat man verstanden, was ein Binomialkoeffizient ist, kann man sehr 00:20.920 --> 00:26.060 schnell eine Antwort auf die Frage geben, warum für jede natürliche 00:26.060 --> 00:31.680 Zahl n 2n über n gleich der Summe der Quadrate der 00:31.680 --> 00:37.840 Binomialkoeffizienten n über k ist, wobei über k von 0 bis n summiert 00:37.840 --> 00:38.140 wird. 00:38.860 --> 00:42.740 Nun, was ist die linke Seite, also 2n über n? 00:43.560 --> 00:48.780 Wer mein Video Binomialkoeffizienten verstehen oder rechnen gesehen 00:48.780 --> 00:53.460 hat, weiß, dass dieser Binomialkoeffizient gleich der Anzahl aller 00:53.460 --> 00:57.920 binären 2n-Tupel mit genau n Einsen ist. 00:58.700 --> 01:02.860 Konkret ist das hier ein binäres 10-Tupel mit 5 Einsen. 01:03.540 --> 01:07.420 Ortet man den 10 Plätzen dieses Tupels von links nach rechts gesehen 01:07.420 --> 01:13.100 10 Dinge zu, die von 1 bis 10 nummeriert sind, so zeigt dieses Tupel 01:13.100 --> 01:20.940 über die Einsen an, dass die Dinge 1, 5, 6, 8 und 10 ausgewählt worden 01:20.940 --> 01:21.280 sind. 01:21.920 --> 01:25.320 Binäre n-Tupel beschreiben also Teilmengen von Mengen. 01:26.240 --> 01:31.920 Wieso ist nun 2n über n gleich der oben stehenden über k laufenden 01:31.920 --> 01:32.420 Summe? 01:33.440 --> 01:37.620 Diese Gleichung schreit geradezu nach einer Fallunterscheidung. 01:37.620 --> 01:44.000 Wir unterscheiden die binären 2n-Tupel mit n Einsen danach, wie viele 01:44.000 --> 01:49.160 der Einsen an den ersten n Stellen stehen und wir nennen diese Anzahl 01:49.160 --> 01:49.640 k. 01:50.700 --> 01:53.860 Dabei kann k jeden Wert von 0 bis n annehmen. 01:55.520 --> 01:59.260 Was ist denn das Produkt dieser beiden Binomialkoeffizienten? 01:59.260 --> 02:05.520 Nun, es ist die Anzahl aller binären 2n-Tupel, die an den ersten n 02:05.520 --> 02:11.580 Stellen genau k Einsen und an den letzten n Stellen genau n-k Einsen 02:11.580 --> 02:11.900 haben. 02:12.560 --> 02:16.980 Der Binomialkoeffizient n über k ist ja die Anzahl der Möglichkeiten, 02:17.680 --> 02:22.100 aus den ersten n Stellen des Tupels k für Einsen auszuwählen. 02:22.100 --> 02:28.640 Für jede solche Auswahl gibt es dann n über n-k Möglichkeiten, aus den 02:28.640 --> 02:32.480 letzten n Stellen n-k für Einsen zu wählen. 02:32.980 --> 02:37.480 Damit sind im 2n-Tupel genau n Einsen vorhanden. 02:37.620 --> 02:40.840 Beachten wir jetzt noch die durch Flippen der Einsen und Nullen 02:40.840 --> 02:45.660 entstehende Gleichung n über n-k gleich n über k. 02:45.660 --> 02:49.840 So folgt die Behauptung, denn bei der Fallunterscheidung müssen wir 02:49.840 --> 02:51.960 über die Werte von k summieren. 02:54.360 --> 02:58.460 Selbstverständlich kann man versuchen, die obige Gleichung mithilfe 02:58.460 --> 03:00.580 vollständiger Induktion zu beweisen. 03:01.280 --> 03:06.400 Man erhält aber damit keinerlei Einsicht, warum diese Gleichung gilt.