0 Daumen
364 Aufrufe

Sei M eine n-elementige Menge. 

Ich möchte beweisen, dass jeder Binomialkoeffizient der Form (n tief 3) über M, die folgende Eigenschaft hat:

"Jedes Element a ∈ M tritt in einem Binomialkoeffizient (n tief 3) genau Tn-2-mal auf"

Tist die n-te Dreieckszahl, also Tn=1+2+....+n = n(n+1)/2 = (n+1 tief 2)

Ich weiß, dass der es sicherlich mit der rekursiven Formel (n tief k)=(n-1 tief k-1) + (n-1 tief k) zu tun hat. Es ist auch nicht schwierig anhand der Formel zu zeigen, dass die Differenz zwischen (n tief 3) und dem Vorgänger (n-1 tief 3) die Dreieckszahl Tn-1 ist. Jedes (n-1 tief 3-1) ist ja eine Dreieckszahl. 

Aber ich drehe mich immer in Kreisen, wenn ich die Eigenschaft für die einzelne Elemente beweisen will.

Hat jemand eine Idee?

Danke!

Gefragt von

Präzision: Ein Element kann eigentlich nicht in einem Binomialkoeffizient auftreten. Wenn ich dich richtig verstehe, willst du nicht beweisen, dass:

"Jedes Element a ∈ M tritt in einem Binomialkoeffizient (n tief 3) genau Tn-2-mal auf"

sondern:

"Jedes Element a ∈ M tritt in genau Tn-2 dreielementigen Teilmengen von M auf"

Die beiden Brüche, die du hier vergleichst, kannst du so kürzen:

Tn-2 = (n-1 tief 2) = (n-1)(n-2)/2

(n tief 3) = (n(n-1)(n-2))/6

Das heisst du müsstest vielleicht begründen, dass (n tief 3) = n/3 * Tn-2

Schlauer ist wohl ein Induktionsbeweis.

Verankerung: n=3 

Ein Element kann in 1 Menge mit 3 Elementen liegen. T3-2 = 1 ok.

1 Antwort

0 Daumen

 

Zu zeigen: Tn-2 = (n-1 tief 2) = (n-1)(n-2)/2

(n tief 3) = (n(n-1)(n-2))/6

Das heisst du müsstest vielleicht begründen, dass (n tief 3) = n/3 * Tn-2

Schlauer ist wohl ein Induktionsbeweis.

Verankerung: n=3 

Ein Element kann in 1 Menge mit 3 Elementen liegen. T3-2 = 1 ok.

Induktionsschritt n -> n+1. D.h. von Tn-2 nach Tn-1

Differenz von Tn-1 - Tn-2 = n-1

In wievielen dreielementigen Teilmengen kann ein Element x einer n+1-elementigen Teilmenge liegen?

In allen, die aus den n ersten Elementen bestehen: Tn-2 Möglichkeiten

+

in allen, die das n+1-te Element enthalten und noch ein anderes (ausser x). Als Anderes kommen n-1 Elemente in Frage (nicht x und nicht das n+1-te.

-----------------------------------------

Total: Tn-2 + n-1 = Tn-1 qed Induktionsschritt.

Beantwortet von 141 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...