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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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