Enumeration on Set Partitions and（k,m）-ary Trees.pdf

1、本文主要研究了幾類帶限制的集合分拆以及(k，m)-叉樹的計數(shù)。首先我們給出了集合[n]={1，2，…，n}上的m正則分拆的一個約簡算法。該算法將集合[n]上的m正則分拆轉化為集合[n-1]上的(m-1)-正則分拆。我們還證明了分拆的不交性質(zhì)在這種約簡算法下保持不變，從而給出了Simion-Ullman以及Klazar的一個組合恒等式的簡單證明。利用該恒等式我們還給出了一種廣義RNA二級結構的計數(shù)公式。對于一般的不交分拆，利用該算法，我們

2、可以將其轉化為一個只包含單點、獨立邊及自環(huán)的圖，從而得到一個將Narayana數(shù)用Catalan數(shù)表示的恒等式。 然后我們介紹了Dyck路和2-Mozkin路上的標號規(guī)則。對于任意一個3長的排列τ，我們都給出了一種Dyck路上的標號規(guī)則，通過這種標號可以建立長為2n的Dyck路與集合[n]上避免τ的有禁排列之間的雙射。這些雙射還將排列上的一些統(tǒng)計量轉化為Dyck路上的統(tǒng)計量。對于2-Mozkin路，我們給出了兩種標號規(guī)則：最遠標

3、號規(guī)則與最近標號規(guī)則。我們可以利用這些標號規(guī)則來研究多種帶限制的集合分拆的計數(shù)等問題。作為這些標號規(guī)則的一個應用，我們還給出了集合[n]上二正則不嵌套分拆(避免abba的二正則分拆)和長為n-2的2-Mozkin路之間的對應。 接下來我們開始研究3不交匹配和3不交分拆。關于3不交匹配的計數(shù)是近兩年由Klazar提出的問題.該問題的更廣義的形式是關于k不交分拆的計數(shù)。我們在本文中指出有三類禁止長度為6的子序列的[2n]上的有禁匹配

4、均和長為2n的不交Dyck路對的集合之間存在一一對應。這三類有禁匹配分別是3不交匹配(避免123123的匹配)、3不嵌套匹配(避免123321的匹配)以及非雙嵌套匹配(避免123312的匹配)。我們還給出了這三類有禁匹配的計數(shù)公式。 本文中關于集合分拆的最重要的結果是引進了一種新的工具：“猶豫楊表”，并通過它來研究匹配以及分拆上的交叉數(shù)與嵌套數(shù)。利用集合分拆與猶豫楊表之間的一個雙射，我們證明了如果給定分拆的每個塊中的最大和最小元

5、素，這些分拆的交叉數(shù)與嵌套數(shù)有對稱的交集分布。因此對所有的集合[n]上的分拆以及集合[n]=[2m]上的匹配，交叉數(shù)與嵌套數(shù)也是對稱交集分布的。該結論的一個推論就是：k不交分拆(匹配)與k不嵌套分拆(匹配)的個數(shù)相等。 在本文的最后我們定義并研究了(k，m)-Catalan數(shù)Ck,m(n)=1/mn+1(mn+1)kn)，它是傳統(tǒng)意義的Catalan數(shù)C(n)=1/n+1(2nn)的一個推廣。我們還給出了(k，m)-Catala