Binomialkoeffizienten & Kombinatorik: 1. (n tief k)= (n tief (n-k)), 2. (n tief k)+(n tief(k+1))=((n+1)tief(k+1))

Question

Beweise für alle n€N und alle o ≤ k ≤ n die Gleichheit von
1. „n aus k“ = „n aus (n-k)“ und
2. „(n aus k)+(n aus (k+1))“ = „(n+1) aus (k+1)„
Beweise 1. Durch Verwendung der Definition der Binomialkoeffizienten und Fakultäten und
2. Durch ein kombinatorisches Argument.

Comments

Was sind denn deine Ideen zu der Aufgabe ? Eigentlich sehen die doch nicht so schwer aus. Und Tipps waren auch schon gegeben? Wo liegt also das Problem?

---

Ja ich weiß nicht, was ein kombinatorisches Argument ist

---

Vgl. auch https://de.wikipedia.org/wiki/Komplement_(Mengenlehre)

Answer 1

Hier mal das 'kombinatorische Argument':

2. „(n aus k)+(n aus (k+1))“ = „(n+1) aus (k+1)„

 „(n+1) tief (k+1)„ steht für die Anzahl der 'k+1' -elementigen Teilmengen einer n+1 - elementigen Menge.

Die kann man folgendermassen zählen:

Die Zahl der 'k+1' -elementigen Teilmengen, die das Element Nr. n+1 enthalten.

Plus

Die Zahl der 'k+1' -elementigen Teilmengen, die das Element Nr. n+1 nicht enthalten.
Nun die beiden Teile separat:

Die Zahl der 'k+1' -elementigen Teilmengen, die das Element Nr. n+1 enthalten. =

Die Zahl der k elementigen Teilmengen aus den ersten n Elementen = ( n tief k)

und

Die Zahl der 'k+1' -elementigen Teilmengen, die das Element Nr. n+1  nicht enthalten. =

Die Zahl der k+1 elementigen Teilmengen aus den ersten n Elementen = ( n tief k+1)

Daraus folgt die Behauptung. qed.

Du kannst auch auch 1. mit einem kombinatorischen Argument beweisen:

Die Zahl der k-elementigen Teilmengen einer Menge mit n Elementen ist gleich gross wie die Zahl ihrer Komplementärmengen. Diese enthalten jeweils n-k Elemente und alle n-k-elementigen Mengen der Menge mit n Elementen sind Komplementärmengen einer k-elementigen Menge.

Daher folgt: (n tief k) = (n tief n-k)

Comments

Was ist gemeint mit „n tief k“ ?

---

Das ist dein 'aus', das mir nicht gefällt. n steht oben und k unten.

---

Achso, ich hab gelesen, dass man „n aus k“ oder „n über k“ sagen kann. ))

---

Dann hast du verkehrt aufgepasst

https://de.wikipedia.org/wiki/Binomialkoeffizient

Man sagt "n über k", "n tief k" ODER "k aus n".

Aber Achtung. Bei k aus n schreibt man das a trotzdem oben. D.h. "n über k" und "n aus k" sind nicht das Gleiche !!

---

Oh Ich habe kominatorisches Argument falsch interpretiert. So macht es natürlich mehr Sinn.

Aber ist Argumentieren ein Beweis ?

---

Kombinatorische Argumentation schon, da sie auf der kombinatorischen Definition der Binomialkoeffizienten beruht.

---

Mathecoach, du sagtest doch, man sagt nicht „n aus k“?

---

(k aus n) darfst du sagen. k unten und n oben.
Ist dann die Abkürzung für 'k Elemente aus einer Menge mit n Elementen'.

---

Ja dann ok .-)

---

https://de.wikipedia.org/wiki/Binomialkoeffizient#Kombinatorische_Beweise

Ich habe inzwischen oben auch noch 1. kombinatorisch bewiesen. 

---

Wo hast du es bewiesen?

---

In meiner Antwort angefügt.

---

Was heißt Komplementärmenge ?

---

http://www.mathe-lexikon.at/mengenlehre/mengenoperationen/komplementaermenge.html
Zitat: Wenn bei einer Mengendefinition eine Grundmenge M angegeben wird, so enthält die Komplementärmenge A' alle Elemente der Grundmenge M, die kein Element der Menge A sind.

Vielleicht habt ihr das in der Schule (Mengenlehre) Ergänzungsmenge genannt?

---

Also ist die Komplementärmenge(A') die ganze Menge?

---

Also ich weiss es schon, aber noch eine Frage: was heißt „plus“ und „und“ in deiner Antwort?

---

Plus ist '+'
und allein auf einer Zeile ist umgangssprachlich zu verstehen und dient zum Abtrennen der Aussagen.

---

Dann hab ich da doch noch Fragen: „Die Zahl der k+1 -elementigen Teilmengen, die das Element Nr.n+1 nicht enthalten.“ Das heißt k+1 aus n, oder nicht? Und 2.Frage: Ist es jetzt bewiesen?

---

.“ Das heißt k+1 aus n, oder nicht?

Ja. Genauer:

.“ Das heißt k+1 aus den ersten n.

Ja. Die Geschichte ist so bewiesen.

---

Mir schien es bloß wie eine Ausbuchstabierung

---

Ja. Das liegt daran, dass man bei der kombinatorischen Argumentation mit der Anzahl der Mengen operieren kann. (Vgl. kombinatorische Definition der Binomialkoeffizienten).

---

Ups..!! Noch was: Was ist das „Element Nr. n+1 ?“ Das ist das „...aus n+1“, nicht ?

---

Ich habe im Beweis die n+1 - elementigen Teilmengen einer n+1-elementigen Menge auf 2 Arten gezählt.
Erst direkt als (n+1 tief k+1) und dann habe ich unterschieden, ob die k+1-elementigen Mengen das n+1-te Element (=das Element Nr. n+1) enthalten, oder nicht. Zum Schluss muss man diese beiden Fälle dann addieren.

Vielleicht hilft es, wenn du mit Zahlen arbeitest.

Menge A = {1,2,3,4,5}

(5 tief 3) = (4 tief 3) * 1 + (4 tief 2)*1

Links: 3 - elem. Mengen von A
Rechts: 3-elem. Mengen aus {1,2,3,4} + (2-elem. Mengen aus {1,2,3,4} mit 5)

5 ist hier die Nr. n+1.

Answer 2

Kombinatorisch heißt du kannst die Regeln der Fakultäten benutzen und die Regel für den Binomialkoeffizienten.

 

(n über k) = (n über (n - k))

n!/(k!·(n - k)!) = n!/((n - k)!·( n - (n - k))!)

n!/(k!·(n - k)!) = n!/((n - k)!·k!)

wzbw.

 

(n über k) + (n über (k + 1)) = ((n + 1) über (k + 1))

n!/(k!·(n - k)!) + n!/((k + 1)!·(n - (k + 1))!) = (n + 1)!/((k + 1)!·((n + 1) - (k + 1))!)

n!/(k!·(n - k)!) + n!/((k + 1)!·(n - k - 1)!) = (n + 1)!/((k + 1)!·(n - k)!)

n!·(k + 1)/((k + 1)!·(n - k)!) + n!·(n - k)/((k + 1)!·(n - k)!) = (n + 1)!/((k + 1)!·(n - k)!)

(n!·(k + 1) + n!·(n - k))/((k + 1)!·(n - k)!) = (n + 1)!/((k + 1)!·(n - k)!)

(n!·(k + 1 + n - k))/((k + 1)!·(n - k)!) = (n + 1)!/((k + 1)!·(n - k)!)

(n!·(n + 1))/((k + 1)!·(n - k)!) = (n + 1)!/((k + 1)!·(n - k)!)

((n + 1)!)/((k + 1)!·(n - k)!) = (n + 1)!/((k + 1)!·(n - k)!)

wzbw.