Rekursion

01.06.2006, 00:31

Marie-Theres

Rekursion

Hallo

Ich weiß grade nicht wie ich da vorgehen soll, aber vielleicht könnt ihr mir ja helfen. also hier mals die aufgabenstellung:

Stellen sie eine Rekursion für die gesuchten Zahlen an auf und lösen sie diese:

Es sei an die Anzahl aller Teilmengen der Menge {1, 2, ...., n} die keine aufeinanderfolgenden Zahlen enthalten.

Jetzt stellt sich mir die Frage was ist mit aufeinanderfolgenden Zahlen gemeint. {1, 3, 5 etc und das für jede Zahl?}
Bitte bitte helft mir!!!

01.06.2006, 00:38

JochenX

Auf diesen Beitrag antworten »

auf einanderfolgende Zahlen sind z.B. 3 und 4; oder 7 und 8; oder n-2 und n-1
nicht aber z.B. 6 und 8

war das dein Problem?
HöMa? verwirrt

01.06.2006, 00:42

Mazze

Auf diesen Beitrag antworten »

Einanderfolgend würde ich als die Nachfolgerelation bezüglich der natürlichen Zahlen charakterisieren wollen (schwall). In sofern wäre

$\begin{eqnarray*} \{1,3,5\} \in A_n \end{eqnarray*}$

für n >= 5

Was ich jetzt von Dir wissen will:

Zitat:

Stellen sie eine Rekursion für die gesuchten Zahlen an auf und lösen sie diese:

Eine rekursive Darstellung für die Zahlen oder der Menge A_n ?

Du wirst schnell feststellen das für n < m gilt $\begin{eqnarray*} A _n \subset A_m \end{eqnarray*}$ woraus Du doch schon die rekursive darstellung fast ableiten kannst.

$\begin{eqnarray*} A_n = A_{n-1} \cup Rest \end{eqnarray*}$

Die Frage ist jetzt wie "Rest" aussieht Augenzwinkern

01.06.2006, 00:42

Marie-Theres

Auf diesen Beitrag antworten »

und jezt eine Rekursion aufstellen und diese lösen.
das ist eher mein problem Augenzwinkern

@mazze
eine Rekursion für die gesuchten Zahlen a_n

01.06.2006, 00:46

Mazze

Auf diesen Beitrag antworten »

Dann versteh ich das Problem nicht, erklärs mal anders oder poste den original Wortlaut der Aufgabe.

01.06.2006, 00:51

Marie Theres

Auf diesen Beitrag antworten »

der original wortlaut ist der aus post 1
aber ich werde daraus ned schlau

01.06.2006, 00:58

Mazze

Auf diesen Beitrag antworten »

Urks, jetzt seh ich's auch (sollte besser lesen), die Anzahl aller Teilmengen, a_n ist also eine Folge ganzer Zahle, fangen wir mal an:

Du hast die Zahl 1, dann gibt es nur eine Teilmenge nämlich die 1 selber

$\begin{eqnarray*} A_1 = 1 \end{eqnarray*}$

Jetzt hast Du die Zahlen (1,2), da sind 3 Teilmengen möglich

{1},{2}{1,2}

{1,2} fällt raus wegen der Bedingung macht also für

$\begin{eqnarray*} A_2 = 2 \end{eqnarray*}$

{1,2,3}

=> {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

davon sind aber nur 4 zu gebrauchen

$\begin{eqnarray*} A_3 = 4 \end{eqnarray*}$

Was auffällt ist das alle Mengen der vorherigen Menge in der neuen drin sind. Aber es werden noch einige zusätzliche , das was ich als Rest benannt habe (oben) dazu kommen.

$\begin{eqnarray*} A_n = A_{n-1} + Rest \end{eqnarray*}$
Jetzt überleg dir mal wie der Rest ausehen muss Augenzwinkern

edit:

habe A_3 geändert, aufpassen es sind nur 4 zu gebrauchen!

01.06.2006, 01:20

MarieTheres

Auf diesen Beitrag antworten »

Ja also:

An = an-1 + an-2 + an-3+ ....... an

Oder?
Aber eigentlich nimmt man bei mengen ja den durchschnitt oder die vereinigung. ma is schon spät und ich steh auf der leitung.

01.06.2006, 01:32

Marie Theres

Auf diesen Beitrag antworten »

Der rest ist besteht doch immer aus den einzelnen Teilmengen der Vorgänger, aber wie soll man den formell in einer Gleichung darstellen?

01.06.2006, 09:01

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} A_n \end{eqnarray*}$ die Menge der Teilmengen von $\begin{eqnarray*} \{1,2,\ldots,n\} \end{eqnarray*}$ mit der angegebenen Eigenschaft, und $\begin{eqnarray*} a_n=|A_n| \end{eqnarray*}$ deren Anzahl.

Wenn du die Rekursion aufstellen willst, musst du für die Mengen $\begin{eqnarray*} M \end{eqnarray*}$ innerhalb $\begin{eqnarray*} A_n \end{eqnarray*}$ zwei Fälle unterscheiden:

1.Fall: $\begin{eqnarray*} n\not\in M \end{eqnarray*}$

Solche Mengen $\begin{eqnarray*} M \end{eqnarray*}$ gibt es genau $\begin{eqnarray*} a_{n-1} \end{eqnarray*}$ Stück.

2.Fall: $\begin{eqnarray*} n\in M \end{eqnarray*}$

Hier muss $\begin{eqnarray*} (n-1)\not\in M \end{eqnarray*}$ gelten, sonst ist die Bedingung verletzt...

So, alles verrate ich natürlich nicht. Weitere Fälle gibt es nicht !

@Mazze

Du hast die leere Menge als Teilmenge vergessen.

01.06.2006, 09:22

Mazze

Auf diesen Beitrag antworten »

Zitat:

Du hast die leere Menge als Teilmenge vergessen.

Ich hatte die leere Menge bewusst nicht gewählt, weils ja keine Zahlen gibt. Gibt natürlich auch keine Verletzung der Bedingung, insofern...

01.06.2006, 09:25

Auf diesen Beitrag antworten »

... muss man sie mitzählen als Menge, die die Bedingung erfüllt. Augenzwinkern

04.06.2006, 18:34

Mira

Auf diesen Beitrag antworten »

Hallo,
das scheint ja eine allseits beliebte Aufgabe zu sein smile

Vorgehensweise:
Am besten schreibt man sich zuerst zwecks Orientierung einige Fälle auf:
n=0: {}
n=1: {}{1}
n=2: {}{1}{2}
n=3: {}{1}{2}{3}{1,3} --> Teilmenge {1,2} darf nicht rein, weil 1 und 2 zwei aufeinanderfolgende Zahlen sind (immer beachten!)
n=4: {}{1}{2}{3}{4}{1,3}{1,4}{2,4}
n=5: {}{1}{2}{3}{4}{5}{1,3}{1,4}{1,5}{2,4}{2,5}{3,5}{1,3,5}

Jetzt schaut man sich an, wie gross die Anzahl der Teilmengen ist:
n=0: 1
n=0: 2
n=0: 3
n=0: 5
n=0: 8
n=0: 13
Was auffällt, ist, dass ab $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ die Anzahl der Teilmengen der Summe der zwei vorhergehenden entspricht: 2+3=5, 3+5=8, 5+8=13 usw. (Fibonacci-Folge)
Dementsprechend können wir die Rekursion bestimmen:
$\begin{eqnarray*} x_n = x_{n-1} + x_{n-2} \end{eqnarray*}$ , $\begin{eqnarray*} n \geq 2, n_0 = 1, n_1 = 2 \end{eqnarray*}$

Zur Lösung der Rekursionsgleichung wählen wir den Ansatz: $\begin{eqnarray*} x_n = \lambda^{n} \end{eqnarray*}$ und wandeln die Rekursionsgleichung in charakteristisches Polynom um:
$\begin{eqnarray*} \lambda^{2} - \lambda - 1 = 0 \end{eqnarray*}$

Wir berechnen die Nullstellen:
$\begin{eqnarray*} - \frac{p}{2} \pm \sqrt{(\frac{p}{2})^2 - q} \end{eqnarray*}$
$\begin{eqnarray*} - \frac{1}{2} \pm \sqrt{(\frac{1}{2})^2 +1} \end{eqnarray*}$
... $\begin{eqnarray*} \Rightarrow \lambda_1 = \frac{1+\sqrt{5}}{2} , \lambda_2 = \frac{1-\sqrt{5}}{2} \end{eqnarray*}$

$\begin{eqnarray*} \lambda_1 \neq \lambda_2 \end{eqnarray*}$ und $\begin{eqnarray*} \lambda_1 , \lambda_2 \in \mathbb R \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ allg. Lösung gegeben durch $\begin{eqnarray*} x_n = c_1 \cdot \lambda_1^{n} + c_2 \cdot \lambda_2^{n} \end{eqnarray*}$

Einsetzen:
I. $\begin{eqnarray*} n_0 = 1 = c_1 \cdot (\frac{1+\sqrt{5}}{2})^0 + c_2 \cdot (\frac{1-\sqrt{5}}{2})^0 = c_1 + c_2 \end{eqnarray*}$
II. $\begin{eqnarray*} n_1 = 2 = c_1 \cdot (\frac{1+\sqrt{5}}{2})^1 + c_2 \cdot (\frac{1-\sqrt{5}}{2})^1 \end{eqnarray*}$

Gleichungssystem lösen: $\begin{eqnarray*} II. - I \cdot \frac{1-\sqrt{5}}{2}<br /> \Rightarrow c_1 = \frac{3+ \sqrt{5}}{2\cdot \sqrt{5}} , c_2 = 1 - c_1 \end{eqnarray*}$

Neue Frage »

Antworten »

Rekursion

Verwandte Themen