標記有根樹的計數問題

Abstract

這篇論文主要是用類似於原始的費伯納西的兔子問題去做一些變形：每個月只能有其中某一對成兔生下一對幼兔，而幼兔要隔一個月才是成兔，而成兔才有機會生下一代幼兔。再藉由對應到標記的平面有根樹的方式，每一種繁衍的過程可以形成這樣的樹，又可以再對應到一組唯一的數列。我們發現固定某個月會產生許多可能的數列，然而幾個不同的數列可能會對應到同構的 “無標記” 平面有根樹。因此我們探討這種同構問題，提供方法去計算出：在同構之下應該會有幾組數列。

The main idea of this thesis adopts the fashion of the original Fibonacci-rabbit problem with a little adjustment. Every month only one mature rabbit couple gives birth of a pair of baby rabbits which needs another month to become mature. Once being mature a couple has a chance to give birth, but not necessarily ought to. We can record the breeding process of all rabbit generations as a labeled rooted tree. We then transform such a tree to be a corresponding sequence. After a few months, plenty of such labeled rooted trees as well as such sequences are created for all possibilities. Among them, several sequences share with a single rooted tree (without label) in groups. So the idea of isomorphic trees is coming out. We are interested in isomorphic trees and study the method to calculate the number of the sequences that share a given isomorphic tree.