bestimme man eine explizite Formel, die ohne Summenzeichen Σ bzw .

Question

Aufgabe:

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 :(

Comments

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}$

Answer 1

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.

Comments

Tausend Dank!

Answer 2

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}$$

Comments

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}$$