Anzahl Möglichkeiten Anordnungen Kombinatorik

Question

Aufgabe:

Sei a_n die Anzahl Möglichkeiten, die Zahlen 1,...,n so anzuordnen, sodass an der k-ten Stelle entweder k − 1,k oder k + 1 steht.

(a) Berechnen Sie a_n für n = 1,2,3,4.
(b) Finden Sie eine Rekursionsformel für a_n+1 und begründen Sie Ihre Lösung.

Comments

missverständliche Formulierung:

Wahrscheinlich ist gemeint: ... an jeder k-ten Stelle, k=1,2,..n, entweder ...

Wahrscheinlich ist nicht gemeint:  ... sodass für ein festes k∈{1,...n} an der k-ten Stelle ...

---

Das kann ich leider auch nicht beantworten

---

Das zweite ist zu einfach für die Uni.

---

Könnte gemeint sein dass an der Stelle k z.B. k = 2 entweder 2(k), 1(k-1) oder 3(k+1) steht?

---

Genau das wird hier gemeint sein.

D.h. die 1 kann an erster oder 2. Stelle stehen.
Die 2 an 1., 2. oder 3. Stelle.
Die 4 an 3., 4. oder 5. Stelle.

Answer 1

Dann ist dem von Der_Mathecoach nichts zu Ergänzen

Du hast also akzeptiert, dass es für n=4 nur folgende Möglichkeiten gibt:

1234, 1243, 1324, 2134, 2143

Jetzt kommt die "5" dazu. Sie darf sicher ans Ende der bereits bestehenden Möglichkeiten, sie darf aber in einigen der 5 vorliegenden Möglichkeiten auch noch an die vorletzte Stelle dazwischen geschoben werden, allerdings nur, wenn bisher an letzter Stelle eine 4 war, die jetzt an den für sie noch erlaubten Platz 5 rutscht.

Comments

12345, 12435, 13245, 21345, 21435, 12354,  13254, 21354; a5 = 8

123456, 124356, 132456, 213456, 214356, 123546,  132546, 213546, 123465, 124365, 132465, 213465, 214365; a6 = 13

---

a₀ = 0

a₁ = 1

a_n = a_n-2 + a_n-1

Ist das so als Rekursive Formel gültig?

---

Du hast richtig erkannt, dass es sich um eine Fibonacci-Folge handelt.

Trotzdem würde ich den Beginn nicht bei 0, sondern bei 1 ansetzen.

\(a_1=1 \) , \(a_2=2 \)  und dann wie bei dir \(a_n=a_{n-1}+a_{n-2} \)

Answer 2

Eigentlich würde ich wenigstens erwarten, dass du für n von 1 bis 4 mal alle Möglichkeiten angeben kannst

a)

n = 1
1 ; a1 = 1
n = 2
12, 21 ; a2 = 2
n = 3
123, 132, 213 ; a3 = 3
n = 4
1234, 1243, 1324, 2134, 2143 ; a4 = 5

Bei a) steht zwar berechnen. Allerdings denke ich das durchaus angeben gemeint ist, denn eine Formel zum berechnen ist ja erst unter b) gefragt.

Prüfe mal meine Angaben. Es kann durchaus sein, dass ich die ein oder andere Möglichkeit hier vergessen habe.

Wenn man das jetzt soweit gemacht hat ist es doch eigentlich ein leichtes die Rekursionsformel anzugeben oder nicht?

Comments

Ich würde bei n = 4 diese Varianten aufführen:

1234, 1243, 2134, 2143, 3142, 3124, 1342, 2341, 2314, 3241, 3214; a4 = 12

---

Bei n = 4 stimme ich Max1337 zu, jedoch würde ich bei n = 3 noch 231 hinzufügen und a3 = 4

---

Ich würde bei n = 4 diese Varianten aufführen:

Wieso? Die Zahl k=1 darf nur an einer der Positionen k-1=0 (diese Possition gibt es nicht) oder an der Position k=1 oder an der Position k+1=2 sein.

Bei 2341 ist die Zahl 1 aber an der nicht erlaubten Position 4.

Die 1 darf weder an dritter noch an vierter Stelle stehen.

würde ich bei n = 3 noch 231 hinzufügen

Darfst du aber nicht.

---

Dann ist dem von Der_Mathecoach nichts zu Ergänzen

Eine Rekursionsformel fällt mir dennoch nicht ein

---

Wenn du nachdenkst glaube ich bestimmt, dass die eine Rekursion einfällt.

Wie kommt man also beispielsweise auf den Wert a4 = 5

Wenn die erste Zahl die 1 ist habe ich a3 Möglichkeiten die 4 - 1 Zahlen dahinter anzuordnen

Wenn die erste Zahl die 2 ist und die zweite Zahl die 1 habe ich dahinter a2 Möglichkeiten die Zahlen anzuordnen oder?

Gibt es jetzt noch Möglichkeiten die ich vergessen habe?

Wenn nicht dürfte es klar sein oder?