Doppeltes Abzählen

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

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

Binomialkoeffizienten

Die Methode kann verwendet werden, um viele Gleichungen mit Binomialkoeffizienten herzuleiten. Als Beispiel soll hier die Gleichung

${n \choose m}{m \choose k}={n \choose k}{n-k \choose m-k}$

dienen. Zum Beweis betrachten wir die Anzahl der Möglichkeiten aus einer Gruppe von $n$ Personen einen Ausschuss aus $m$ Personen und aus diesen wiederum einen Unterausschuss mit $k$ Personen auszuwählen.

• Einerseits können wir erst den Ausschuss auswählen. Dazu gibt es ${\tbinom {n}{m}}$ Möglichkeiten. Anschließend bestimmen wir den Unterausschuss. Hierzu gibt es – unabhängig von der Wahl des Ausschusses – jeweils ${\tbinom {m}{k}}$ Möglichkeiten, sodass die Gesamtzahl gerade der linken Seite der obigen Formel entspricht.

• Andererseits können wir auch zuerst den Unterausschuss bestimmen, wozu es ${\tbinom {n}{k}}$ Möglichkeiten gibt. Anschließend müssen wir die restlichen $m-k$ Mitglieder des Ausschusses aus den verbleibenden $n-k$ Personen auswählen. Dafür gibt es ${\tbinom {n-k}{m-k}}$ 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

Auch die Faulhabersche Formel zur Berechnung von Potenzsummen lässt sich mit doppeltem Abzählen herleiten, hier exemplarisch für die Summe der ersten $n$ Quadratzahlen. Dazu betrachten wir die Mächtigkeit der Menge

$M=\{(x,y,z)\in \mathbb {N} ^{3}|1\leq x,y,z\leq n+1,x<z,y<z\}$

der Tripel natürlicher Zahlen zwischen $1$ und $n+1$, bei denen der letzte Eintrag der größte ist. Für $z=k+1$ gibt es für $x$ und $y$ unabhängig voneinander jeweils $k$ Möglichkeiten, sodass die Menge die Mächtigkeit

$|M|=\sum _{k=1}^{n}k^{2}$

hat, also gerade die gesuchte Summe. Die Mächtigkeit lässt sich aber auch auf andere Weise bestimmen. Dazu unterscheiden wir drei Fälle: $x=y<z$, $x<y<z$ und $y<x<z$. Im ersten Fall gibt es ${\tbinom {n+1}{2}}$ Möglichkeiten Werte für $(x,y,z)$ zu wählen, in den beiden anderen jeweils ${\tbinom {n+1}{3}}$. Es gilt also

$|M|=\sum _{k=1}^{n}k^{2}={n+1 \choose 2}+2{n+1 \choose 3}={\frac {1}{3}}n^{3}+{\frac {1}{2}}n^{2}+{\frac {1}{6}}n$.

Analog lassen sich mit längeren Tupeln auch die Summen höherer Potenzen bestimmen.

Quellen

• 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.