Kombinatorischer Beweis (Binomialkoeffizient)

13.11.2009, 16:05

Divison by Zero

Kombinatorischer Beweis (Binomialkoeffizient)

Hallo, ich benötige dringend Hilfe für folgende Gleichung. Ich soll mittels kombinatorischer Beweisführung zeigen, dass für alle $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gilt:
$\begin{eqnarray*} \sum_{k=1}^n~k \begin{pmatrix} n \\ k \end{pmatrix} = n \cdot 2^{n - 1} \end{eqnarray*}$
Problem ist, dass ich durch mangelnde Erklärungen und Desinteresse seitens des Lehrpersonals (gut ausgedrückt, wa?) keinen blassen Schimmer habe wie ich damit jetzt vorgehen soll. Ein Ansatz, wenn irgend möglich eine komplette Lösung, wären hilfreich.

Des weiteren muss ich das selbe nochmal für diese Gleichung zeigen:
$\begin{eqnarray*} \sum_{k=1}^n~k \begin{pmatrix} n \\ k \end{pmatrix}^2 = n \cdot \begin{pmatrix} 2n - 1 \\ n - 1 \end{pmatrix} \end{eqnarray*}$
Ich sag mal, wenn ich mir aus der ersten Gleichung ein verständliches Beispiel ziehen kann, sollte ich die auch hinbekommen. Aber ich verzweifle leider echt daran.

Bin äußerst dankbar für jede Hilfe!!

13.11.2009, 17:00

Auf diesen Beitrag antworten »

Zu 1.:

Hier hilft das Prinzip des doppelten Abzählens, angewandt auf alle Elemente aller Teilmengen einer Menge mit $\begin{eqnarray*} n \end{eqnarray*}$ Elementen.

EDIT: Sch... Tippfehler.

13.11.2009, 17:18

Mystic

Auf diesen Beitrag antworten »

Ebenfalls zu 1.

Hier hilft auch die Potenzregel fürs Differenzieren, falls du damit mehr anfangen kannst... Natürlich muss dazu vorher eine Vartiable x her Wink

13.11.2009, 17:22

Auf diesen Beitrag antworten »

@Mystic

Hier wurde ausdrücklich nach einem kombinatorischen Beweis gefragt. Ich habe meine Zweifel, dass dein Vorschlag da reinpasst. verwirrt

Für einen nicht rein kombinatorischen Beweis würde ich übrigens den Weg über

$\begin{eqnarray*} k \cdot \binom{n}{k} = n \cdot \binom{n-1}{k-1} \end{eqnarray*}$

vorschlagen.

14.11.2009, 14:54

DivisionByZero

Auf diesen Beitrag antworten »

RE: Kombinatorischer Beweis (Binomialkoeffizient)
Ich verstehe das Prinzip des doppelten abzählens nicht so ganz, die englische Wiki Seite hilft mir auch nicht. Wir haben zwar ein kleines Bsp in der Vorlesung gehabt, aber damit komme ich nicht weiter.
Könnt ihr das nicht ahand von erstens mir mal zeigen, damit ich das Prinzip nachvollziehen und auf zweitens anwenden kann?
Danke schon mal.

16.11.2009, 09:13

DivisionByZero

Auf diesen Beitrag antworten »

RE: Kombinatorischer Beweis (Binomialkoeffizient)
Bitte, ich muss das morgen abgeben und habe keine Ahnung vom doppelten Abzählen...
Helft mir doch unglücklich

16.11.2009, 09:23

Auf diesen Beitrag antworten »

Lesen!!!

Zitat:

Original von Arthur Dent
Hier hilft das Prinzip des doppelten Abzählens, angewandt auf alle Elemente aller Teilmengen einer Menge mit $\begin{eqnarray*} n \end{eqnarray*}$ Elementen.

Bezogen auf die Teilmengengröße erhält man dann auf der einen Seite (hier links):

Es gibt $\begin{eqnarray*} \binom{n}{k} \end{eqnarray*}$ Teilmengen der Größe $\begin{eqnarray*} k \end{eqnarray*}$ , in denen befinden sich also insgesamt $\begin{eqnarray*} k\cdot \binom{n}{k} \end{eqnarray*}$ Elemente, d.h. man unterscheidet bei dieser Betrachtung an sich gleiche Elemente der Grundmenge, indem man etwa als Index die Teilmengennummer anhängt o.ä. Das ganze macht man jetzt für alle Teilmengen, d.h., man summiert über alle möglichen Teilmengengrößen $\begin{eqnarray*} k=0,\ldots,n \end{eqnarray*}$ , wobei man aber den Term für $\begin{eqnarray*} k=0 \end{eqnarray*}$ wegen $\begin{eqnarray*} 0\cdot \binom{n}{0} = 0\cdot 1 = 0 \end{eqnarray*}$ auch gleich weglassen kann.

Andererseits kann man aber auch ein Element der Grundmenge festhalten und sich fragen, in wie vielen Teilmengen genau dieses Element enthalten ist. So kommt man dann auf den Ausdruck auf der rechten Seite.

Zitat:

Original von DivisionByZero
Könnt ihr das nicht ahand von erstens mir mal zeigen, damit ich das Prinzip nachvollziehen und auf zweitens anwenden kann?

Das geht wie so oft in der Kombinatorik nicht automatisch und bequem per Rezept. Man muss sich schon wirklich in das Beispiel vertiefen, um eine geeignete Menge zu finden, deren Abzählung das gewünschte Ergebnis bringt. Diese geeignete Menge hatte ich dir im ersten Fall sogar bereits genannt - trotzdem hast du keinen Finger gerührt.

16.11.2009, 21:56

brainless

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Andererseits kann man aber auch ein Element der Grundmenge festhalten und sich fragen, in wie vielen Teilmengen genau dieses Element enthalten ist. So kommt man dann auf den Ausdruck auf der rechten Seite.

ein Element aus der Grundmenge kann in einer Teilmenge sein und kommt dann n-Mal vor, da ja von k=0 bis k=n aufsummiert wird..
aber wie kommt man auf den rechten Teil.. (warum hoch n-1)
habe jetzt ca. 2 Stunden nachgedacht und komm nicht weiter Erstaunt2

17.11.2009, 19:31

Auf diesen Beitrag antworten »

Zitat:

Original von brainless
ein Element aus der Grundmenge kann in einer Teilmenge sein und kommt dann n-Mal vor, da ja von k=0 bis k=n aufsummiert wird..

Keine Ahnung, was du damit sagen willst. Nein, es geht so:

Du nimmst die Grundmenge abzüglich des fraglichen Elementes, und bildest von dieser $\begin{eqnarray*} n-1 \end{eqnarray*}$ Elemente umfassenden Menge alle Teilmengen - das sind genau $\begin{eqnarray*} 2^{n-1} \end{eqnarray*}$ Stück. Wenn du jetzt zu jeder dieser Teilmengen das fragliche Element wieder hinzufügst, dann hast du genau die Teilmengen der Ausgangsmenge, die dieses Element enthalten.

Neue Frage »

Antworten »

Kombinatorischer Beweis (Binomialkoeffizient)

Verwandte Themen