棘手, 但很迷人 一一从有序树的计数看数学模型

《棘手, 但很迷人 一一从有序树的计数看数学模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、數學傳播33卷1期,pp.65-75棘手,但很迷人一一從有序樹的計數看數學模型柳柏濂一.問題的提出—從細胞繁殖到有序樹細胞繁殖(cell-growthproblem)是生物數學中的一個著名問題:從一個正方形的「細胞」開始,每次從其中一邊生長出一個新的細胞。如此繼續,所形成的「動物」不含空洞。那麼,n個細胞(正方形)能形成多少個不同的動物?我們試考察n=4的情形。四個細胞所形成的動物如下:n=4(1)(2)(3)(4)圖1對於一般的n。設f(n)表示n個細胞的不同動物數。迄今,只知道如下的結果(n≤24

2、)(見[1])n12345678910···2324f(n)1125123510836912854655···168,047,007,728654,999,200,403我們所說的不同的動物,指的是在旋轉,反射變換下不同的動物式樣。如果我們把細胞的生成限制在平面上,則所述的問題變成平面細胞繁殖問題。同樣,對於n=4,考察平面細胞的不同式樣,則圖1的(1),(3),(4)圖無變化,但圖(2)應變成下列兩個圖。6566數學傳播33卷1期民98年3月(1)(2)圖2也就是說,在平面上用旋轉變換,圖2中的圖(

3、1)無論如何是不能變成圖(2)的。處於三維空間的你,習慣於三維空間中的條件變換,往往不經意地把三維空間中的反射,用於限制在二維空間的圖形中,因而誤認為圖2中的圖(1),(2)是同一個圖。正是利用你習慣性思維造成誤判,電子商炮製出流行的俄羅斯方塊遊戲。當方塊在平面上翻著“筋斗”下落時(圖3),你能準確地判斷出它能否嵌入下方的凹洞中嗎?同樣限制在平面上,我們考慮在計算機演算法中不可或缺的樹圖(tree)。所謂n階樹,就是n個頂點的無圈連通圖,而每個頂點所連接的邊數稱為該頂點的度(degree)。易知:n階

4、樹有n−1條邊,且至少有兩個度為1的圖3點,即懸掛點(pendentvertex),或稱為葉點。限制在平面上變換的樹,稱為平面樹。把樹的某一點作特殊標號,這樣的樹稱為根樹(roo-tedtree)。此特殊的點稱為根點。根點是懸掛點的根樹稱為植樹(planttree),如同上述俄羅斯方塊的原理,圖4中兩棵平面植樹(1)和(2)是不同的。(1)有序植樹且是二叉樹(2)有序植樹且是二叉樹(3)有序植樹(4)有序樹圖4因為圖4中的樹(1)不能通過旋轉變為樹(2)。於是,在平面樹中「枝椏」都是有序的。因此,平面

5、植樹(圖4中(1)(2)(3))又稱為有序植樹(orderedplanttree),平面根樹(圖棘手,但很迷人—從有序樹的計數看數學模型674(4))(根點不一定是懸掛點)稱為有序樹(orderedtree),而像圖4的(1)(2)那樣僅由1度點和3度點組成的植樹,稱為二叉(有根)樹(2-raytree)。二叉樹的每個分叉都可以分成左右兩枝。我們看看以圖4中的兩棵二叉樹為模型的演算法框圖,就可以瞭解它們為什麼應該看作不同。我們約定左枝表示Yes,右枝表示No。以比較a,b,c3個不同的實數的大小為例。

6、(1)(2)圖5圖5中的框圖(1)的樹圖模型是圖4的根樹(1)(倒過來),它判斷是否有a=max{a,b,c}而圖5中的框圖(2)的樹圖模型是圖4的根樹(2)。它判斷是否有a=min{a,b,c}。一個自然提出的問題是:n階有序植樹有多少種不同的式樣?二.組合模型—枯燥的排隊激發鮮活的靈感排隊,在生活中屢見不鮮,你曾想過,排隊與有序樹有什麼聯系嗎?試看下面的一個排隊買票問題。戲院票房前有2n個人買票,其中n個人只有5角一張的紙幣,其餘的n個人只有1元一張的紙幣。在開始賣票時,票房裏無任何零錢,而每個人

7、只能買一張5角的票,問買票的人有多少種不同的排隊方法,能使每個人都能買到一張5角的票?68數學傳播33卷1期民98年3月我們分析一下,這種排隊方法,它必須具有下列特徵:(A)2n個人排隊,每個人手裡不是拿著5角就是拿著1元1(A)恰有n個人拿5角,另外n個人拿1元2(A)為了保證:「每個人都能買到一張5角的票」,第一個人必須拿5角,第2個人3(A)可拿5角或1元。若第2個人拿1元,則第3個人必須拿5角,否則票就賣不出去;若第2個人拿5角,則第3個人(甚至第4個人

8、)都可拿5角或1元···。為了使上述特徵變得清晰,我們把上述組合模型數字化。把拿5角的人表為0,拿1元的人表為1,於是符合要求的排隊,可表示為如下特徵:(B)長為2n的0,1序列1(B)序列中恰有n個0和n個1,且第1,2個數為0,12(B)(B)序列的第1項為0,且由首項到任一項所形成的子序列,0的個數不少於1的3個數我們稱滿足(B1),(B2),(B3)特徵的(0,1)序列為B序列。現在,回過頭來,看看我們的有序植樹。(圖