Kombinatorischer Beweis - Bedeutung?

11.11.2014, 23:00

Matheneuling1991

Kombinatorischer Beweis - Bedeutung?

Hallo zusammen,

ich soll kombinatorisch beweisen, dass:

$\begin{eqnarray*} \sum\limits_{k=1}^n k \begin{pmatrix} n \\ k \end{pmatrix}=n*2^{n-1} \end{eqnarray*}$

Erst einmal, was heißt es, etwas "kombinatorisch" zu beweisen? Und hat vielleicht jemand einen Ansatz? smile

12.11.2014, 09:38

HAL 9000

Auf diesen Beitrag antworten »

Durch "inhaltliche" Überlegungen, wie man die Summe links - und auch den Ausdruck rechts - kombinatorisch deuten könnte. In dem Zusammenhang spielt oft (so auch hier) das Prinzip des Doppelten Abzählens eine wichtige Rolle.

Um mal hier einen Start zu geben: Wir betrachten eine $\begin{align*} n \end{align*}$ -elementige Grundmenge, dann ist $\begin{align*} \binom{n}{k} \end{align*}$ die Anzahl derjenigen Teilmengen dieser Menge, die genau $\begin{align*} k \end{align*}$ Elemente umfassen. Jetzt richte mal den Fokus auf die einzelnen Elemente dieser Teilmengen...

12.11.2014, 10:47

Matheneuling1991

Auf diesen Beitrag antworten »

RE: Kombinatorischer Beweis - Bedeutung?
Okay, das heißt praktisch kein rechnerischer Beweis, Induktion etc.

Ich weiß, dass

$\begin{eqnarray*} \sum\limits_{k=1}^n \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

die Menge ALLER Teilmengen einer n-Elementigen Menge ist(außer einer TM, nämlich die, dass kein Element in der Teilmenge ist, da die Summe ja erst bei 1 startet)

Dies muss

$\begin{eqnarray*} 2^n-1 \end{eqnarray*}$

ergeben, da ich ja auch bei jedem Element direkt fragen kann, ob es, ob es in der Teilmenge enthalten ist; Für jedes Element gibt es 2 Möglichkeiten: Enthalten und Nicht Enthalten;

Also gibt es

$\begin{eqnarray*} 2*2*2*2...=2^n \end{eqnarray*}$

Teilmengen und die 1 muss ich abziehen, weil ja eine Teilmenge fehlt..

In meinem Beispiel werden die k-elementigen TM mit k multipliziert, d.h. die TM mit einem Element werden mit 1 multipliziert, die TM mit 2 Elementen mit 2 usw.
Wie ich das dann handhabe weiß ich leider nicht.. unglücklich

Hilft mir der oben genannte Ansatz und kann ich den modifizieren, um auf die Lösung zu kommen oder funktioniert der Weg so nicht?

12.11.2014, 10:54

HAL 9000

Auf diesen Beitrag antworten »

Es geht nicht so sehr um die Anzahl $\begin{align*} 2^n-1 \end{align*}$ aller nichtleeren Teilmengen, sondern um die Summe der Mächtigkeiten dieser Teilmengen:

$\begin{align*} \sum_{M\subseteq \{1,\ldots,n\}} |M| \end{align*}$

Versuche mal diese Summe im obigen Sinne "doppelt" abzuzählen: Einmal unter dem Gesichtspunkt der Teilmengenmächtigkeit $\begin{align*} |M|=k \end{align*}$ , und das andere mal bezogen auf die Einzelelemente $\begin{align*} x\in\{1,\ldots,n\} \end{align*}$ .

13.11.2014, 02:22

Matheneuling1991

Auf diesen Beitrag antworten »

Hey...

Danke nochmals für deine Antwort und sorry für die etwas spätere Antwort..
Und ein drittes Mal sorry, aber ich komme immer noch nicht weiter, weil ich die Summe nur auf eine Weise abzählen kann, nämlich so, wie auf der linken Seite..
Vielleicht kannst du mir nochmals einen Denkanstoß geben? Aber am besten einen Starken, weil ich habe das Gefühl, dass ich wirklich richtig auf dem Schlach stehe Big Laugh

Danke!

13.11.2014, 08:41

HAL 9000

Auf diesen Beitrag antworten »

OK, ein allerletzter Versuch, es verständlich zu machen - mit kompletter Lösung, was anderes bleibt ja anscheinend nicht mehr übrig: Für $\begin{align*} \Omega=\{1,2,\ldots,n\} \end{align*}$ betrachten wir die Menge der geordneten Paare

$\begin{align*} A := \left\{ (M,x) \bigm| M\subseteq \Omega,\, x\in M \right\} \end{align*}$

und versuchen, dieses $\begin{align*} A \end{align*}$ "doppelt" abzuzählen:

a) Über konstante $\begin{align*} M \end{align*}$ :

$\begin{align*} |A| = \sum_{M\subseteq \Omega} \left| \left\{ x \bigm| x\in M \right\} \right| = \sum_{M\subseteq \Omega} |M| = \sum_{k=0}^n \sum_{\substack{M\subseteq \Omega\\|M|=k}} |M| = \sum_{k=0}^n k\binom{n}{k} \end{align*}$

b) Über konstante $\begin{align*} x \end{align*}$ :

$\begin{align*} |A| = \sum_{x=1}^n \left| \left\{ M \bigm| M\subseteq \Omega\;\mbox{mit}\;x\in M \right\} \right| = \sum_{x=1}^n 2^{n-1} = n2^{n-1} \end{align*}$

Der Summand ist hier jeweils $\begin{align*} 2^{n-1} \end{align*}$ , weil die Anzahl der Teilmengen von $\begin{align*} \{1,2,\ldots,n\} \end{align*}$ , die zwingend $\begin{align*} x \end{align*}$ enthalten, gleich der Anzahl aller Teilmengen der $\begin{align*} (n-1) \end{align*}$ -elementigen Menge $\begin{align*} \{1,2,\ldots,n\}\setminus\{x\} \end{align*}$ ist.

13.11.2014, 23:24

Matheneuling1991

Auf diesen Beitrag antworten »

Vielen Dank!! smile

Ich weiß es wirklich zu schätzen, dass du dir die Mühe gemacht hast, danke!
Habe es jetzt, nach 2 mal durchlesen auch vollständig verstanden.. Allerdings wäre ich selbst so schnell nicht drauf gekommen, drum nochmals danke
Freude

14.11.2014, 07:37

HAL 9000

Auf diesen Beitrag antworten »

Da zitiere ich mal aus dem oben verlinkten Wikipedia-Artikel:

Zitat:

Solche Beweise sind häufig sehr kurz und leicht zu verstehen, da oft keinerlei komplexe mathematische Werkzeuge notwendig sind. Dagegen erfordert es aber oft viel Kreativität, um sie zu finden.

Neue Frage »

Antworten »

Kombinatorischer Beweis - Bedeutung?

Verwandte Themen