Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis von Binomialidentitäten

Beweis von Binomialidentitäten

Universität / Fachhochschule

Tags: Binomialkoeffizient

Clemensum aktiv_icon

09:45 Uhr, 01.11.2011

Man
gebe kombinatorische Beweise für die folgenden Binomialidentitäten:
(a)

n \cdot (\binom{n - 1}{k - 1}) = k \cdot (\binom{n}{k})

(b)

\sum_{i = 0}^{n} i \cdot (\binom{n}{i}) = n \cdot 2^{n - 1}

Zu (a): die rechte Seite ist die Anzahl aller Möglichkeiten aus einer
n-Menge eine k-Menge auszuwählen und dort ein Element "rot" zu färben,
nennen wir dies a bei einer beliebigen Menge A.
Grund: Jede Teilmenge hat ja k-Elemente und ich habe bei jeder Teilmenge
ja die Möglichkeit ein Element zu färben und das kann ich wohl k mal
machen, also...

So, bei der rechten Seite scheint es günstig zu sein, dieses angefärbte
Element in den Teilmengen zu "suchen". Wenn ich wissen will, wo es
vorkommt, nehme ich es überall dort raus, wo es vorkommt, denn so kann
ich Methoden anwendbar machen und die Anzahl der Teilmengen verändert
sich ja dadurch offenbar nicht...
Nun, wenn ich das a aus allen Teilmengen entferne, wo es drinnen liegt, redzuziert sich die Anzahl der Elemente bei diesen Teilmengen um 1. Da es dann aber in KEINER Teilmenge mehr drinnen ist, ist es so, als würde ich von der Hauptmenge

X := 1, 2, 3 \dots, n

ein Element nehmen und erhalte so alle Teilmengen von

X \ {a}

. Also ergibt dies

(\binom{n - 1}{k - 1})

.

Mein Problem ist jedoch, dass ich kombinatorisch nicht einsehe, wie man auf das

n

auf der linken Seite kommen soll. Ich habe ein beliebiges, aber festes angemaltes Element betrachtet und es abgezählt. Warum sollte die Anzahl

n

mal so hoch sein, wie mein Resultat?

Kann mir dabei jemand helfen?

Zu b)
Folgt sofort aus (a), wenn man die rechte Seite von (a) aufsummiert; es ist klar, dass daraus die Potenzmengenmächtigkeit resultiert...

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

prodomo aktiv_icon

09:56 Uhr, 01.11.2011

Der Beweis mit der Auflösung in Fakultäten ist relativ einfach. Was ist mit "kombinatorischer Beweis" gemeint ?

n \cdot (\begin{matrix} n - 1 \\ k - 1 \end{matrix}) = n \cdot \frac{(n - 1)!}{(k - 1)! \cdot (n - k)!} = \frac{n!}{(k - 1)! \cdot (n - k)!} = k \cdot \frac{n!}{k! \cdot (n - k)!}

Clemensum aktiv_icon

10:02 Uhr, 01.11.2011

Moin!

Danke dir erstmal für deine Schnelle reaktion! :-)

Jedoch ist mit kombinatorischen Beweis natürlich nicht das elementare Einsetzen in die Definition gemeint, das wäre mir leicht gelungen. Es ist das geeignete Betrachten der dahintersteckennde Teilmengeninterpretation gemeint. Zuerst male ich rechts ein beliebiges, aber festes element a an und danach ändere ich die Sichtweise und suche dann das Element, wobei ich zur linken Seiten kommen sollte. Jedoch verstehe ich - rein im Sinne der Kombinatorik - nicht, wie man auf das

\cdot n

kommt.

Hast du hier eine Idee?

teppich aktiv_icon

14:27 Uhr, 01.11.2011

Bei kombinatorischen Beweisen geht es im wesentlichen darum, den Anzahlformeln eine kombinatorische Bedeutung zu verleihen und anschließend eine "Bijektion" zwischen diesen kombinatorischen Modellen zu finden.

Clemensum, Deine Idee, die Objekte auf der rechten (und somit auch auf der linken) Seite als

k

-elementige Teilmengen von

{1, 2, \dots, n}

mit einem gefärbten Element zu interpretieren ist ein sehr guter Ansatz. Konstruierst Du nun ein solches Objekt, kann dies auf folgende Arten geschehen:

(i) auf der rechten Seite wählst Du erst

k

Elemente aus und färbst dann
(ii) auf der linken Seite färbst Du erst eines der

n

Elemente und ergänzt dann

k - 1

von den verbliebenen

n - 1

Eine Übersetzung der Konstuktionen in Anzahlformeln ergibt die zu beweisende Gleichheit.

Clemensum aktiv_icon

18:39 Uhr, 01.11.2011

Gut, danke dir, das dürfte nun klar sein!

Wirklich Probleme jedoch habe ich bei folgendem (kombinatorischen) Beispiel:

(\binom{n + 1}{k + 1}) = \sum_{m = k}^{n} (\binom{m}{k})

Mit Induktion habe ich es zusammengebracht. Aber, ich soll ja einen rein kombinatorischen Beweis erbringen...
Es scheint für mich jedoch mit der Summierung der Mächtigkeiten der Teilmengen in der Potenzmenge zu tun zu haben, also kann ich es lediglich auf

< 2^{n}

abschätzen.

Die Anfärbungen gelingen hier offenbar nicht mehr.

Ein Ansatz fällt mir jedoch ein: Man könnte die linke Seite der zu beweisenden Identität durch sukzessive Summenbildung a la

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

geeignet oft abspalten.
Jedoch ist dieses Vorgehen ziemlich mühsam und kommt nur schwer zum Ziel.

Fällt euch ein besseres Verfahren ein?

teppich aktiv_icon

20:04 Uhr, 01.11.2011

Eine Interpretation der linken Seite sollte kein Problem sein. Auf der rechten Seite hat jeder Summand seine eigene Interpretation. In der Kombinatorik entspricht das + einem "oder"

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

933499

933112

	Status: nicht eingeloggt	Noch nicht registriert?