In combinatorics, dem doppelten Zählen, hat auch das Zählen auf zwei Weisen genannt, ist eine kombinatorische Probetechnik, um zu zeigen, dass zwei Ausdrücke durch das Demonstrieren gleich sind, dass sie zwei Weisen sind, die Größe eines Satzes aufzuzählen. In dieser Technik, die "eines der wichtigsten Werkzeuge in combinatorics nennen," beschreibt man einen begrenzten Satz X von zwei Perspektiven, die zu zwei verschiedenen Ausdrücken für die Größe des Satzes führen. Da beide Ausdrücke der Größe desselben Satzes gleichkommen, kommen sie einander gleich.

Beispiele

Das Formen von Komitees

Ein Beispiel der doppelten zählenden Methode zählt die Zahl von Wegen auf, auf die ein Komitee von n Leuten gebildet werden kann, jeder Zahl der Leute (sogar Null von ihnen) erlaubend, ein Teil des Komitees zu sein. D. h. man zählt die Zahl von Teilmengen auf, die ein N-Element-Satz haben kann. Eine Methode, für ein Komitee zu bilden, soll jede Person bitten zu wählen, ob man sich ihm anschließt. Jede Person hat zwei Wahlen - ja oder nein - und diese Wahlen sind von denjenigen der anderen Leute unabhängig. Deshalb gibt es 2 × 2 ×... × 2 = 2 Möglichkeiten. Wechselweise kann man bemerken, dass die Größe des Komitees eine Zahl zwischen 0 und n sein muss. Für jede mögliche Größe k ist die Zahl von Wegen, auf die ein Komitee von k Leuten von n Leuten gebildet werden kann, der binomische Koeffizient

Deshalb ist die Gesamtzahl von möglichen Komitees die Summe von binomischen Koeffizienten über k = 0, 1, 2... n. Gleichstellung der zwei Ausdrücke gibt die Identität

ein spezieller Fall des binomischen Lehrsatzes. Eine ähnliche doppelte zählende Methode kann verwendet werden, um die allgemeinere Identität zu beweisen

.

Lemma von Handshaking

Ein anderer Lehrsatz, der mit einem doppelten zählenden Argument allgemein bewiesen wird, stellt fest, dass jeder ungeleitete Graph eine gerade Zahl von Scheitelpunkten des sonderbaren Grads enthält. D. h. die Zahl von Scheitelpunkten, die eine ungerade Zahl von Ereignis-Rändern haben, muss gleich sein. In mehr umgangssprachlichen Begriffen in einer Partei von Leuten, von denen einige sich die Hände schütteln, muss eine gerade Zahl von Leuten eine ungerade Zahl der Hände anderer Leute geschüttelt haben; aus diesem Grund ist das Ergebnis als das handshaking Lemma bekannt.

Um das durch das doppelte Zählen zu beweisen, lassen Sie d (v) der Grad des Scheitelpunkts v sein. Die Zahl von Vorkommen des Scheitelpunkt-Randes im Graphen kann auf zwei verschiedene Weisen aufgezählt werden: durch das Summieren der Grade der Scheitelpunkte, oder durch das Zählen von zwei Vorkommen für jeden Rand. Deshalb

wo e die Zahl von Rändern ist. Die Summe der Grade der Scheitelpunkte ist deshalb eine gerade Zahl, die nicht geschehen konnte, wenn eine ungerade Zahl der Scheitelpunkte sonderbaren Grad hatte. Diese Tatsache, mit diesem Beweis, erscheint in der 1736-Zeitung von Leonhard Euler auf den Sieben Brücken von Königsberg, der zuerst die Studie der Graph-Theorie begonnen hat.

Das Aufzählen von Bäumen

Wie ist die Nummer T von verschiedenen Bäumen, die können von einer Reihe n verschiedener Scheitelpunkte gebildet werden? Die Formel von Cayley gibt die Antwort. verzeichnen Sie vier Beweise dieser Tatsache; sie schreiben über das vierte, ein doppelter zählender Beweis wegen Jim Pitmans, dass es von ihnen allen "am schönsten ist."

Der Beweis des Bergmannes zählt auf zwei verschiedene Weisen die Zahl von verschiedenen Folgen von geleiteten Rändern auf, die zu einem leeren Graphen auf n Scheitelpunkten hinzugefügt werden können, um davon einen eingewurzelten Baum zu bilden. Eine Weise, solch eine Folge zu bilden, soll mit einem der T möglichen uneingewurzelten Bäume anfangen, einen seiner n Scheitelpunkte als Wurzel wählen, und eine der möglichen Folgen wählen, in denen man seine Ränder hinzufügt. Deshalb ist die Gesamtzahl von Folgen, die auf diese Weise gebildet werden können.

Eine andere Weise, diese Rand-Folgen aufzuzählen, soll denken, die Ränder eins nach dem anderen zu einem leeren Graphen hinzuzufügen, und die Zahl von an jedem Schritt verfügbaren Wahlen aufzuzählen. Wenn man eine Sammlung von Rändern bereits hinzugefügt hat, so dass der durch diese Ränder gebildete Graph ein eingewurzelter Wald mit k Bäumen ist, gibt es Wahlen für den folgenden Rand, um beizutragen: Sein Startscheitelpunkt kann irgendwelche der n Scheitelpunkte des Graphen sein, und sein endender Scheitelpunkt kann irgendwelche der K-Wurzeln außer der Wurzel des Baums sein, der den Startscheitelpunkt enthält. Deshalb, wenn man zusammen die Zahl von Wahlen vom ersten Schritt, dem zweiten Schritt usw. multipliziert, ist die Gesamtzahl von Wahlen

Gleichstellung dieser zwei Formeln für die Zahl von Rand-Folgen läuft auf die Formel von Cayley hinaus:

und

Wie Aigner und Ziegler beschreiben, können die Formel und der Beweis verallgemeinert werden, um die Zahl von eingewurzelten Wäldern mit k Bäumen für jeden k aufzuzählen.

Siehe auch

Zusätzliche Beispiele

• Die Identität von Vandermonde, eine andere Identität auf Summen von binomischen Koeffizienten, die durch das doppelte Zählen bewiesen werden können.
• Quadrieren Sie pyramidale Zahl. Die Gleichheit zwischen der Summe der ersten n Quadratzahlen und einem Kubikpolynom kann durch das doppelte Zählen des Verdreifachens von Nummern x, y und z gezeigt werden, wo z größer ist als jede der anderen zwei Zahlen.
• Lubell-Yamamoto-Meshalkin-Ungleichheit. Der Beweis von Lubell dieses Ergebnisses auf Satz-Familien ist ein doppeltes zählendes Argument auf Versetzungen, verwendet, um eine Ungleichheit aber nicht eine Gleichheit zu beweisen.
• Beweise des kleinen Lehrsatzes von Fermat. Ein Teilbarkeitsbeweis durch das doppelte Zählen: Für jeden ersten p und natürliche Zahl A gibt es Wörter der Länge-p über ein A-Symbol-Alphabet, das zwei oder mehr verschiedene Symbole hat. Diese können in Sätze von p Wörtern gruppiert werden, die in einander durch kreisförmige Verschiebungen umgestaltet werden können; diese Sätze werden Ketten genannt. Deshalb, Ketten), und ist durch p teilbar.
• Beweise der quadratischen Reziprozität. Ein Beweis durch Eisenstein leitet eine andere wichtige mit der Zahl theoretische Tatsache durch doppelte zählende Gitter-Punkte in einem Dreieck ab.

Zusammenhängende Themen

• Bijektiver Beweis. Wo das doppelte Zählen mit dem Zählen des Derjenige-Satzes auf zwei Weisen verbunden ist, schließen bijektive Beweise das Zählen von zwei Sätzen auf eine Weise durch die Vertretung ein, dass ihre Elemente ein für einen entsprechen.
• Der Einschließungsausschluss-Grundsatz, eine Formel für die Größe einer Vereinigung von Sätzen, die zusammen mit einer anderen Formel für dieselbe Vereinigung können, als ein Teil eines doppelten zählenden Arguments verwendet werden.
• . Das doppelte Zählen wird als ein allgemeiner Grundsatz auf der Seite 126 beschrieben; der doppelte zählende Beweis des Bergmannes der Formel von Cayley ist auf Seiten 145-146.
• . Nachgedruckt und übersetzt darin.