Rekursionsgleichung von Verteilungsproblem aufstellen

10.07.2012, 18:38	Ben91	Auf diesen Beitrag antworten »
Rekursionsgleichung von Verteilungsproblem aufstellen Meine Frage: Nabend! Die Aufgabe ist folgende: n Stühle stehen in einer Reihe. Wieviele Möglichkeiten gibt es, die Stühle so mit Männern und Frauen zu besetzen, dass keine zwei Frauen nebeneinander sitzen. Hierzu gilt es, die Rekursionsgleichung (R) zu finden, inklusive Anfangsbedingungen (A) $\begin{eqnarray} x_0, x_1, ... \end{eqnarray}$ . Meine Ideen: $\begin{eqnarray} W_{n} = \{x \epsilon \{m, f\}^{n} \| \textrm{ x enthällt keine 2 aufeinander folgenden f}\} \end{eqnarray}$ $\begin{eqnarray} w_{n} = \|W_{n}\| = \textrm{Anzahl solcher Worte} \end{eqnarray}$ Annahmen zu (R): Sei $\begin{eqnarray} (x_1, x_2, .., x_n) \epsilon W_n \end{eqnarray}$ Falls: $\begin{eqnarray} x_n = f \end{eqnarray}$ , dann $\begin{eqnarray} x_{x-1} = m \end{eqnarray}$ und $\begin{eqnarray} (x_1, x_2, .., x_{n-2}) \epsilon W_{n-2} \end{eqnarray}$ , also $\begin{eqnarray} x \epsilon W_{n-2} \{m\} * \{f\} \end{eqnarray}$ in diesem Fall $\begin{eqnarray} \to W_{n-2} \end{eqnarray}$ solche Worte. Falls:* $\begin{eqnarray} x_n = m \end{eqnarray}$ , dann $\begin{eqnarray} (x_1, x_2, .., x_{n-1}) \epsilon W_{n-1} \end{eqnarray}$ , also $\begin{eqnarray} x \epsilon W_{n-1} \{m\} \to W_{n-1} \end{eqnarray}$ solche Worte. Annahme zu (A):* $\begin{eqnarray} W_1 = \{m\} \end{eqnarray}$ , $\begin{eqnarray} w_1 = 2 = \{(m),(f)\} \end{eqnarray}$ $\begin{eqnarray} W_2 = \{m,f\} \end{eqnarray}$ , $\begin{eqnarray} w_2 = 3 = \{(mm),(mf),(fm)\} \end{eqnarray}$ $\begin{eqnarray} W_3 = \{m,m,f\} \end{eqnarray}$ , $\begin{eqnarray} w_3 = 5 = \{(mmm),(mmf),(mfm),(fmm),(fmf)\} \end{eqnarray}$ Dieser Lösungsversuch ist ähnlich dem, was wir in einer Übung für eine ähnliche Aufgabe behandelt hatten und ich bin mir unsicher, ob diese Lösung korrekt ist. Kann mir jemand Feedback geben, wie es um die Korrektheit bestellt ist?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »