Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Anzahl der k-elementigen Teilmengen

Anzahl der k-elementigen Teilmengen

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Binomialkoeffizient

MathsTom aktiv_icon

21:03 Uhr, 31.03.2014

Hallo,
ich möchte zeigen, dass die Anzhal der k-elementigen Teilmengen einer n-Elementigen Menge stets

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

ist.
Das ganze mache ich mit Induktion: Es muss natürlich

0 \leq k \leq n

sein.
IA:

n = 1,

dann ist

k = 0,1

.
Für

k = 0

erhält man die leere Menge,

(\begin{matrix} 1 \\ 0 \end{matrix}) = 1

.
Für

k = 1

erhält man das einzige Element in der Menge,

(\begin{matrix} 1 \\ 1 \end{matrix}) = 1

.

IV: Für ein

n \in ℕ

gilt: Eine n-elementige Menge hat

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

k-elementige Teilmengen,

0 \leq k \leq n

.

IS: Wie geht man hier vor?
Zudem habe ich zwei kleinere Fragen: Wenn ich mit

n = 0

beginne, habe ich

(\begin{matrix} 0 \\ 0 \end{matrix}) = \frac{0}{0}! = 0

. Aber es gibt doch eine 0-elementige Teilmenge, die leere Menge.

Ich danke euch :-)
Tom

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

DrBoogie aktiv_icon

21:06 Uhr, 31.03.2014

Es gibt eine Vereinbarung, dass 0!=1. Dementsprechend ist

(\binom{0}{0}) = 1

.
Siehe de.wikipedia.org/wiki/Fakult%C3%A4t_(Mathematik)

MathsTom aktiv_icon

21:09 Uhr, 31.03.2014

Schon klar, aber

\frac{0}{1}

ist ja immernoch 0. Setzt mal in der Formel für

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

für

n

und

k 0

ein. Ich komme da auf

\frac{0}{1}

. Vielleicht stelle ich mich aber auch doof an :-P)

DrBoogie aktiv_icon

21:18 Uhr, 31.03.2014

Nein, es gilt

(\binom{0}{0}) = \frac{0!}{0! \cdot 0!} = 1

MathsTom aktiv_icon

21:21 Uhr, 31.03.2014

Laut der Definition ja, aber es ist ja auch

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

und bei mir kommt das damit nicht hin...

Shipwater aktiv_icon

23:55 Uhr, 31.03.2014

Pünktchenschreibweise verwirrt, schreibe

(\begin{matrix} n \\ k \end{matrix}) = \prod_{j = 1}^{k} \frac{n + 1 - j}{j}

dann folgt

(\begin{matrix} 0 \\ 0 \end{matrix}) = \prod_{j = 1}^{0} \frac{1 - j}{j}

und jetzt erkennst du auch, dass da 1 herauskommt, siehe leeres Produkt: de.wikipedia.org/wiki/Leeres_Produkt

k = 1

führt also dazu, dass im Zähler nur

n

stehen bleibt, aber bei

k = 0

hast du ein leeres Produkt, also einfach

1,

das hast du verwechselt.
Zur eigentlichen Aufgabe: Schreibe im Induktionsschritt die Menge als

{a_{1}, ..., a_{n + 1}}

und zähle dann einmal die Teilmengen die

a_{n + 1}

enthalten und dann noch die, die

a_{n + 1}

nicht enthalten.

MathsTom aktiv_icon

09:45 Uhr, 01.04.2014

Okay, also habe ich

M = {a_{1}, ..., a_{n + 1}}

.
Es gibt nach IV

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

k-elementige Teilmengen von

M,

die

a_{n + 1}

nicht enthalten.
Man kann aber auch eine

k - 1

elementige Menge aus

{a_{1}, ..., a_{n}}

auswählen und dann

a_{n + 1}

dazulegen. Dafür gibt es nach IV

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

Möglickeiten.

Somit gibt es

(\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k - 1 \end{matrix})

Möglichkeiten, aus einer n+1-elementige Menge eine k-elementige Teilmenge auszuwählen. Hier ist

0 \leq k \leq n

. Bleibt der Fall

K = n + 1

. Hier gibt es aber nur eine Möglichkeit und das passt zu

(\begin{matrix} n + 1 \\ n + 1 \end{matrix}) = 1

.

Das reicht? ;-) Man sollte die Summe vielleicht nochmal ausrechnen:

(\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k - 1 \end{matrix}) = \prod_{i = 1}^{k} \frac{n + 1 - i}{i} + \prod_{j = 1}^{k - 1} \frac{n + 1 - j}{j} = \prod_{i = 1}^{k - 1} \frac{n + 1 - i}{i} \cdot \frac{n + 1 - k}{k} + \prod_{j = 1}^{k - 1} \frac{n + 1 - j}{j} = \prod_{i = 1}^{k - 1} \frac{n + 1 - i}{i} \cdot (\frac{n + 1}{k})

Shipwater aktiv_icon

11:27 Uhr, 01.04.2014

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

kann man leicht nachrechnen. Das sollte eigentlich bekannt sein, Pascalsches Dreieck und so.

MathsTom aktiv_icon

12:05 Uhr, 01.04.2014

Aber wie komme ich da mit meiner GLeichungskette von oben drauf?

Shipwater aktiv_icon

15:21 Uhr, 01.04.2014

Rechne mit

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

das macht es angenehmer.

MathsTom aktiv_icon

16:08 Uhr, 01.04.2014

Ok, ja das ist wirklich einfacher ;-)
Ob ich noch was loswerden darf?

V

sei VR endlicher Dimension, ungleich 0. Zwei Basen

B_{1}, B_{2}

sind gleich orientiert, wenn der Endomorphismus

f_{1,2} : V \to V,

der

B_{1}

auf

B_{2}

abbildet, positive Determinante hat.
Die Relation "sind gleichorientiert" definiert eine Äquivalenzrelation, das habe ich schon gezeigt. Nun soll ich zeigen, dass es genau zwei Äquivalenzklassen gibt.
Dazu die Idee:

B_{1}, B_{2}

sind wie in Definition gewählt, mit

{det f}_{1,2} < 0 (= 0

ist ausgeschlossen, da bijektiv). Dann ist jede Basis

B

äquivalet zu

B_{1}

oder

B_{2}

f_{1}

sei die Abbildung, die

B

auf

B_{1}

bringt,

f_{2}

analog.
Gilt dann

f_{2} = f_{1,2} \circ f_{1}

?

Und wer sagt mir, dass es immer Basen gibt, die nicht gleich orientiert sind?

Lieben Dank!

Shipwater aktiv_icon

19:53 Uhr, 01.04.2014

Jap das sieht gut aus und dann hast du ja

\det (f_{2}) = \underset{< 0}{\underset{⎵}{\det (f_{1, 2})}} \cdot \det (f_{1})

also ist entweder

\det (f_{1}) > 0

oder

\det (f_{2}) > 0

Und zur letzten Frage: Zu beliebigem

B_{1}

kannst du ein anders orientiertes

B_{2}

einfach erhalten, indem du das erste Basiselement mit

- 1

multiplizierst. Denn die Determinante der Basiswechselmatrix ist ja dann -1.

MathsTom aktiv_icon

19:56 Uhr, 01.04.2014

Danke, dass du drüber geguckt hast!

Wieso ist die Determinante dann

- 1

? ;-)

Shipwater aktiv_icon

20:04 Uhr, 01.04.2014

Wie sieht denn die entsprechende Basiswechselmatrix aus? (also die bezüglich

B_{1}

und

B_{2}

meine ich damit natürlich)

MathsTom aktiv_icon

20:07 Uhr, 01.04.2014

Der Begriff sagt mir leider nichts... Aber ich kann dann ja die Darstellungsmatrix von

f

bzgl den zwei Basen betrachten. Diese müsste dann Diagonalgestalt haben, oder? Mit Diag(-1,1,...,1). Dann folgt das sofort.

Shipwater aktiv_icon

20:10 Uhr, 01.04.2014

Richtig, so hab ich das gemeint.

MathsTom aktiv_icon

20:11 Uhr, 01.04.2014

Danke! :-)

1155833

1155640

	Status: nicht eingeloggt	Noch nicht registriert?