Kombinatorik, Sitzplätze

11.05.2011, 13:56

Shortstop

Kombinatorik, Sitzplätze

Ich soll die Anzahl der Möglichkeiten berechnen, eine beliebige Anzahl von Leuten auf eine Reihe von n Stühlen zu verteilen, ohne dass 2 Leute nebeneinander sitzen. Dabei ist die leere Reihe (also 0 Leute) auch eine Möglichkeit.

Also:

0 Leute: 1 Möglichkeit
1 Leute: n Möglichkeiten

Und hier bin ich mir schon nicht mehr so sicher, mein Gedankengang ist: Alle Möglichkeiten, 2 Stühle aus n Stück auszuwählen abzüglich derer, wo 2 nebeneinander sitzen:

2 Leute: $\begin{eqnarray*} \binom{n}{2} - (n-1) \end{eqnarray*}$

Ab hier find ich keinen Weg mehr, die Anzahlen zu bestimmen. Ich kann nur noch sagen, dass man maximal $\begin{eqnarray*} \lceil \frac{n}{2} \rceil \end{eqnarray*}$ Leute auf die Stühle verteilen kann, ohne dass welche nebeneinander sitzen.

Weiß jemand Rat?

11.05.2011, 14:01

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von kvnb
2 Leute: $\begin{eqnarray*} \binom{n}{2} - (n-1) \end{eqnarray*}$

$\begin{eqnarray*} = \binom{n-1}{2} \end{eqnarray*}$

Und das ist durchaus kein Zufall, bei 3 Leuten kommt $\begin{eqnarray*} \binom{n-2}{3} \end{eqnarray*}$ heraus. Jetzt muss du dir nur noch überlegen, wieso das so ist.

P.S.: Ein leicht anderer Zugang zu dem Problem hier geht über die Fibonacci-Folge.

11.05.2011, 14:24

Shortstop

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
P.S.: Ein leicht anderer Zugang zu dem Problem hier geht über die Fibonacci-Folge.

Danke dir erstmal. Wir sollen die Aufgabe mMn auch über diesen Zugang lösen, der Prof hatte erwähnt dass es etwas mit den Fibonacci-Zahlen zu tun hat. Also muss ich das anders angehen?

11.05.2011, 14:29

René Gruber

Auf diesen Beitrag antworten »

Rekursiv denken! Sei $\begin{eqnarray*} a_n \end{eqnarray*}$ die gesuchte Anzahl Möglichkeiten bei $\begin{eqnarray*} n \end{eqnarray*}$ Stühlen.

Nun gibt es für den letzten, $\begin{eqnarray*} n \end{eqnarray*}$ -ten Stuhl genau zwei mögliche Fälle: besetzt oder nicht besetzt. In jedem der beiden Fälle kannst du die Anzahlen bestimmen über irgendwelche $\begin{eqnarray*} a_k \end{eqnarray*}$ mit $\begin{eqnarray*} k<n \end{eqnarray*}$ ...

11.05.2011, 14:56

Shortstop

Auf diesen Beitrag antworten »

Okay.

Fall 1: Der n-te Stuhl ist besetzt. Dann muss der (n-1). frei sein und die Anzahl der Möglichkeiten ergibt sich als die der Möglichkeiten, Leute auf (n-2) Stühle in einer Reihe zu verteilen.

Fall 2: Der n-te Stuhl ist leer. Die Anzahl der Möglichkeiten ergibt sich als die Anzahl derer, Leute auf (n-1) Stühle in einer Reihe zu verteilen.

Also:
$\begin{eqnarray*} a_n = a_{n-1} + a_{n-2} \end{eqnarray*}$ wobei aber $\begin{eqnarray*} a_1=2 \end{eqnarray*}$ und $\begin{eqnarray*} a_2=3 \end{eqnarray*}$ , und damit ist das die Folge der Fib-Zahlen.

...so einfach?

11.05.2011, 15:05

René Gruber

Auf diesen Beitrag antworten »

Zumindest eine (vom Index her) verschobene Fibonacci-Folge, denn beim Original ist ja

$\begin{eqnarray*} F_0=0,\; F_1=1,\; F_2=1,\;F_3=2,\;F_4=3,\;\ldots \end{eqnarray*}$ ,

d.h. hier ist $\begin{eqnarray*} a_n = F_{n+2} \end{eqnarray*}$ .

11.05.2011, 15:11

Shortstop

Auf diesen Beitrag antworten »

Jepp, das ist mir auch eben aufgefallen.

Vielen Dank smile

edit: Ich soll nun noch zeigen, dass für einen kreisrunden Tresen gilt, dass die Anzahl für $\begin{eqnarray*} n\ge 2 \end{eqnarray*}$ gleich $\begin{eqnarray*} F_n + F_{n-2} \end{eqnarray*}$ ist.

Ich bekomme aber raus, dass in

Fall 1: Der n-te besetzt, die 2 anliegenden frei, also die Anzahl ist gleich $\begin{eqnarray*} a_{n-3} = F_{n-1} \end{eqnarray*}$

und

Fall 2: Der n-te frei, die Anzahl ist gleich $\begin{eqnarray*} a_{n-1}=F_{n+1} \end{eqnarray*}$

also insgesamt gleich $\begin{eqnarray*} F_{n+1} + F_{n-1} \end{eqnarray*}$ . Wo liege ich falsch?

11.05.2011, 15:26

Shortstop

Auf diesen Beitrag antworten »

Ich glaube der Grund sind unterschiedliche Definitionen der Fibonacci-Zahlen...

11.05.2011, 18:17

René Gruber

Auf diesen Beitrag antworten »

Ja, damit hast du wohl Recht. Obwohl die von mir oben angegebene Variante die meistens übliche ist, kommt es doch gelegentlich vor, dass man mit $\begin{eqnarray*} F_0=F_1=1 \end{eqnarray*}$ startet, so wohl auch bei dir.

Neue Frage »

Antworten »

Kombinatorik, Sitzplätze

Verwandte Themen