Frage von AnonyJS, 69

Herleitung vom Binomialkoeffizient - ein Schritt unverständlich?

Also Fakultät ist mir klar, die Anzahl aller Möglichkeiten mit Reihenfolge egal.

Nun kommt also die Frage: Wie viele Möglichkeiten existieren k aus n Elementen auszuwählen?

Für k=1 wären das n Möglichkeiten oder?

für k ∈ lN sollen das doch dann (n!)/((n-k)!) sein.

Genau diesen Schritt verstehe ich nicht. Geht nicht um die Umschreibung, sondern um das Verständnis.

Sei n=12 und k=2, dann sollen das 10! sein... Kann mir das jemand für doofe erklären??? Wenn man das einfach annimmt verstehe ich die Umschreibung, aber ich würde das sehr gerne verstehen wollen.

Danke.

Nachtrag: Sei n=3 und k=2

So gilt: 3!=3*2*1=6 und daraus Möglichkeiten 2 zu ziehen.

Wären 3!-2!=1! Also genau 1 und das ist logisch betrachtet doch total falsch.

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von kreisfoermig, 42

Zur Verfügung stehen n Objekte. Es sind k Objekte auszuwählen. Die Reihenfolge sei dabei nicht zu beachten, dass heißt z. B. die Wahlen 1,2,7,3 sowie 3,2,1,7 von k=4  Objekten aus n=8 Objekten sind ein und dieselbe.

Ansatz. Zunächst wird die Reihenfolge beachtet, danach werden die Verdoppelungen ausgemistet.

  • Es seien also k Plätze 1,2, …, k und jedem Platz ordne man einem eindeutigen Objekt aus den n Objekten. Dadurch geht man alle Möglichkeiten, auf geordnete Weise k von n zu wählen. Wie viele Möglichkeiten sind das? Na:
  • Zu Platz 1 stehen n Objekte zur Auswahl; zu Platz 2 dann n–1; zu Platz 3 dann n–2; … ; zu Platz k  dann n–(k–1) Objekte.
  • Das macht #Möglichkeiten = n·(n–1)·…·(n–(k–1)) = n·(n–1)·…·(n–(k–1))·[(n–k)·…·1] / [(n–k)·…·1] = n! / (n–k)!

Jetzt werden die Verdoppelungen gezählt. Wie viel mal werden kommen dieselben k Objekte x1, x2, … , xk vor, nur in einer anderen Reihenfolge? Das sind genau die Anzahl der Permutationen der k Plätze, welches k! sind. (Das kannst du leicht und getrennt von dieser Situation beweisen).

Folglich wird (zum Glück auf einheitliche Weise!!) eine jede Auswahl von k-Objekten aus den n genau k! doppelt gezählt. Sei N die Anzahl der Auswahl von k-Objekten aus den n. Dann gilt also

N·k! = Anzahl oben = n! / (n–k)!

Darum erhält man N = n! / (k!·(n–k)!).

Kommentar von AnonyJS ,

Danke, habe es nun verstanden.

Antwort
von gfntom, 14

Zu deinem Nachtrag:

n=3, k=2 -> n!/(n-k)!=3!/(3-2)!=3!/1!=3! = 6

d.h. du kannst auf 6 Arten 2 aus 3 auswählen, wenn es auf die Reihenfolge ankommt.
(nimm die Elemente a, b und c so hast du ab ac ba bc ca cb)

3! - 2! = 1!  wie du schreibst,ist erstens falsch und geht aus keiner Formel hervor.

Wenn es nicht auf die Reihenfolge ankommt hast du um den Faktor 2! = 2 weniger. Also 6 / 2 = 3.
(bei a, b, c hast du ab ac bc (weil ba ca und cb dort in anderer Reihenfolge schon vorkommen)

Allgemein:
spiel es einfach durch:
auf wieviele Arten kann man 2 aus 5 auswählen? (Elemente a,b,c,d,e):
Im ersten Zug hast du 5 Auswahlmöglichkeiten (also jedes Element der 5)
Beim zweiten Zug hast du 4 Auswahlmöglichkeiten (also wieder alle - das eine, das du bereits vorher gewählt hast)

Also gesamt 5 * 4 = 20
(ab ac ad ae ba bc bd be ca cb cd ce da db dc de ea eb ec ed)

Wenn die Reihenfolge egal ist, halbiert sich das wieder( *1/2! da es für 2 Elemente immer 2 Möglichkeiten gibt, zb ba = ab)

Und dies 5 * 4 ist genau das, was die Formel ergibt:
5! / (5-2)! = 5! / (3)! = 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 5 * 4 = 20




Expertenantwort
von Willy1729, Community-Experte für Mathematik, 33

Hallo,

nehmen wir an, Du möchtest berechnen, wieviel Möglichkeiten es gibt, aus 5 Elementen 2 auszuwählen, wenn man die Reihenfolge mit berücksichtigt. Dann kann das erste Element eines von 5 sein, das jeweils mit den 4 restlichen kombiniert werden kann, das wäre also 5*4 bzw. 5!/3! denn (5*4*3*2*1)/(3*2*1)=5*4

Auf die 3 kommst Du auch, wenn Du 5-3, also n-k rechnest.

So kommst Du auf n!/(n-k)!

Wenn es aber auf die Reihenfolge nicht ankommt, kannst Du alles durch k!, also durch 2! teilen, weil die Hälfte aller Elemente der Lösung nur dadurch zustandekommt, daß die Zahlen miteinander vertauscht werden:

2;1 ist ohne Beachtung der Reihenfolge das Gleiche wie 1;2 usw.

So kommst Du auf die Formel n!/[k!*(n-k)!], was der Binomialkoeffizient
n über k ist.

Herzliche Grüße,

Willy

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten