Beweis mit Dreieckszahlen und Binomialkoeffizienten.

Question

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 T_n-2-mal auf"

T_n ist die n-te Dreieckszahl, also T_n=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 T_n-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.

Comments

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 T_n-2-mal auf"

sondern:

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

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

T_n-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 * T_n-2

Schlauer ist wohl ein Induktionsbeweis.

Verankerung: n=3 

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

Answer 1

 

Zu zeigen: T_n-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 * T_n-2

Schlauer ist wohl ein Induktionsbeweis.

Verankerung: n=3 

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

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

Differenz von T_n-1 - T_n-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: T_n-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: T_n-2 + n-1 = T_n-1 qed Induktionsschritt.