0 Daumen
3,8k Aufrufe
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.
Avatar von
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

2 Antworten

0 Daumen

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)

Avatar von 162 k 🚀
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.
0 Daumen

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.

Avatar von 477 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community