Hilfe Schubfachprinzip & Koeffizienten?

Question

Ich verzweifel hier an den Aufgaben, vorallem bei 1 weiß ich überhaupt nicht wie ich das korrekt mathematisch beweisen soll.

1.)Zeigen Sie unter Verwendung des Schubfachprinzipes, dass jede 5-elementige
Teilmenge von {1,2,3,4,5,6,7,8} mindestens zwei Zahlen enthält, deren
Summe 9 ist.

2.) Bestimmen Sie den Koeffizienten von x^2y^5 in (x + y)^7 und von wx^4y^3z
in (w + x + y + z)^9. ja der Multinomialkoeffizient... bloß wie...

Answer 1

1) Die Menge enthält acht Zahlen, nämlich genau 4 Paare, die sich jeweils zu 9 addieren. Damit also kein Paar mehr enthalten ist, dass sich zu 9 addiert, muss von jedem Paar eine Zahl "herausgenommen" werden. In einer 5-elementigen Teilmenge fehlen aber nur 3 Elemente, also bleibt immer ein Paar übrig, das sich zu 9 addiert.

Ich weiß zwar nicht, was das Schubfachprinzip ist, aber so kann mans beweisen.

2) Also das erste ist ja einfach der Binomialkoeffizient (7, 2) = 7!/(2!*5!) = 21

Beim zweiten musst du den Multinomialkoeffizient verwenden, der definiert ist als

(n, k₁, ..., k_r) = n!/(k₁!*...*k_r!)

mit k₁+...+k_r=n

In diesem Fall sind die k's:

k_w = 1

k_x = 4

k_y = 3

k_z = 1

Tatsächlich gilt 1+4+3+1 = 9 = n

Auszurechnen ist also:

9!/(1!*4!*3!*1!) = 2520

Comments

Schubfachprinzip: Seien m Objekte in n Kategorien („Schubfächer“) eingeteilt. Wenn m > n ist, so gibt es mindestens eine Kategorie, die mindestens zwei Objekte enthält.