Doppeltes Abzählen ist ein Beweisverfahren aus dem Gebiet der abzählenden Kombinatorik, das aber auch auf anderen Gebieten Anwendung findet. Das Prinzip besteht darin, die Mächtigkeit einer Menge auf zwei verschiedene Arten zu ermitteln. Die beiden Ergebnisse müssen dann gleich sein, so dass man eine Gleichung erhält.
Anwendung Bearbeiten
Das Beweisprinzip wird häufig verwendet, um einen gegebenen Ausdruck zu vereinfachen. Die Schwierigkeit besteht dann darin, eine geeignete Menge zu finden, deren Mächtigkeit einerseits gleich dem gegebenen Ausdruck ist, die sich andererseits auch auf eine andere Weise abzählen lässt, die zu einer einfacheren Formel führt. Solche Beweise sind häufig sehr kurz und leicht zu verstehen, da oft keinerlei komplexe mathematische Werkzeuge notwendig sind. Dagegen erfordert es aber oft viel Kreativität, um sie zu finden. Daher werden Aufgaben, die auf diesem Prinzip beruhen, auch häufig in mathematischen Schülerwettbewerben gestellt.
Beispiele Bearbeiten
Binomialkoeffizienten Bearbeiten
Die Methode kann verwendet werden, um viele Gleichungen mit Binomialkoeffizienten herzuleiten. Als Beispiel soll hier die Gleichung
dienen. Zum Beweis betrachten wir die Anzahl der Möglichkeiten aus einer Gruppe von Personen einen Ausschuss aus Personen und aus diesen wiederum einen Unterausschuss mit Personen auszuwählen.
- Einerseits können wir erst den Ausschuss auswählen. Dazu gibt es Möglichkeiten. Anschließend bestimmen wir den Unterausschuss. Hierzu gibt es – unabhängig von der Wahl des Ausschusses – jeweils Möglichkeiten, sodass die Gesamtzahl gerade der linken Seite der obigen Formel entspricht.
- Andererseits können wir auch zuerst den Unterausschuss bestimmen, wozu es Möglichkeiten gibt. Anschließend müssen wir die restlichen Mitglieder des Ausschusses aus den verbleibenden Personen auswählen. Dafür gibt es Möglichkeiten, sodass sich bei dieser Methode die rechte Seite der Gleichung als Gesamtzahl der Möglichkeiten ergibt.
Folglich sind die beiden Seiten der Formel tatsächlich gleich, die Gleichung wurde durch doppeltes Abzählen bewiesen.
Potenzsummen Bearbeiten
Auch die Faulhabersche Formel zur Berechnung von Potenzsummen lässt sich mit doppeltem Abzählen herleiten, hier exemplarisch für die Summe der ersten Quadratzahlen. Dazu betrachten wir die Mächtigkeit der Menge
der Tripel natürlicher Zahlen zwischen und , bei denen der letzte Eintrag der größte ist. Für gibt es für und unabhängig voneinander jeweils Möglichkeiten, sodass die Menge die Mächtigkeit
hat, also gerade die gesuchte Summe. Die Mächtigkeit lässt sich aber auch auf andere Weise bestimmen. Dazu unterscheiden wir drei Fälle: , und . Im ersten Fall gibt es Möglichkeiten Werte für zu wählen, in den beiden anderen jeweils . Es gilt also
Analog lassen sich mit längeren Tupeln auch die Summen höherer Potenzen bestimmen.
Quellen Bearbeiten
- Martin Aigner, Günter M. Ziegler: Das Buch der Beweise. Springer, Berlin 2004, ISBN 3-540-40185-7. Kapitel 25: Schubfachprinzip und doppeltes Abzählen, Kapitel 30: Cayleys Formel für die Anzahl der Bäume.
- Arthur Engel: Problem Solving Strategies. Springer 1998, ISBN 0-387-98219-1. Chapter 5: Enumerative Combinatorics.