Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Induktions: Anzahl der k-elementigen Teilmeingen

Induktions: Anzahl der k-elementigen Teilmeingen

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Binomialkoeffizient

ray11 aktiv_icon

18:21 Uhr, 12.03.2020

Hi Leute, ich habe ein kleines Problem bei folgender Aufgabe:

Es seien

k, n \in ℕ

mit

n \geq k \geq 1

. Zeigen Sie mithilfe vollständiger Induktion, dass die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge

M

gleich

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

ist.

Induktion über

n :

Induktionsanfang:

n = 1 :

1 \geq k \geq 1 \Rightarrow k = 1

Die Anzahl der 1-elementigen Teilmengen einer 1-elementigen Menge ist natürlich

1,

was auch mit

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

passt.

Induktionsschritt:

n \to n + 1 :

Die Anzahl der k-elementigen Teilmengen einer

n + 1

-elementigen Menge soll

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

sein.
Wie geht man hier vor?

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

michaL aktiv_icon

19:11 Uhr, 12.03.2020

Hallo,

wenn deine Menge

M

nun

n + 1

Elemente hat, dann nehmen wir ein ganz spezielles Elemente aus

M

her, etwa

x

.

Nun kann in einer

k

-elementigen Menge

K

das

x

enthalten sein, oder eben nicht.
Wenn es nicht enthalten ist, dann ist es eine

k

-elementige Teilmenge der Menge

M \ {x}

, welche ja nur

n

Elemente hat.
Wenn es enthalten ist, dann ist noch Platz von

k - 1

Elemente, die ebenfalls aus

M \ {x}

stammen.

Sei ihm, wie ihn sei, in jedem Fall reduziert sich die Induktionsvariable

n

. Mal auf das

k

, mal nicht.

Damit - und mit einer speziellen EIgenschaft der Summe spezieller Binomialkoeffizienten - solltest du den Beweis abschließen können.

Mfg Michael

ray11 aktiv_icon

19:31 Uhr, 12.03.2020

Ahhh, jetzt geht mir ein Licht auf.
Nur noch pascalsches Dreieck und fertig, richtig?

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

Nur wäre ich nie im Leben drauf gekommen, dass man hier ein spezielles Element wählt und dann die zwei Möglichkeiten vergleicht.
Aber wenn man das weiß ist es natürlich einfach.
Vielen Dank.

abakus

20:05 Uhr, 12.03.2020

Dein Induktionsanfang ist unvollständig.
Du hast nur nachgerechnet, dass bei n=1 die Formel für die Anzahl der EINELEMENTIGEN Teilmengen stimmt. Den Fall n=1, k=0 hast du vergessen.

ray11 aktiv_icon

22:01 Uhr, 12.03.2020

Laut meiner Angabe sind

k

und

n \in ℕ

mit

n \geq k \geq 1

.
Somit habe ich den Fall

n = 1, k = 0

nicht, da

k \geq 1

ist.
Oder übersehe ich hier etwas?

abakus

22:05 Uhr, 12.03.2020

Nein, du hast nichts übersehen, ich habe die (eigentlich unnötige) Einschränkung auf k>0 übersehen.

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

1497043

1497029

	Status: nicht eingeloggt	Noch nicht registriert?