Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Rekursives Zählen » Turm aus Bausteinen
Autor
Universität/Hochschule Turm aus Bausteinen
sonny
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.05.2021
Mitteilungen: 30
  Themenstart: 2021-08-01

Hallo zusammen, Ich beschäftige mich im Moment mit einer Aufgabe aus Peter Tittmann "Einführung in die Kombinatorik" Seite 78. Es soll ein Rekurrenzgleichungssystem aufgestellt werden. Ich vestehe allerdings nur die 1. Rekurrenzgleichung Wir haben einen ausreichend großen Vorrat an Holzbaustein vom Format 2x1x1. Auf wieviel verschiedene Arten können wir einen Turm der Höhe n mit einer Grundfläche der Größe 2 * 2 bauen? Lösung: b_n=Anzahl der Türme der Höhe n Man kann zwei Steine nebeneinander legen oder um 90° verdreht und darauf einen Turm von n-1 Steinen darauf bauen: 2b_(n-1) Man kann 4 Steine aufrecht stellen mit einer Grundfläche 2x2 und darauf einen Turm der Höhe n-2 bauen: b_(n-2) Jetzt kommt, was ich nicht verstehe: Man kann einen Stein hinlegen und zwei aufrecht daneben stellen, so dass eine Grundfläche von 2x2 entsteht. Dieses Gebilde kann man drei mal um 90° drehen: 4c_(n-1) Das ergibt für mich nachvollziehbar 1.Rekurrenzgleichung: \ b_n=2b_(n-1)+b_(n-2)+4c_(n-1) Nicht nachvollziehbar ist für mich: \ c_n=b_(n-1)+c_(n-1) Wie komme ich auf diese Gleichung? Wie kann ich mir den Turm c_1 und c_2 vorstellen? Gruß Sonny


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7131
Wohnort: Milchstraße
  Beitrag No.1, eingetragen 2021-08-01

\quoteon(2021-08-01 16:06 - sonny im Themenstart) Nicht nachvollziehbar ist für mich: \ c_n=b_(n-1)+c_(n-1) \quoteoff Hallo sonny, mMn müsste hier \ c_n=b_(n-2)+c_(n-1) stehen. Bist du sicher, dass die Formel stimmt?


   Profil
sonny
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.05.2021
Mitteilungen: 30
  Beitrag No.2, vom Themenstarter, eingetragen 2021-08-01

Ob die Formel stimmt, weiß ich nicht. So steht sie aber im Tittmann.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2659
  Beitrag No.3, eingetragen 2021-08-01

\quoteon(2021-08-01 16:06 - sonny im Themenstart) Nicht nachvollziehbar ist für mich: c_n=b_(n-1)+c_(n-1) \quoteoff $c_n$ ist die Anzahl der Türme der Höhe $n$, in deren unterster Ebene eine bestimmte (beliebige, aber dann fest gewählte) Hälfte frei bleibt. Wenn man das hier macht: \quoteon(2021-08-01 16:06 - sonny im Themenstart) Man kann einen Stein hinlegen und zwei aufrecht daneben stellen, so dass eine Grundfläche von 2x2 entsteht. \quoteoff Dann ist die unterste Ebene komplett und die nächste halb mit Bausteinen gefüllt. Man benötigt also zum Weiterbauen genau so einen "$c$-Turm" der Höhe $n$. Das erklärt den Summanden $b_n=\ldots+4\,c_{n-1}$. Wenn man einen $c$-Turm der Höhe $n$ bauen will, kann man das auf zwei Arten machen: 1. Man füllt zuerst die fehlende Hälfte der unterste Ebene mit einem liegenden Baustein auf und baut dann auf der entstehenden planen Unterlage einen $b$-Turm der Höhe $n-1$. 2. Man füllt zuerst die fehlende Hälfte der unterste Ebene mit zwei stehenden Bausteinen auf, die dann in die nächste Ebene hineinragen, und baut darauf dann einen $c$-Turm der Höhe $n-1$. Beides zusammen führt zu $c_n=b_{n-1}+c_{n-1}$. \quoteon(2021-08-01 16:43 - StrgAltEntf in Beitrag No. 1) mMn müsste hier \ c_n=b_(n-2)+c_(n-1) stehen. Bist du sicher, dass die Formel stimmt? \quoteoff Mir erscheint die Formel korrekt. --zippy [Die Antwort wurde nach Beitrag No.1 begonnen.]


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7131
Wohnort: Milchstraße
  Beitrag No.4, eingetragen 2021-08-01

\quoteon(2021-08-01 17:40 - zippy in Beitrag No. 3) \quoteon(2021-08-01 16:43 - StrgAltEntf in Beitrag No. 1) mMn müsste hier \ c_n=b_(n-2)+c_(n-1) stehen. Bist du sicher, dass die Formel stimmt? \quoteoff Mir erscheint die Formel korrekt. \quoteoff Mir jetzt auch. Ich dachte erst, \(c_n\) zählt die Anzahl der Türme der Höhe n, bei denen ganz unten ein liegender Baustein fehlt und ganz unten zwei Bausteine nebeneinander aufrecht stehen. Aber letzteres muss gar nicht sein.


   Profil
sonny
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.05.2021
Mitteilungen: 30
  Beitrag No.5, vom Themenstarter, eingetragen 2021-08-01

1. Man füllt zuerst die fehlende Hälfte der unterste Ebene mit einem liegenden Baustein auf und baut dann auf der entstehenden planen Unterlage einen b-Turm der Höhe n−1. Woraus besteht die unterste Ebene? Ein einzelner liegender Baustein kann es nicht sein, da ich nach dem Auffüllen die unterste Ebne des b-Turms habe. Oder ist es die 2.Zeile des "L", die ich mit dem liegenden Stein auffülle? Dann kann ich aber nur einen b-Turm der Höhe n-2 draufsetzen, wenn die Gesamthöhe n sein soll. 2. Man füllt zuerst die fehlende Hälfte der unterste Ebene mit zwei stehenden Bausteinen auf, die dann in die nächste Ebene hineinragen, und baut darauf dann einen c-Turm der Höhe n−1. Beides zusammen führt zu cn=bn−1+cn−1. Hier besteht die unterste Ebene aus einem liegenden Stein? Der Turm c_(n-1) beginnt dann in der 2. Zeile? PS: Ich weiß nicht, wie man zitiert.


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2055
Wohnort: Thüringen
  Beitrag No.6, eingetragen 2021-08-01

\quoteon(2021-08-01 18:42 - sonny in Beitrag No. 5) PS: Ich weiß nicht, wie man zitiert. \quoteoff Der Beitrag, der zitiert werden soll...einfach auf QUOTE (kleiner roter Pfeil) gehen unter dem Beitrag. Überflüssiges dann rauslöschen.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2659
  Beitrag No.7, eingetragen 2021-08-01

\quoteon(2021-08-01 18:42 - sonny in Beitrag No. 5) Oder ist es die 2.Zeile des "L", die ich mit dem liegenden Stein auffülle? \quoteoff Genau die. \quoteon(2021-08-01 18:42 - sonny in Beitrag No. 5) Dann kann ich aber nur einen b-Turm der Höhe n-2 draufsetzen, wenn die Gesamthöhe n sein soll. \quoteoff Du musst darauf achten, von welchem $n$ du gerade sprichst, denn es werden ja Teiltürme verschiedener Höhen betrachtet. Wenn man sich um $c_n$ kümmert, ist $n$ die Höhe des gerade betrachteten $c$-Turms und nicht notwendigerweise die Höhe des gesamten Turms. \quoteon(2021-08-01 18:42 - sonny in Beitrag No. 5) Hier besteht die unterste Ebene aus einem liegenden Stein? \quoteoff Nicht notwendigerweise, es könnten auch die oberen Hälften von zwei stehenden Steinen sein. Vergiss nicht, dass die unterste Ebene des gerade betrachteten $c$-Turms ja nicht die unterste Ebene des gesamten Turms sein muss. \quoteon(2021-08-01 18:42 - sonny in Beitrag No. 5) PS: Ich weiß nicht, wie man zitiert. \quoteoff Drücke auf "Quote". [Die Antwort wurde nach Beitrag No.5 begonnen.]


   Profil
sonny
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.05.2021
Mitteilungen: 30
  Beitrag No.8, vom Themenstarter, eingetragen 2021-08-22

Ich möchte eine Formel herleiten, mit der ich für eine gegebene Turmhöhe die Anzahl an Möglichkeiten direkt ausrechnen kann. Gegeben: \ I b_n=2b_(n-1)+b_(n-2)+4c_(n-1) II c_n=b_(n-1)+c_(n-1) b_0=c_0=c_1=1, b_1=2 Ich möchte nicht alle algebraische Umformungen zeigen, nur Zwischenschritte, damit ihr sehen könnt, ob ich bis zu einem gewissen Punkt noch alles richtig gemacht habe. eliminiere b aus I mit Hilfe von II: \ c_(n+3)=3c_(n+2)+3c_(n+1)-c_n mit einem Potenzreihenansatz führt diese Rekurrenz-Gleichung auf die erzeugende Funktion: \ F(z)=(1-2z+6z^2)/(1-3z-3z^2+z^3) Die Nullstellen des Nenners sind: \ z=-1, z=2-sqrt(3), z=2+sqrt(3) Somit ergibt sich als Ansatz für die Koeffizienten f_n der Potenzreihe: \ III f_n=p(2-sqrt(3))^n+q(2+sqrt(3))^n+r(-1)^n c_2 errechnet sich aus den anfangsbedingungen zu c_2=3 Diese Anfangsbedingungen in III eingesetzt liefert: \ f_n=(sqrt(3)+1)/(2*sqrt(3))*(2-sqrt(3))^n+1/(3+sqrt(3))*(2+sqrt(3))^n z.B:: f_10=110771 D.h. nur für einen c-Turm der Höhe 10 gibt es 110771 Möglichkeiten. Dasgleiche kann man dann für den b-Turm machen. Aber diese beiden Türme gibt es doch auch für die Höhe 10 gemischt!? Wie kann man diese Möglichkeiten ausrechnen?


   Profil
sonny hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]