Doppeltes Abzählen

Beweisverfahren

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.