有序樹的計數(shù)及其應(yīng)用

金應(yīng)烈， 任俊麗

( 南開大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 天津 300071 )

0 引言

RNA二級結(jié)構(gòu)的計數(shù)問題是計算分子生物學(xué)中的研究課題之一，也是組合數(shù)學(xué)的一個新興研究課題.文獻[1-6]研究了滿足一定參數(shù)條件的RNA二級結(jié)構(gòu)計數(shù)，但其結(jié)果大多只滿足于不同參數(shù)條件下的RNA二級結(jié)構(gòu)計數(shù)的遞推關(guān)系式、生成函數(shù)或近似估計值，而對完全顯示閉公式研究得很少.文獻[7-8]利用不同的對合算法研究了含有k個內(nèi)點的標(biāo)號有序樹的計數(shù).本文利用標(biāo)號有序樹與森林的對合，討論含有k+1個內(nèi)點和p個外層內(nèi)點且外層內(nèi)點的度不小于正整數(shù)m的頂點數(shù)為n+1-k的非標(biāo)號有序樹的計數(shù)，并給出端環(huán)長度不小于正整數(shù)m的RNA二級結(jié)構(gòu)計數(shù)的完全顯示閉公式.在本文中作如下規(guī)定：對于有序樹T中的一個內(nèi)點u， 若u的所有子結(jié)點均為葉子點，則稱u為外層內(nèi)點；否則，稱u為內(nèi)層內(nèi)點.高度為1的標(biāo)號有序樹稱為基本有序樹.

1 非標(biāo)號有序樹的計數(shù)

定理1設(shè)含有k+1個內(nèi)點、頂點數(shù)為n+1-k的標(biāo)號有序樹T組成的集合為A， 由k+1個基本有序樹組成的頂點數(shù)為n+1的森林Fk+1的集合為B， 其中k+1個基本有序樹的根結(jié)點標(biāo)號在{1,2,…,n+1-k}上，則A與B之間存在一個雙射.

1)在有序樹T的所有外層內(nèi)點中，找出標(biāo)號最小的外層內(nèi)點vi；

3)重復(fù)以上過程，直至T中除根結(jié)點以外的所有內(nèi)點均成為基本有序樹Ti(i=1,2,…,k)的根結(jié)點為止.

由以上可得一個由k+1個基本有序樹所構(gòu)成的頂點數(shù)為n+1的森林Fk+1.

其次，以集合B中的一個森林Fk+1構(gòu)造A中的一個有序樹T.

3)重復(fù)以上過程，直至森林Fk+1變?yōu)橐粋€標(biāo)號有序樹.

由以上可證，集合A與B之間存在一個雙射.

從上述的雙射構(gòu)造過程可知，在有序樹T中若有p個外層內(nèi)點，則在森林Fk+1中恰有每個根結(jié)點的度不小于正整數(shù)m的p個基本有序樹，且其葉子點均為非星號點，而其余內(nèi)層內(nèi)點所對應(yīng)的基本有序樹的葉子點中至少含有1個星號點.

定理2設(shè)頂點數(shù)為n+1-k的非標(biāo)號有序樹含有k+1個內(nèi)點和p個外層內(nèi)點，且外層內(nèi)點的度不小于正整數(shù)m， 則滿足條件的非標(biāo)號有序樹的個數(shù)為

證明當(dāng)k=0時，根結(jié)點外的所有頂點均為葉子點，此時顯然只有一個基本無序樹.當(dāng)k≥1時，由定理1知，所求標(biāo)號有序樹T的個數(shù)與頂點數(shù)為n+1的森林Fk+1的個數(shù)相等，其中Fk+1中恰含有p個度不小于正整數(shù)m且其葉子點均為非星號點的基本有序樹.因此，若求滿足定理條件的標(biāo)號有序樹T的個數(shù)，只需求頂點數(shù)為n+1的森林Fk+1的個數(shù)即可.

再次，將k個星號點進行排列后分給剩余的k+1-p個基本有序樹的葉子點,然后將n-2k-q個非星號點再進行排列后分給2k+1-p個位置上，其標(biāo)號的方法數(shù)為

由pm≤q≤n-2k可知，標(biāo)號森林Fk+1的個數(shù)為

2 RNA二級結(jié)構(gòu)的計數(shù)

引理1[3]設(shè)在集合{1,2,…,n}上,具有k個堿基對且所有端環(huán)長度不小于正整數(shù)m的RNA二級結(jié)構(gòu)的個數(shù)為Hn(k)， 則有：

下面討論端環(huán)長度不小于正整數(shù)m的RNA二級結(jié)構(gòu)計數(shù)的完全顯示閉公式.

定理3設(shè)在集合{1,2,…,n}上含k個堿基對和p個端環(huán)的RNA二級結(jié)構(gòu)的集合為A， 含有k+1個內(nèi)點、n-2k個葉子點和p個外層內(nèi)點的頂點數(shù)為n+1-k的有序樹的集合為B， 則在A與B之間存在一個雙射.

證明首先，以集合A中的1個RNA二級結(jié)構(gòu)S構(gòu)造集合B中的1個有序樹T.令頂點u為樹T的根.

1)若(i,j)是S的一個堿基對，且其包含的結(jié)構(gòu)為一個分支，則把點i作為u的兒子內(nèi)點；若i為一個外點，則將點i作為u的葉子點，并按S中原來的左右順序進行排列；

2)若i是u的兒子內(nèi)點，則去掉堿基對(i,j)， 并按步驟1)把(i,j)內(nèi)部的所有外點和分支作為頂點i的兒子結(jié)點；

3)重復(fù)步驟2)，直至考慮完所有的堿基對為止.

其次，以集合B中的一個有序樹T構(gòu)造集合A中的一個RNA二級結(jié)構(gòu)S.令T(u)為根結(jié)點u的所有兒子結(jié)點的集合.

1)對?v∈T(u)， 如果v為T中的葉子點，則v在RNA二級結(jié)構(gòu)中對應(yīng)的點就是外點；如果v為內(nèi)點，則v對應(yīng)的點就是RNA中的一個分支，并按照它們原來的左右順序插入到RNA二級結(jié)構(gòu)中；

2)對T(u)中的內(nèi)點p， 將T(p)中的所有點按照步驟1)均插入到(p,q)分支的內(nèi)部；

3)重復(fù)步驟2)，直至考慮完所有的頂點為止.

由以上可證，集合A與B之間存在一個雙射.

由定理3可得RNA二級結(jié)構(gòu)與非標(biāo)號有序樹的對應(yīng)關(guān)系,見表1.由表1和定理2可得定理4.

表1 RNA二級結(jié)構(gòu)與非標(biāo)號有序樹的對應(yīng)關(guān)系

注推論1的結(jié)論就是引理1遞推關(guān)系式的完全顯示閉公式.