一弊仪、排列
排列是一個很重要的對象循帐,在代數(shù)表示論特愿、拓撲中的上同調(diào)响委、幾何中的計數(shù)幾何以及組合中都有重要的應用堕油。
先規(guī)定一下記號仙蛉,使用來表示二項式系數(shù)茅坛。
1.1 概念及其基本性質(zhì)
1.1.1 排列常用的表示方式
記酱畅,
上的一個排列指的是將這些數(shù)按順序排成一列
.
表示
元集合的排列組成的集合案怯,
.
從映射的角度君旦,可以將排列視作一個元集合到自己的雙射,將一種排列方式視為一種雙射.
還可以用矩陣(每行每列有一個
的方陣)的角度來看這個問題,稱為排列矩陣.
矩陣的
個元素為1.
雙隨機矩陣:
滿足 1)
為非負實數(shù); 2)每行每列的元素之和為1.
每個雙隨機矩陣可以視為
中的一個點.
一個經(jīng)典的結論是:所有雙隨機矩陣構成
上的一個凸多面體,其頂點恰為所有的
排列矩陣.
排列的圈表示(圈分解),這里學過抽象代數(shù)的話,就可以理解:中的元素都可以分解為輪換的乘積.一個圈就是一個輪換,顯然這個圈是有序(順逆時針)的圈.
定義(第一類Stirling數(shù)) 中具有
個圈的排列的個數(shù)稱為(無符號)的第一類Stirling數(shù),記做
.即
由定義即可得到.
為了更好地理解,我們采用生成函數(shù)的方法:
不嚴格地說, 我們可以把生成函數(shù)看作表示計數(shù)函數(shù)
的 “載體”.通常這個載體是形式冪級數(shù).其中最常見的兩類生成函數(shù)是一般生成函數(shù)和指數(shù)生成函數(shù).——Stanley《計數(shù)組合學》
定理 以下公式成立
為證明該公式,我們引入以下的引理:
引理 滿足以下的遞歸關系:
證明思路 要生成
個元素且有
個圈的排列,可以考慮從
個元素的排列出發(fā).一是在有
個圈的排列中插入一個單一的元素構成的圈
,這時就構成了一個
個元素且有
個圈的排列.二是在有
個圈的排列中插入一個元素金砍,這個元素可以插入
個位置.綜合這二者來看,就得到了
.
定理證明 只需要把的系數(shù)設出來,驗證其是否滿足和
一樣的遞推關系即可.
即.再代入首項即可得知
注:這是一個很典型的組合的證明方法,用到的主要工具是建立雙射,這門課后面的幾乎所有的證明都是在一定程度上尋找到合適的雙射.
1.1.2 逆序數(shù)
高等代數(shù)中定義行列式的值時使用了逆序數(shù),基本的含義是一個排列中,每個數(shù)后面比這個數(shù)要大的數(shù)的個數(shù)的和.
定義(逆序數(shù)) 令.則
的一個逆序(對)定義為:
且
.
的所有逆序的個數(shù)稱為
的逆序數(shù),記為
.
下面研究的生成函數(shù):
這個生成函數(shù)好像和別的有所不同,可能是因為排列之間沒法定義一個很好地順序關系,所以將其放在指數(shù)上進行處理.
注:由于歷史原因,常用來代替
使用.
定理 對,記
.則
證明 正如我們前面說明的那樣,我們這里建立一個等式兩邊的簡易的表示之間的雙射,從而證明這個定理.
記
容易得到(只需要考慮每一項怎么進行相乘的):
接下來的工作就是建立這個與我們需要的
之間一個滿足要求的雙射.
其中
是以
開頭的逆序?qū)Φ膫€數(shù),即
.
那么.
之后的建立雙射也是顯然的,給定義一串數(shù),你可以通過它的逆序數(shù)來唯一確定這個排列的模樣.(這里可以通過一個計算的算法來說明,鑒于時間原因,這里暫不敘述,有空的時候可以想一個計算的程序.)
拓展:主指標
的主指標定義為:
.一個關鍵的定理是:主指標生成函數(shù)滿足
.換句話說,主指標和逆序數(shù)這兩個統(tǒng)計量在
上式等分布的(
).\
1.1.3 排列的群結構
在抽象代數(shù)中,我們知道排列構成的集合在復合下構成一個群,稱為"對稱群"
這個群也是"A型Lie代數(shù)對應的Weyl group".
群就是在一個非空集合上定義了一種運算,這種運算滿足結合律,而且集合中有一個單位元,這個運算下,每個元素都有逆元.(抽象代數(shù)中已經(jīng)學過,此處不再贅述.)
在中,這個運算:令
,那么
容易驗證這是一個滿足群的定義的運算.
1.1.4 重集上的排列
我們經(jīng)常需要研究含有多個重復元素的排列個數(shù),這時候就需要研究一下重集上的排列.
允許元素重復的集合稱為重集,我們這里研究的重集可以表示為
其中
表示
出現(xiàn)的次數(shù).
定理 重集上的排列個數(shù)為
證明 先將所有元素視為不同得到(m_1+m_2+\cdots+m_n)!,之后只需要除以重復的個數(shù)即可得到.
類似普通排列,可以定義重集排列的逆序數(shù),和之前定義的逆序數(shù)完全相同.
類似上面關于逆序數(shù)的生成函數(shù)的定理,我們這里也有:
定理 重集上的排列的逆序數(shù)的生成函數(shù)滿足以下公式:
這里
取遍所有排列.
證明 有空了再寫.
1.2 排序算法
一般來講,排序算法指的是將字符按照一定順序重新排列.
漢諾塔(Tower of Hanoi)局蚀,又稱河內(nèi)塔,是一個源于印度古老傳說的益智玩具恕稠。大梵天創(chuàng)造世界的時候做了三根金剛石柱子琅绅,在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上谱俭。并且規(guī)定奉件,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤昆著。
用遞歸的方法計算一下便可知,移動個圓盤至少需要
次.
1.2.1 堆棧排列
給定一個排列,一個"棧"指的是將一個排列按照一定算法轉(zhuǎn)化為新的排列.
第一步:將
第二步:取
繼續(xù)重復這個操作,到最后一步時,如果棧內(nèi)還有好多個元素,那么就將這些元素從上至下一個一個輸出.
經(jīng)過堆棧排序后可以得到一個新的排列
任何時候棧內(nèi)的排列都是上面小下面大的.
下面我們關心一個問題:什么時候
定義 如果滿足
,那么就稱
是可堆棧排序的.
定理 是可堆棧排序的
不包含
.也就是說,不存在三個元素同時滿足以下兩個條件 1)a<b<c; 2)b在a前面,a在c前面.
先證明一條結構性的引理:
引理 如果可以記為
,那么
.
證明 這是顯然的.在之前的元素先進入棧中進行排列轉(zhuǎn)化為
.
進入之后,這些元素全部從棧中輸出出來.之后
進入,
后面的元素在
上面的椣孛玻空間進行排列得到
,那么輸出后即為
.
下面我們來證明上面這個定理
證明 ()要證明若
,那么
不包含
考慮它的逆否命題即可. 使用歸納法,設排列元素個數(shù)
時結論成立,那么考慮有
個元素的排列.將
分解為
,考慮兩種情況:
-
中的元素均比
中的小(有一者為空的情況其實也包含在內(nèi)),那么二者至少一者中含有
,則
和
中至少有一個不是遞增排列,那么
不是遞增排列,可得結論成立.
-
中的某個元素比
中的某個元素大,那么
中有元素比
中的元素大,所以
不是遞增排列.結論成立.
()如果
不包含
,那么
形成的排列是遞增排列.類似上面的歸納法,這個是顯然的.
接下來考慮中不包含
的排列的個數(shù):
定理 令
,當
時,
證明 我們?nèi)匀皇褂蒙厦娴慕Y構引理. ,那么
中沒有
,且
中的元素分別為
,由此可得所求公式.
即為大名鼎鼎的Catalan數(shù)(
),不過我們這里不予證明.
令
是
中的任一元素,一個經(jīng)典的結論是
的值為
,與
無關.
1.2.2 耐心排序
撲克牌游戲:取一副撲克牌,標號為,經(jīng)過一定的洗牌之后隨機得到一個排列,自上而下記做
.按如下規(guī)則將
中的
張牌分成一些"堆":每次取一張牌,可以
- 放到已有的堆的上方,但要求該張牌必須小于要放置的堆的最上面的牌.
- 放到所有的堆的右側(cè),形成一個新的堆.
目標:取完張牌后,盡可能形成堆的數(shù)目最少.
對任意的序列,能否找到一個算法使得堆的數(shù)目最少?
耐心排序給出一個答案."貪婪"策略:當一張牌可以放在已存在的堆的上方時,選取最左側(cè)可以放置的堆.
定理 耐心排序形成的堆的數(shù)目最小.
堆的數(shù)目和排列的"遞增子列"密切相關.定義排列()的子列是:
,且
.
遞增子列指的是子列是遞增的.令為
的最長遞增子列長度.
引理 任意合法策略下形成的堆的數(shù)目.
證明 考慮這個最長的遞增序列,那么這里面的每個元素都不在一個堆中,否則就會有一個堆中上面的元素大于下面的元素的情況,與堆的定義矛盾.故至少有個堆.
引理 耐心排序形成的堆的個數(shù)恰好為.
證明 由耐心排序定義可得,每個時刻,所有的堆的最上面的元素滿足從左到右逐次遞增的關系,因為這樣的話才滿足每個元素都放在可以放的最左邊的堆.假設形成了個堆,在這個情況下設第
個堆的最上面的元素為
.考察
的前
個元素放置完之后形成的堆.令第
個堆的頂部元素為
,則
.繼續(xù)對
繼續(xù)這個操作,可以得到
,以此類推,即可得到一個遞增子列:
.因此,
結合上一個引理可得
1.3 Robinson-Schensted算法
Robinson-Schensted算法建立了排列和楊表之間的對應關系。
1.3.1 楊表
楊表是在楊圖中填充數(shù)字得到的凑懂。楊圖以及整數(shù)分拆我們在離散結構與算法筆記(三)中有具體定義煤痕,這里不再贅述。
定義(楊表) 令是
的一個分拆.將
個不同的正整數(shù)填充到
對應的楊圖中使得:
- 每行元素從左到右遞增;
- 每列元素從上到下遞增;
稱滿足以上填充為形狀為的一個楊表.
楊表在代數(shù)組合論接谨、不變量理論摆碉、表示論中有著重要的作用.
NOTE:如果填充的數(shù)字為那么稱其為一個標準楊表;形狀為
的標準楊表個數(shù)記為
.
問題在于