Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rechteck mit Kachelungen

Rechteck mit Kachelungen

Universität / Fachhochschule

Erzeugende Funktionen

Rekursives Zählen

Tags: Erzeugende Funktionen, Rekursives Zählen

Clemensum aktiv_icon

20:09 Uhr, 25.09.2012

Für

n \in ℕ

betrachte man ein

(1 \times n) -

Rechteck (also Breite 1, Länge n) und bezeichne mit

f_{n}

die anzahl der verschiedenen Kachelungen dieses Rechtecks mit

(1 \times 1) -

Kacheln und (

2 \times 1

)-Kacheln: Es ist offensichtlich

f_{1} = 1

und

f_{2} = 2 .

Zusätzlich definiere man

f_{0} = 1

und

f_{i} = 0

und

i \in ℤ, i < 0,

und haben damit die Zahlen

f_{n}

für alle

n \in ℤ

erklärt.
Zeigen Sie hierzu: Für

ℤ ∋ m, n \geq 0

die folgende Rekursion erfüllt ist und zwar durch direktes kombinatorisches Argument:

f_{m + n} = f_{m} f_{n} + f_{m - 1} f_{n - 1}

.

Zuerst eiinmal muss ich feststellen, dass sich der Dozent wahrscheinlich mit der angabe vertan hat. Wie soll denn dies sinn ergeben:

(1 \times 1) -

Kacheln und (

2 \times 1

)-Kacheln ? Da sollte doch wohl eher etwas in Abhängigkeit von

n

stehen, oda?

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

Bummerang

16:42 Uhr, 26.09.2012

Hallo,

"Da sollte doch wohl eher etwas in Abhängigkeit von

n

stehen, oda?"

Wieso? Du hast Kacheln der Form

1 x 1

und

2 x 1 (

in ausreichender Menge), die sind fest vorgegeben.

Wenn Dein

n = 1

ist, dann hast Du ein Rechteck der Größe

1 x 1

und da kannst Du die gegebenen Kacheln auf genau eine Art und Weise verlegen: Genau eine 1x1-Kachel. Deshalb ist

f_{1} = 1

.

Wenn Dein

n = 2

ist, dann hast Du ein Rechteck der Größe

1 x 2

und da kannst Du die gegebenen Kacheln auf genau zwei Arten und Weisen verlegen: Genau zwei 1x1-Kacheln oder genau eine 2x1-Kachel. Deshalb ist

f_{2} = 2

.

Und der Beweis, dass die angegebene Gleichung stimmt, ist auch einfach:

Zunächst nimmt man jede Möglichkeit bei den 1xm-Rechtecken, da gibt es

f_{m}

Stück und hängt jede Möglichkeit bei den 1xn-Rechtecken "hinten" an, da gibt es

f_{n}

Stück. Dann hat man eine der

f_{m} \cdot f_{n}

Möglichkeiten, für die gilt, dass an m-ter und (m+1)-ter Stelle jeweils eine 1x1-Kachel liegt.

Dann nimmt man an, dass an m-ter und (m+1)-ter Stelle eine 2x1-Kachel liegt. Die Anzahl der Möglichkeiten, die

(m - 1)

Stellen vorher zu füllen, ist

f_{m - 1},

die Anzahl der Möglichkeiten, die

(n - 1)

Stellen nachher zu füllen, ist

f_{n - 1}

. Das ergibt dann

f_{m - 1} \cdot f_{n - 1}

Möglichkeiten.

Da beide Möglichkeiten disjunkt sind, kann man deren Anzahlen addieren und erhält

f_{m + n} = f_{m} \cdot f_{n} + f_{m - 1} \cdot f_{n - 1}

Clemensum aktiv_icon

11:17 Uhr, 27.09.2012

Achso ist das! :O

Ein genial einfach Ansatz! Vielen Dank für deine Hilfe, es ist mir nun klar geworden!

P.S.
Es tut mir leid, dass ich nicht schon früher geantwortet habe, ich hatte ein paar deiner Ansätze anfangs nicht verstanden und habe mich nicht getraut zu antworten, weil es unehrlich gewesen wäre. Ich habe rein Interessenhalber in dein Profil geschaut!
Lieber Bumerang, es tut mir leid! :(

1031759

1031396

	Status: nicht eingeloggt	Noch nicht registriert?