Wie viele Möglichkeiten gibt es dafür?

...komplette Frage anzeigen

4 Antworten

Sei n=32. Es gibt n paarweise identische Steine und 2n Plätze. Es dürfen 0<=k<=n der Steine auf die Felder gelegt werden. Sei 0<=k<=n: wie viele Möglichkeiten gibt es, k Steine auf die Felder zu setzen? Na, dies ist gleich dem Problem, erstmals k Plätze von den 2n Plätzen zu wählen (danach legt man jeweils einen Stein auf ein Feld). Die Anzahl dieser Möglichkeiten? (2n über k).

Insgesamt ist die gesuchte Anzahl der Möglichkeiten gegeben durch die Summe über alle (2n über k) für 0<=k<=n. Jetzt vereinfacht man: wegen Symmetrie ist dies die hälfte der Summe von 0 bis 2n. Dies ist gleich 2^(2n). Also ist die Anzahl 2^(2n–1).

lks72 26.08.2015, 19:47

In der letzten Zeile hast du übersehen, dass du den mittleren Term (in diesem Fall (64 über 32)) auch durch 2 dividierst, dieser ist aber nur einmal da und damit am Ende nur noch 1/2 mal. Also noch 1/2 * (2n über k) dazuaddieren.

Trotzdem schöne Idee.

0
kreisfoermig 26.08.2015, 20:23
@lks72

Ups, ja, da hast du recht. [0,n] gespiegelt ist [n,2n] und nicht [n+1,2n]. Ich war ja unterwegs ; )

0

0 Steine auf 64 Felder ---> (64 über 0) = 1

1 Stein auf 64 Felder  --> (64 über 1)  = 64

.

u.s.w.

.

32 Steine auf 64 Felder --> (64 über 32)

.

u.s.w.

.

64 Steine auf 64 Felder (64 über 32) = 1

Die Summe aller dieser Summanden ist 2^64.

Allerdings ist nur die linke Seite interessant (0 bis 31), daher dividieren wir alles durch 2. Jetzt ist aber (64 über 32) nur "halb" da, also noch 1/2 * (64 über 32) dazu.

macht: 2^64 / 2 + (64 über 32) / 2

= 2^63 + (64 über 32) / 2

p.s. Falls 0 Steine nicht erlaubt sind, dann halt noch 1 subtrahieren vom Ergebnis.

Für den 1. Stein gibt es, wie Du schreibst, 64 Möglichkeiten.

Für den 2. Stein dann nur noch 63, für den 3. noch 62 Möglichkeiten usw.

Also insgesamt 64 ∙ 63 ∙ 62 ∙ 61 ∙  . . . ∙ 33 = 64 ! /32 !  = 4,82... ∙ 10⁵³

(etwa eine halbe Nonillion)

lks72 26.08.2015, 19:49

Dies sind die Möglichkeiten für genau 32 Steine, der Fragesteller möchte aber glaube ich alle Möglichkeiten von 1 bis 32 Steinen haben.

0

2080 würde ich sagen 64+63+62+61...+2+1

Was möchtest Du wissen?