Beweise mit kombinatorischer Begründung: Term mit Binomialkoeffizienten und Summe

Question

Gesucht ist eine kombinatorische Begründung für den folgenden Ausdruck:

$$\sum \limits_{k=1}^{n}k^{2}\binom{n}{k}=n(n+1)2^{n-2}$$

mit k, n aus N.

Bekannt ist a) (das konnte ich kombinatorisch begründen):

$$\sum \limits_{k=1}^{n}k\binom{n}{k}=n2^{n-1}$$

Und man soll die Identität:

$$n(n+1)2^{n-2} = n(n-1)2^{n-2} + n2^{n-1}$$

nutzen.

Mir fehlt eine zündende Idee, wie man ansetzen könnte. Der Hinweis deutet auf Nutzung der Formel unter a) hin, aber wie?

Irgendwelche Ideen?

Lg

J.

Comments

Das Anwenden von Formeln und Identitäten widerspricht aber der Aufgabe, die Gleichung kombinatorisch zu begründen.

---

Darin sehe ich keinen Widerspruch.

Es läuft doch darauf hinaus zu begründen, dass \(\sum \limits_{k=1}^{n}k^{2}\binom{n}{k}=n(n-1)2^{n-2} + n2^{n-1}\) bzw. dass \(\sum \limits_{k=1}^{n}k^{2}\binom{n}{k} - \sum \limits_{k=1}^{n}k\binom{n}{k}=n(n-1)2^{n-2} \) also dass \(\sum \limits_{k=1}^{n}\binom k2\binom{n}{k} =\binom n2 2^{n-2} \) ist. Und das kann man analog zu meinem Beitrag hier kombinatorisch über Eisbecher mit zwei Früchten erledigen.

---

Ah, das hilft weiter! Vielen Dank an hj2166!

Answer 1

Man kann dies auch zu einer kombinatorischen Begründung "zusammenfassen". Es sei \(N:=\{1, \ldots,n\}\).´. Dann lautet die kombinatorische Aufgabe: Wie viele Paare \(((x,y),A)\) mit \(A \sub N\) und einem Paar \((x,y)\) aus A gibt es? Das kann man auf 2 Wegen beantworten:

1. Wähle für \(k=1, \ldots,n\) eine k-elementige Menge A und daraus ein Paar.

2. Wähle zunächst das Paar und ergänze aus dem Rest zur Menge A. Dabei braucht es eine Fallunterscheidung:

2a. Das Paar besteht aus 2 verschiedenen Elementen aus N, es stehen dann noch n-2 Elemente aus N zur Ergänzung zur Verfügung

2b. Das Paar hat die Form (x,x), es stehen dann n-1 Elemente aus N zur Verfügung.

Insgesamt für 2: \(n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}\)

Comments

Vielen Dank! Als jemand, der sich mit Mathe etwas auskennt aber nicht mit Kombinatorik speziell, kommt mir das schon recht anspruchsvoll vor .

Der Fall 2b) müßte also gleichzeitig auch der kombinatorische Beweis für die Aussage a) aus meiner Ursprungsfrage sein, die hj2166 mit seinem Fruchtbecher gelöst hat (was ich aber noch nicht ganz durchdrungen habe ).

---

Genau, 2b entspricht Deiner Aussage a bzw der Überlegung von hj2166