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

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

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

3、號(hào)規(guī)則與最近標(biāo)號(hào)規(guī)則。我們可以利用這些標(biāo)號(hào)規(guī)則來(lái)研究多種帶限制的集合分拆的計(jì)數(shù)等問(wèn)題。作為這些標(biāo)號(hào)規(guī)則的一個(gè)應(yīng)用，我們還給出了集合[n]上二正則不嵌套分拆(避免abba的二正則分拆)和長(zhǎng)為n-2的2-Mozkin路之間的對(duì)應(yīng)。 接下來(lái)我們開(kāi)始研究3不交匹配和3不交分拆。關(guān)于3不交匹配的計(jì)數(shù)是近兩年由Klazar提出的問(wèn)題.該問(wèn)題的更廣義的形式是關(guān)于k不交分拆的計(jì)數(shù)。我們?cè)诒疚闹兄赋鲇腥惤归L(zhǎng)度為6的子序列的[2n]上的有禁匹配

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

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