Wie viele Möglichkeiten gibt es? (Knifflig)

16.03.2012, 18:38

AileenWie

Wie viele Möglichkeiten gibt es? (Knifflig)

Meine Frage:
Ich programmiere gerade ein Programm, das mir die Lösungen für Rätselaufgaben gibt, von denen ich leider das Lösungsheft verloren habe. Nun stehe ich vor folgendem Problem, dass ich nicht lösen kann:
Es geht darum, Felder entweder schwarz oder weiß zu malen. (Also man hat 2 Möglichkeiten) Es gibt eine gegebene Anzahl von Feldern, z.B. 10 die angemalt werden können. Am Rand stehten Zahlen, die anzeigen, wie viele Felder in Folge jeweils schwarz sind. Zwischen 2 schwarzen Feldern muss immer mindestens ein weißes sein.
Beispiel:
Es gibt 5 Felder _ _ _ _ _ Die Zahlen sind 1 2
Nun gibt es folgende Möglichkeiten:
(X entspricht schwarz, _ weiß)

X _ X X _
oder
X _ _ X X
oder
_ X _ X X

macht also 3 Möglichkeiten.
Nächstes Bespiel:
5 Felder _ _ _ _ _ Zahlen 1 1 1
X _ X _ X

macht 1 Möglichkeit.

Nun meine Frage: gibt es eine allgemeine Formel, mit der ich ausrechnen kann, wie viele Möglichkeiten es jeweils gibt? Ich weiß, dass wir in der Schule mal so etwas ähnliches gemacht haben, aber mit zusammenhängenden Zahlen und Freistellen dazwischen bin ich überfordert.

Ich hoffe ihr könnt mir helfen, diese Formel ist esentiell für die Weiterentwicklung meines Programms.
Liebe Grüße
Aileen

Meine Ideen:
Beispiele:
5 Felder _ _ _ _ _ Zahl 1

X _ _ _ _
_ X _ _ _
_ _ X _ _
_ _ _ X _
_ _ _ _ X

5 Möglichkeiten

5 Felder _ _ _ _ _ Zahl 2

X X _ _ _
_ X X _ _
_ _ X X _
_ _ _ X X

4 Möglichkeiten

5 Felder Zahl 3
3 Möglichkeiten

5 Felder Zahl 4
2 Möglichkeiten

5 Felder Zahl 5
1 Möglichkeit

Bis hierhin klappt es mit Anzahl Felder - schwarze Felder +1 = Anzahl Möglichkeiten

Aber bei 5 Felder Zahlen 1 1
gibt es 6 Möglichkeiten

Bei 5 Felder Zahlen 1 2
wiederum nur 3

16.03.2012, 19:47

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von AileenWie
Nun meine Frage: gibt es eine allgemeine Formel, mit der ich ausrechnen kann, wie viele Möglichkeiten es jeweils gibt?

Die gibt es, man muss nur ein wenig nachdenken, schon ist man bei einer kombinatorischen Grundkonstellation, es ist also nicht übermäßig "knifflig". Augenzwinkern

Allgemeine Situation: $\begin{eqnarray*} n \end{eqnarray*}$ Felder, davon $\begin{eqnarray*} s \end{eqnarray*}$ schwarze in $\begin{eqnarray*} k \end{eqnarray*}$ Blöcken mit festen Blockgrößen $\begin{eqnarray*} s_1,\ldots,s_k \end{eqnarray*}$ , die selbstverständlich dann $\begin{eqnarray*} s_1+\ldots+s_k=s \end{eqnarray*}$ erfüllen.

Dann sind noch $\begin{eqnarray*} w=n-s \end{eqnarray*}$ weiße Felder zu platzieren, auf $\begin{eqnarray*} k+1 \end{eqnarray*}$ mögliche Räume (zwischen den schwarzen Blöcken sowie links und rechts am Rand) mit der Forderung, dass zwischen den schwarzen Blöcken jeweils mindestens ein weißes Feld sein muss.

Wegen dieser letzten Forderung können noch $\begin{eqnarray*} w-(k-1)=n-s-k+1 \end{eqnarray*}$ weiße Felder frei (!) auf die $\begin{eqnarray*} k+1 \end{eqnarray*}$ Zwischenräume platziert werden.

Diese Anzahl berechnet sich gemäß der Anzahlformel "Kombinationen mit Zurücklegen":

$\begin{eqnarray*} \binom{(k+1)+(n-s-k+1)-1}{(k+1)-1} = \binom{n-s+1}{k} \end{eqnarray*}$

Angewandt auf deine Beispiele:

1 2 : n=5,s=1+2=3,k=2 mit Anzahl $\begin{eqnarray*} \binom{5-3+1}{2} = \binom{3}{2} = 3 \end{eqnarray*}$

1 1 1 : n=5,s=1+1+1=3,k=3 mit Anzahl $\begin{eqnarray*} \binom{5-3+1}{3} = \binom{3}{3} = 1 \end{eqnarray*}$

16.03.2012, 19:59

AileenWie

Auf diesen Beitrag antworten »

Vielen vielen Dank, das hat mir wirklich weiter geholfen. smile

17.03.2012, 11:47

NUrGast

Auf diesen Beitrag antworten »

RE: Wie viele Möglichkeiten gibt es? (Knifflig)

Zitat:

Original von AileenWie
Beispiel:
Es gibt 5 Felder _ _ _ _ _ Die Zahlen sind 1 2
Nun gibt es folgende Möglichkeiten:
(X entspricht schwarz, _ weiß)

X _ X X _
oder
X _ _ X X
oder
_ X _ X X

macht also 3 Möglichkeiten.

wirklich nur diese 3? warum nicht auch noch
XX_X_
XX_ _X
_XX_X

17.03.2012, 19:03

AileenWie

Auf diesen Beitrag antworten »

Weil die Reihenfolge auch noch angegeben ist. Sorry, das hatte ich vergessen zu schreiben. 1 2 heißt, es muss erst das eine Feld kommen, dann die 2. Ansonsten wäre es vermutlich unmöglich das Rätsel zu lösen Augenzwinkern

18.03.2012, 22:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von AileenWie
Weil die Reihenfolge auch noch angegeben ist.

Hatte ich nach Schilderung deines ersten Beispiels auch genauso verstanden.

Zitat:

Original von AileenWie
Ansonsten wäre es vermutlich unmöglich das Rätsel zu lösen

Das vielleicht, aber die Anzahlberechnung ist nicht schwieriger, es kommt lediglich ein (Permutations-)Faktor hinzu.

Neue Frage »

Antworten »

Wie viele Möglichkeiten gibt es? (Knifflig)

Verwandte Themen