n Objekte in Reihe, keine gleichen nebeneinander

16.08.2012, 22:40	unr8d	Auf diesen Beitrag antworten »
n Objekte in Reihe, keine gleichen nebeneinander Guten Abend, ich hab hier ne kleine Aufgabe: Es befinden sich n Objekte in einer Reihe, die jeweils die Zustände 0 und 1 annehmen können. Dabei sollen keine zwei Objekte mit dem Zustand 1 nebeneinander liegen. Auf wie viele Arten ist das möglich? Ich weiß leider nicht recht wie ich da rangehen soll. Mir ist bisher nur aufgefallen, dass sich die Möglichkeiten für die n´te Stelle, wenn man der Reihe nach durchgeht, sich wie die Fibonacci-Zahlen zu verhalten scheinen. Möglichkeiten an Stelle i = f_(i+2), i=1,..,n Kann mir da jemand weiterhelfen? edit: Ok, eine Summenformel für die Fibonacci Folge lässt sich leicht aufstellen und eine explizite Formel für die einzelnen Elemente findet man auch, damit könnte man also den Wert der Summe angeben. Müsste man "nur" noch begründen, warum sich das mit den Möglichkeiten so verhält.
16.08.2012, 23:17	Mystic	Auf diesen Beitrag antworten »
RE: n Objekte in Reihe, keine gleichen nebeneinander Du musst einfach die "zulässigen" Binärfolgen der Länge n in jene unterteilen, welche auf 0 enden und jene, welche auf 01 enden...
16.08.2012, 23:58	unr8d	Auf diesen Beitrag antworten »
Mein Gedanke mit dem Aufsummieren war natürlich völliger Blödsinn. Meinst du folgendes, bzw kann ich so argumentieren? Auf jedes Glied kann eine 0 folgen, aber nur auf eine 0 darf eine 1 folgen. Also Bezeichne $\begin{eqnarray} f_n \end{eqnarray}$ die Anzahl zulässiger Folgen bei n Stellen und $\begin{eqnarray} f_n^{(0)} \end{eqnarray}$ bzw $\begin{eqnarray} f_n^{(1)} \end{eqnarray}$ die Anzahl der zulässigen Folgen die auf 0 bzw 1 enden. Damit ist $\begin{eqnarray} <br /> f_n=f_n^{(0)}+f_n^{(1)}<br /> f_n^{(0)}=f_{n-1}<br /> f_n^{(1)}=f_{n-1}^{(0)}=f_{n-2} \end{eqnarray}$
17.08.2012, 00:05	Mystic	Auf diesen Beitrag antworten »
Ja, das meinte ich, wobei du für die Auflösung der Rekursion auch noch die Werte von $\begin{eqnarray} f_0 \end{eqnarray}$ und $\begin{eqnarray} f_1 \end{eqnarray}$ benötigst...
17.08.2012, 00:13	unr8d	Auf diesen Beitrag antworten »
Jo, klar. Da dürfte es genügen zu sagen $\begin{eqnarray} f_0:=1 \end{eqnarray}$ und $\begin{eqnarray} f_1=2 \end{eqnarray}$ offensichtlich, oder?
17.08.2012, 00:14	Mystic	Auf diesen Beitrag antworten »
Ja
Anzeige

17.08.2012, 00:15	unr8d	Auf diesen Beitrag antworten »
Super, danke

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »