Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rekursive Gleichung finden

Rekursive Gleichung finden

Universität / Fachhochschule

Erzeugende Funktionen

Tags: Kombinatorik

anonymous

22:29 Uhr, 26.03.2021

Stelle zu folgendem Problem eine Rekursionsgleichung mit Anfangsbedingungen auf:
Wie viele Wörter gibt es in

{A, B, C}^{n},

die

A A A

oder

A B A

(oder beides) enthalten?

Mein Ansatz: Mittels Rechnung per Hand und eines Python Skripts weiß ich, dass die fü

n = 0,1, . .

.
genau

0, 0, 0, 2, 11, 45, 170, 611

solcher Wörter existieren. Meine rekursive Gleichung lautet

a_{n} = 3 \cdot a_{n - 1} + 6 \cdot (3^{n - 4} - a_{n - 4})

mit

a_{0} = a_{1} = a_{2} = 0, a_{3} = 2

Zur Erläuterung der Bestandteile:

3 a_{n - 1}

ist ein Summand, weil jedes gültige Wort auch dann noch ein fültiges Wört ist, wenn ich

A, B

oder

C

am Ende hinzufüge

(3^{n - 4} - a_{n - 4})

sind alle möglichen Wörter der Länge

n - 4,

aber minus all jener Wörter, welche schon die Zeichenkette

A A A

oder

A B A

enthalten
Diese Wörter werden mit 6 multipliziert, weil an jedes dieser Wörter ein

A A A A, B A A A, C A A A, A A B A, B A B A

oder

C A B A

hinzugefügt werden kann, also alle "neu geschaffenen" gültigen Wörter

Die Folge, welche durch meinen Ansatz erzeugt wird ist

0, 0, 0, 2, 12, 42, 180,

Es weicht also leicht von der richtigen Lösung ab

Mir ist bereits aufgefallen, dass bei meiner Folge

12

und nicht

11

vorkommt, weil

A A A A

doppelt gezählt wird, aber ich weiss nicht, wie ich meine Formel anpassen kann, um den Fehler zu beheben

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Gemischte Aufgaben der Kombinatorik
Kombinatorik: Ziehen mit Reihenfolge und mit Zurücklegen
Kombinatorik: Ziehen mit Reihenfolge und ohne Zurücklegen
Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

HAL9000

23:04 Uhr, 26.03.2021

> Diese Wörter werden mit 6 multipliziert, weil an jedes dieser Wörter ein AAAA [...] hinzugefügt werden kann.

Wenn du AAAA anfügst, dann hast du ein Wort, welches du bereits in deinem

3 a_{n - 1}

erfasst hast - das leidige Problem der Mehrfachzählung, wenn man nicht richtig aufpasst...

Nein, diese Rekursion muss überarbeitet werden. Stoisch systematisch z.B. so:

1.Fall: Letzter Buchstabe B oder C. Anzahl

2 a_{n - 1}

.
2.Fall: Letzter Buchstabe A. Weitere Unterteilung nötig.
2.1.Fall: Vorletzter Buchstabe C. Anzahl

a_{n - 2}

.
2.2.Fall: Vorletzter Buchstabe B. Weitere Unterteilung nötig.
2.2.1.Fall: Drittletzter Buchstabe A. Anzahl

3^{n - 3}

.
2.2.2.Fall: Drittletzter Buchstabe B oder C. Anzahl

2 a_{n - 3}

2.3.Fall: Vorletzter Buchstabe A. Weitere Unterteilung nötig.
2.3.1.Fall: Drittletzter Buchstabe A. Anzahl

3^{n - 3}

.
2.3.2.Fall: Drittletzter Buchstabe B. Weitere Unterteilung nötig.
2.3.2.1.Fall: Viertletzter Buchstabe A. Anzahl

3^{n - 4}

.
2.3.2.2.Fall: Viertletzter Buchstabe B oder C. Anzahl

2 a_{n - 4}

2.3.3.Fall: Drittletzter Buchstabe C. Anzahl

a_{n - 3}

.

Sammeln wir alles auf:

a_{n} = 2 a_{n - 1} + a_{n - 2} + 3 a_{n - 3} + 2 a_{n - 4} + 7 \cdot 3^{n - 4}

.

P.S.: Man hätte auch zunächst die Anzahl

b_{n}

aller

n

-buchstabigen Wörter betrachten können, die weder AAA noch ABA enthalten, d.h., per Komplement ist dann

a_{n} = 3^{n} - b_{n}

.

Dann ist nämlich

(b_{n})

eine homogene Differenzenfolge

b_{n} = 2 b_{n - 1} + b_{n - 2} + 3 b_{n - 3} + 2 b_{n - 4}

mit den Startwerten

b_{0} = 1, b_{1} = 3, b_{2} = 9, b_{3} = 25

N8eule

00:00 Uhr, 27.03.2021

Hallo
Das ist eine Aufgabe, wie sie vom Typus her hier im Forum schon ein paar mal etwa folgendermaßen angegangen und zur Lösung empfohlen wurden.

Worte der Länge

n = 3

lassen sich ja noch verhältnismäßig leicht abzählen.
Überleg dir mal:
Wie viele Worte der Länge

n = 3

gibt es denn?

Kriterium

α :

Wie viele Worte der Länge

n = 3

enthalten bereits die Ausdrücke "AAA" oder "ABA"?

Kriterium

β :

Wie viele Worte der Länge

n = 3

erfüllen noch nicht das Kriterium

α,

enden jedoch auf "AA" oder "AB"?

Kriterium

γ :

Wie viele Worte der Länge

n = 3

erfüllen weder Kriterium

α

noch

β,

enden jedoch auf "A"?

Kriterium

δ :

Wie viele Worte der Länge

n = 3

erfüllen weder Kriterium

α,

noch

β,

noch

γ, i . a . W

. bilden den traurigen Rest?

Das sollte so weit noch leicht abzählbar sein.

Jetzt aber die folgende Überlegung/Fortführung zur Untersuchung längerer Worte.
Worte der Länge

n = 4

kann man bilden, indem man an Worte der Länge

n = 3

noch einen Buchstaben hinten anfügt.
Worte der Länge

n = 5

kann man bilden, indem man an Worte der Länge

n = 4

noch einen Buchstaben hinten anfügt.
Worte der Länge

(n + 1)

kann man bilden, indem man an Worte der Länge

n

noch einen Buchstaben hinten anfügt.

Überleg dir mal:
Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

α

entstehen aus Worten der Länge

n

gemäß Kriterium alpha?
Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

α

entstehen aus Worten der Länge

n

gemäß Kriterium beta?
Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

α

entstehen aus Worten der Länge

n

gemäß Kriterium gamma?
Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

α

entstehen aus Worten der Länge

n

gemäß Kriterium delta?

Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

β

entstehen aus Worten der Länge

n

gemäß Kriterium alpha?

. .

.
Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

β

entstehen aus Worten der Länge

n

gemäß Kriterium delta?

Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

γ

entstehen aus Worten der Länge

n

gemäß Kriterium alpha?

. .

.

Wie viele Worte der Länge

(n + 1)

gemäß Kriterium

δ

entstehen aus Worten der Länge

n

gemäß Kriterium alpha?

. .

.

Einmal systematisch zu Ende gedacht - für immer glücklich... :-)

[

PS:
upps, sorry HAL, ich hatte nicht gesehen, dass du nachgebessert hast

]

HAL9000

15:20 Uhr, 29.03.2021

> Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

Wollte ich schon immer mal fragen: Was heißt in dem Zusammenhang "geschlossen" ? Denn posten kann man ja immer noch in dem Thread (wie jetzt eben gerade von mir geschehen).

N8eule

15:36 Uhr, 29.03.2021

Hallo HAL
Ich ahne, im Forum tauchen "geschlossene" Threads nicht mehr unter der Rubrik "offenen Fragen" oder "offene Rückfragen" auf.
Sonst richtig, sonst macht das nicht wirklich ein Unterschied.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1532636

1532511

	Status: nicht eingeloggt	Noch nicht registriert?