Doppeltes Abzählen, Summenzeichen

Question

Aufgabe:

Beweisen Sie \( \sum\limits_{k=0}^{n}{k*\binom{n}{k}} \)  = n2^n-1  indem Sie die Anzahl Möglichkeiten aus n Schülern einer Klasse (beliebliger Größe k) zusammenzustellen und daraus einen Klassensprecher auszuwählen, doppelt abzählen.

Mein Ansatz:

1.Abzählung:

Wenn man aus n Schülern eine beliebige Klasse k auswählen will, hat man (n über k) Möglichkeiten.

Um aus dieser Klasse mit beliebiger Größe k einen Klassensprecher auszuwählen gibt es k Möglichkeiten.

Nach der Produktregel folgt k*(n über k).

Wäre das so richtig, weil ich mir nicht sicher bin wie ich das summenzeichen hier noch hinzufügen soll.

2.Abzählung

Hier würde ich jetzt zuerst aus n Schülern einen Klassensprecher auswählen, das wären dann ja n Möglichkeiten. Aber ich bin mir unsicher wie man jetzt auf die 2^n-1 kommt ?

Answer 1

Die Summe über k kommt zustande, weil Du eine Teilmenge der Schüler auswählen sollst, aber die Anzahl in der Teilmenge nicht festgelegt ist. D.h. Du kannst eine Teilmenge mit 1 oder 2 oder 3 oder ... oder n Schülern wählen - und daraus einen Sprecher. Achtung k=0 wird formal mitgenommen, indem der Faktor k hier 0 beiträgt.

Was die rechte Seite angeht: Du wählst einen Sprecher und ergänzt diesen zu einer Teilmenge der Gesamtmenge der Schüler. Da der Sprecher zu dieser Teilmenge gehören muss, hast Du noch n-1 Schüler zur Ergänzung zur Verfügung. Die Anzahl an Teilmengen einer Menge mit n-1 Elementen ist 2^(n-1)

Ein wenig formal: Du hast die Menge der Schüler. Du zählst Paare (x,A) ab, wobei \(x \in A \sube S\) ist. Die rechte Seite zählt die Paar in der Form

$$(x,B \cup\{x\}) \text{  mit } B \sube S \setminus \{x\}$$

Und die linke Seite

$$\bigcup_{k=1}^n\{(x,A)\mid A \subset S, |A|=k,x \in A\}$$