臺灣國際科展

無孤力點無交錯分割的區塊細分及五個新的Riordan組合結構

科展類別
臺灣國際科展
屆次
2003年
科別
數學科
學校名稱
臺北市立建國高級中學
指導老師
游森棚
作者
侯昆邦、洪仕安
備註
新加坡第廿六屆青年科學節

摘要或動機

將一個集合{1,2,...,n}分成數個非空的集合(組,區塊),稱為此集合的一個分割。如果可以找到1 ≦ a < b < c < d ≦ n,且a,c在同一組(或稱為區塊),b,d
在另外一組,則稱這兩組有交錯。如果任一組的元素個數都至少是2 ,則稱這個分割是無孤立點的。無交錯的分割在許多領域(RNA 模型,組合計數,資訊科學)上都是個重要的問題。


已知無孤立點無交錯分割以Riordan 數{rn}n≥0 =1,0,1,1,3,6,15,36,... 來計數。在這篇文章中我們研究無孤立點無交錯分割的一些性質。



首先我們考慮無孤立點的無交錯分割按區塊的細分。我們得出:集合{1,2,...,n}恰含k個區塊的無孤立點的無交錯分割的個數為:數學公式

其次,我們證明bn,k和多邊形的剖分有令人訝異的關連。令dn,k是用不相交對角線將凸n 邊形分成k 塊的方法。我們用代數方法證出
bn,k = dn+2−k ,k,也給了一個新的組合證明。

最後,透過對應的方法,我們找出了七個嶄新的組合結構,這些結構都是以Riordan 數來計數。


Partition the set {1,2,...,n} into several nonempty sets (blocks) and call it a
partition. If there exists 1 ≦ a < b < c < d ≦ n such that a,c are in the
same block and b,d are in the same block, then this parition is crossing. If the
number of elements in each block is greater than 1, then this partition is nonsingleton.
Noncrossing partitions play an important role in many fields (such as RNA decoding,
enumerative combinatorics, computer science, etc.)

It is known that the nonsingleton noncrossing partitions are counted by Riordan
numbers {rn}n≥0 =1,0,1,1,3,6,15,36,... In this paper we study
the properties of them.


First we consider the enumeration of nonsingleton noncrossing partitions in respect
to the blocks. We prove that the number of nonsingleton noncrossing partitions of
{1,2,...,n} with k blocks is
數學公式

Then we give a connection between nonsingleton noncrossing partitions and polygon
dissections. Let dn,k be the ways to dissect an n –gon with noncrossing
diagonals. We prove that bn,k = dn+2−k ,k


We also give a combinatorial proof. Furthermore, by way of the technic of bijection,
we find 7 new combinatorial structures counted by Riordan numbers.



「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
無孤力點無交錯分割的區塊細分及五個新的Riordan組合結構 805 KB Adobe Reader(Pdf)檔案