Kombinatorischer Beweis von ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n

Unter Verwendung der folgenden Gleichung:

∑ k = 0 N ( N k ) 3 k = 4 N

Ich muss beweisen, dass beide Seiten der Gleichung dasselbe kombinatorische Problem lösen.

Es ist leicht zu erkennen, dass die rechte Seite der Gleichung die Anzahl der Teilungsmöglichkeiten zählt N verschiedene Bälle hinein 4 Eimer.

Ist es richtig zu sagen, dass die linke Seite der Gleichung dasselbe Problem auf folgende Weise löst (?):

Seit ∑ k = 0 N ( N k ) 3 k = ∑ k = 0 N ( N N − k ) 3 k , können wir die Gleichung ändern zu:

∑ k = 0 N ( N N − k ) 3 k = 4 N

Und aus der neuen Gleichung ist es einfacher zu erkennen, dass jeder Binomialkoeffizient die Anzahl der Kugeln auswählt, die in den ersten Eimer gelegt werden sollen, und 3 k teilt den Rest k Bälle zwischen den restlichen 3 Eimern ohne Begrenzung.

Ich nehme an, du willst das nicht: ∑ k = 1 N ( N k ) 3 k = ∑ k = 1 N ( N k ) 1 N − k 3 k = ( 1 + 3 ) N = 4 N ...
Danke @lhf, aber nein, ich suche nur nach einer kombinatorischen Erklärung.
@MichaelS: Dein kombinatorisches Argument ist einfach und richtig.
Ist das Ergebnis, das MichaelS zu beweisen versucht, richtig? Ich verstehe das, wenn N = 1 , Dann ∑ k = 1 1 ( 1 k ) 3 k = ( 1 1 ) 3 1 = 3 = 4 1 = 4 ? Das sagt der Binomialsatz 4 N = ( 3 + 1 ) N = ∑ k = 0 N ( N k ) 3 k 1 N − k = ∑ k = 0 N ( N k ) 3 k Dies ist ein etwas anderes Ergebnis (beachten Sie den unterschiedlichen Summierungsbereich).
@ChristianBlatter, danke! Freut mich zu sehen, dass ich es richtig gemacht habe..
@DilipSarwate, ich habe k=1 anstelle von k=0 geschrieben, ich werde es sofort beheben.
Alles ist gut. Ich für mich ziehe es vor, die Wörter der Länge zu zählen N über dem Alphabet { 1 , 2 , 3 , 4 } . Gleiche Analyse.

Antworten (2)

Ja, ich stimme Ihrer Interpretation der linken Seite zu, und auch der Kommentar von lhf kann so gesehen werden:

  1. 4 N die Wege der Teilung N Bälle rein 4 Boxen
  2. ( 3 + 1 ) N das gleiche wie oben
  3. ∑ k = 0 N ( N k ) 1 N − k 3 k für jeden k , die Möglichkeiten zu wählen k Bälle unter den N Bälle hast du, mal die Wege zu legen N − k Bälle in eine Kiste, mal die Möglichkeiten den Rest zu legen k Kugeln im Rest 3 Boxen
  4. ∑ k = 0 N ( N k ) 3 k wie oben, mit 1 N − k = 1
Danke! Freut mich zu sehen, dass ich es richtig gemacht habe :)
Das Ergebnis, das Sie zu beweisen versuchen, ist nicht korrekt und die Interpretation, die Sie geben, ist fehlerhaft.
Emanuele, ich habe in die Frage k=1 statt k=0 geschrieben, bitte bearbeite deine Antwort, damit der Beweis nicht falsch ist. Ich habe die Frage bereits auf k = 0 bearbeitet.
Verzeihung. Ich habe nur die Identität von lhf kopiert, weil ich zu faul war, diese Tippfehler nicht bemerkt zu haben. Ich nehme an, @Dilip hat sich darauf bezogen.

Die RHS sieht aus wie die Formel für die Anzahl der Basis-4-Saiten. Wir können also auch die LHS ähnlich wie die Kugelzählung als Zählung aller möglichen Basis-3-Saiten interpretieren, die in die gelegt werden können N Länge-String und füllt den Rest mit der verbleibenden Ziffer.

Zum Beispiel

X X X 012201 X X 021 X X
Wo ( N k ) wählt wo 0 , 1 , 2 geh und 3 k zählt jede mögliche Zeichenfolge.

Sie sollten bei der Angabe von Buckets vorsichtig sein, da sie unterschiedlich sind , was aus der Reihenfolge einer Zeichenfolge hervorgeht.

Kombinatorischer Beweis von ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n
AntwortenHierDatenschutz-Bestimmungen1y, 0v