0 Daumen
369 Aufrufe

Aufgabe:

blob.png

Text erkannt:

3.4 Für die Summe
\( \sum \limits_{k \geq 0} k\binom{n}{k}^{2} \)
bestimme man eine explizite Formel, die ohne Summenzeichen \( \sum \) bzw. . . . auskommt.



Problem/Ansatz: ich denke hier kannn man was mit Vandermonde oder etwas ähnliches benutzen, aber ich komm nicht drauf :(

Avatar von

Hinweis: berechne die ersten paar Summen und dividiere durch die Zweierpotenz \(2^{n-1}\)

Oh - ich hatte das Qudarat übersehen. Mein vorheriger Kommentar gilt nur für \(\sum\limits_{k\ge0} k {n \choose k}\)

2 Antworten

+2 Daumen

Hier ist ein kombinatorischer Weg, der ausnutzt, dass gilt:$$\binom nk = \binom n{n-k}$$

Dann sieht die Summe also so aus (Beachte: \(k=0\) kann man weglassen): $$\sum_{k=1}^nk\binom nk\binom n{n-k}$$

Wir bilden jetzt die Anzahl der Komitees bestehend aus n Personen, die aus n Führungspersonen (F) und n Angestellten (A) gewählt werden können. Dabei muss eine der Führungspersonen Vorsitzender des Komitees sein.

Zählung 1:
Wähle \(k=1\ldots n \) aus F und davon den Vorsitzenden: \(k\binom nk\)

Wähle die restlichen \(n-k\) aus A: \(\binom n{n-k}\)

Insgesamt: \(\displaystyle \sum_{k=1}^nk\binom nk\binom n{n-k}\)


Zählung 2:

Wähle zunächst einen Vorsitzenden aus F: \(n\)

Wähle aus den restlichen \(2n-1\) die weiteren \(n-1\) Personen: \(\binom {2n-1}{n-1}\)

Insgesamt: \(n\binom {2n-1}{n-1}\)


Zusammen: $$\sum_{k=1}^nk\binom nk\binom n{n-k} =n\binom {2n-1}{n-1} $$


2. Weg mit Koeffizientenvergleich:

$$(1+x)^n = \sum_{i=0}^n\binom ni x^i \Rightarrow nx(1+x)^{n-1}= \sum_{i=0}^ni\binom ni x^i$$

Multipliziere die beiden Reihen:
$$nx(1+x)^{2n-1} = \sum_{k=0}^{2n}\left(\sum_{i=0}^k i\binom ni\binom n{k-i}\right)x^k = ...$$ $$ ...= n\sum_{k=1}^{2n}\binom{2n-1}{k-1}x^k$$

Koeffizientenvergleich für \(k=n\) gibt:

$$\sum_{i=0}^n i\binom ni\binom n{n-i} = n\binom{2n-1}{n-1}$$

Fertig.

Avatar von 11 k

Tausend Dank!

+1 Daumen

Aloha :)

Hier brauchst du gar nicht viel zu rechnen:$$S(n)=\sum\limits_{k\ge0}k\binom{n}{k}^2=\sum\limits_{k=1}^{n}k\cdot\frac nk\binom{n-1}{k-1}\cdot\binom{n}{k}=n\cdot\sum\limits_{k=1}^{n}\binom{n-1}{n-k}\cdot\binom{n}{k}$$

Der Wert der Summe ist nach kurzem Hinsehen klar. Stelle dir dazu eine Menge \(M\) mit \((2n-1)\) Elementen vor. Diese Menge teilst du in zwei Mengen auf. Die erste Menge \(M_1\) hat \((n-1)\) Elemente und die Menge \(M_2\) hat \(n\) Elemente. Jetzt spiele mal die Summation im Kopf durch:

\(k=1:\;\) Aus \(M_1\) wählst du \((n-1)\) Elemente und aus \(M_2\) wählst du \(1\) Element.

\(k=2:\;\) Aus \(M_1\) wählst du \((n-2)\) Elemente und aus \(M_2\) wählst du \(2\) Elemente.

\(k=3:\;\) Aus \(M_1\) wählst du \((n-3)\) Elemente und aus \(M_2\) wählst du \(3\) Elemente.

Das geht so weiter bis \(k=n\).

Wenn du diese Fälle addierst, bekommst du die Anzahl der Möglichkeiten, aus \((2n-1)\) Elementen genau \(n\) auszuwählen. Daher ist:$$S(n)=n\binom{2n-1}{n}=\frac{2n^2}{2n}\binom{2n-1}{2n-1-n}=\frac n2\cdot\frac{2n}{n}\binom{2n-1}{n-1}=\frac n2\binom{2n}{n}$$

Avatar von 152 k 🚀

Ich sehe jetzt 2 verschiedene Lösungen??

Habe falsch geguckt.

Aber immerhin hast du nur 14 Minuten gebraucht, um richtig zu gucken ;)

Weil ich noch mit einem anderen Problem beschäftigt war: Bei Deinem zweiten Gleichheitszeichen sieht es so aus, als sei

$${n \choose k}=\frac{n}{k}{ n-1 \choose k}$$

Ja, da hänge ich auch gerade...woher kommt das? und wie kommst du auf die Umformungen in der letzten Reihe?

Naja, wenn ich das mal für k=1 auswerten ....

Ich habe die erste Zeile nochmal umgeschrieben.

In der letzten Zeile habe ich folgende Rechenregeln benutzt:$$\binom{n}{k}=\frac nk\cdot\binom{n-1}{k-1}\quad\text{und}\quad\binom{n}{k}=\binom{n}{n-k}$$

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community