Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Bijektiver Beweis für Binomialkoeffizient

Bijektiver Beweis für Binomialkoeffizient

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Beweis, Bijektion, bijektiv, Bijektivität, Binomialkoeffizient

jni97 aktiv_icon

14:53 Uhr, 08.11.2017

Hallo,
ich habe in einer Übung folgende Aufgabe bekommen:

Es seien

n; k; j

natürliche Zahlen, so dass

j \leq k \leq n

. Man zeige die folgende Behauptungen mit einem "bijektiven Beweis":

a)

(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})

b)

(\begin{matrix} n \\ k \end{matrix}) (\begin{matrix} k \\ j \end{matrix}) = (\begin{matrix} n \\ j \end{matrix}) (\begin{matrix} n - j \\ k - j \end{matrix})

Leider finde ich keinen Ansatz für die Aufgabe.
Soweit ich Bijektionen verstanden habe, gibt es genau ein Element aus der Definitionsmenge für die Bildmenge und jedes Element aus der Bildmenge wird getroffen. Aber wie soll ich damit einen Beweis zeigen?

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

Zu diesem Thema passende Musteraufgaben einblenden

DrBoogie aktiv_icon

15:13 Uhr, 08.11.2017

Gab's schon:
www.onlinemathe.de/forum/Bijektiver-Beweis

jni97 aktiv_icon

15:23 Uhr, 08.11.2017

Die erneute Frage tut mir leid, aber ich werde aus dem Ansatz trotzdem nicht schlau...
Ich verstehe irgendwie nicht, wie man das Beweisen soll. Also wie soll ich das aufschreiben? Soll ich mir eine bijektive Abbildung ausdenken? Wenn ja, von welcher Menge?(Es ist ja keine gegeben).
Ich bin noch ein Anfänger in dem Themengebiet...

DrBoogie aktiv_icon

15:39 Uhr, 08.11.2017

"Also wie soll ich das aufschreiben?"

Für a) - so wie ich das gemacht habe, vielleicht etwas ausführlicher.

"Soll ich mir eine bijektive Abbildung ausdenken?"

Ja, aber eine passende. Ich habe eine passende vorgeschlagen, sie sieht so aus:

A \to M \ A

. Dabei ist

M

eine

n

-elementige Menge, z.B.

{1, 2, . . ., n}

und

A

eine beliebige Teilmenge davon.

"Wenn ja, von welcher Menge?(Es ist ja keine gegeben)."

Wie gesagt, man kann

M = {1, 2, . . ., n}

nehmen und Abbildung

A \to M \ A

betrachten, wo

A

beliebig aus

P (M)

ist (Menge der Teilmengen von

M

). Also Abbildung geht von

P (M)

nach

P (M)

.

Für einen Anfänger ist es leider keine sehr einfache Aufgabe, ich weiß nicht, warum man Anfängern so was serviert.

DrBoogie aktiv_icon

15:59 Uhr, 08.11.2017

In b) ist die Geschichte etwas komplizierter.
Da kann man dieselbe Menge

M

nehmen und dann eine Abbildiung
auf

P (M) \times P (M)

definieren, also auf Paaren der Teilmengen von

M

.
Und zwar nur auf Paaren:

(A, B)

mit

A \subseteq B

.
Diese Abbildung sieht dann so aus:

(A, B) \to (A, B \ A)

.
Da

(\binom{n}{k}) (\binom{k}{j})

die Anzahl der Paare

A, B

mit

A \subset B

und

∣ A ∣ = j, ∣ B ∣ = k

ist und da

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

die Anzahl der Paare

A, B

mit

∣ A ∣ = j, ∣ B ∣ = k - j

und

A \cap B = \emptyset

, liefert die Abbildung die gewünschte Gleichung.

jni97 aktiv_icon

16:18 Uhr, 08.11.2017

Danke erstmal für die Hilfe. Das war jetzt verständlich für mich. Dann werde ich mich jetzt mal daran versuchen.

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

1396371

1396340

	Status: nicht eingeloggt	Noch nicht registriert?