離散結構與算法筆記（一）

一弊仪、排列

排列是一個很重要的對象循帐，在代數(shù)表示論特愿、拓撲中的上同調(diào)响委、幾何中的計數(shù)幾何以及組合中都有重要的應用堕油。
先規(guī)定一下記號仙蛉，使用 $\binom{n}{k}$ 來表示二項式系數(shù)茅坛。

1.1 概念及其基本性質(zhì)

1.1.1 排列常用的表示方式

記 $S=\{1,2,3,\dots,n\}$ 酱畅， $S$ 上的一個排列指的是將這些數(shù)按順序排成一列 $\pi=\pi_1\pi_2\dots \pi_n$ . $S_n$ 表示 $n$ 元集合的排列組成的集合案怯， $|S_n|=n!$ .

從映射的角度君旦，可以將排列視作一個 $n$ 元集合到自己的雙射，將一種排列方式視為一種雙射.

還可以用 $0/1$ 矩陣(每行每列有一個 $1$ 的方陣)的角度來看這個問題，稱為排列矩陣. $\pi_1\pi_2\dots\pi_n\leftrightarrow$ $n\times n$ 矩陣的 $a_{i,\pi_i}$ 個元素為1.

雙隨機矩陣: $M=(m_{ij})_{n\times n}$ 滿足 1) $m_{ij}$ 為非負實數(shù); 2)每行每列的元素之和為1.
每個 $n\times n$ 雙隨機矩陣可以視為 $\mathbb{R}^{n^2}$ 中的一個點.
一個經(jīng)典的結論是:所有 $n\times n$ 雙隨機矩陣構成 $\mathbb{R}^{n^2}$ 上的一個凸多面體,其頂點恰為所有的 $n\times n$ 排列矩陣.

排列的圈表示(圈分解),這里學過抽象代數(shù)的話,就可以理解: $S_n$ 中的元素都可以分解為輪換的乘積.一個圈就是一個輪換,顯然這個圈是有序(順逆時針)的圈.

定義(第一類Stirling數(shù)) $S_n$ 中具有 $k$ 個圈的排列的個數(shù)稱為(無符號)的第一類Stirling數(shù),記做 $c(n,k)$ .即
$c(n,k)=|\{\pi\in S_n|\pi的圈表示恰有k個圈\}|$

由定義即可得到 $\sum_{i=0}^nc(n,k)=n!$ .

為了更好地理解 $c(n,k)$ ,我們采用生成函數(shù)的方法:
$\sum_{k=1}^nc(n,k)x^k$

不嚴格地說, 我們可以把生成函數(shù)看作表示計數(shù)函數(shù) $f(i)$ 的 “載體”.通常這個載體是形式冪級數(shù).其中最常見的兩類生成函數(shù)是一般生成函數(shù)和指數(shù)生成函數(shù).——Stanley《計數(shù)組合學》

定理以下公式成立
$\sum_{i=1}^n c(n,k)x^k=x(x+1)(x+2)\cdots (x+n-1)$

為證明該公式,我們引入以下的引理:
引理 $c(n,k)$ 滿足以下的遞歸關系:
$c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$ 證明思路 要生成 $n$ 個元素且有 $k$ 個圈的排列,可以考慮從 $n-1$ 個元素的排列出發(fā).一是在有 $k-1$ 個圈的排列中插入一個單一的元素構成的圈 $(n)$ ,這時就構成了一個 $n$ 個元素且有 $k$ 個圈的排列.二是在有 $k$ 個圈的排列中插入一個元素金砍，這個元素可以插入 $n-1$ 個位置.綜合這二者來看,就得到了 $c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$ .

定理證明 只需要把 $F_n(x)=x(x+1)(x+2)\cdots (x+n-1)$ 的系數(shù)設出來,驗證其是否滿足和 $c(n,k)$ 一樣的遞推關系即可.
$F_n(x)=\sum_{k=1}^nb(n,k)x^k=(x+n-1)F_{n-1}(x)= xF_{n-1}(x)$
$+(n-1)F_{n-1}(x)=\sum_{k=1}^{n-1}b(n-1,k)x^{k+1}+(n-1)\sum_{k=1}^{n-1}b(n-1,k)x^k$
即 $b(n,k)=b(n-1,k-1)+(n-1)b(n-1,k)$ .再代入首項即可得知 $b(n,k)=c(n,k)$ $\square$

注:這是一個很典型的組合的證明方法,用到的主要工具是建立雙射,這門課后面的幾乎所有的證明都是在一定程度上尋找到合適的雙射.

1.1.2 逆序數(shù)

高等代數(shù)中定義行列式的值時使用了逆序數(shù),基本的含義是一個排列中,每個數(shù)后面比這個數(shù)要大的數(shù)的個數(shù)的和.

定義(逆序數(shù)) 令 $\pi=\pi_1\pi_2\dots\pi_n\in S_n$ .則 $\pi$ 的一個逆序(對)定義為: $(\pi_i,\pi_j),1\leq i< j \leq n,$ 且 $\pi_i>\pi_j$ . $\pi$ 的所有逆序的個數(shù)稱為 $\pi$ 的逆序數(shù),記為 $inv(\pi)$ .

下面研究 $inv(\pi)$ 的生成函數(shù):
$\sum_{\pi\in S_n}x^{inv(\pi)}=?$

這個生成函數(shù)好像和別的有所不同,可能是因為排列之間沒法定義一個很好地順序關系,所以將其放在指數(shù)上進行處理.
注:由于歷史原因,常用 $q$ 來代替 $x$ 使用.

定理對 $s\geq 1$ ,記 $[k]=1+q+q^2+\cdots+q^{k-1}$ .則
$\sum_{\pi\in S_n}q^{inv(\pi)}=[1]·[2]\cdots[n]=[n]!$
證明正如我們前面說明的那樣,我們這里建立一個等式兩邊的簡易的表示之間的雙射,從而證明這個定理.
記
$I_n=\{(a_1,a_2,\dots,a_n)|0\leq a_i\leq n-i\}$
容易得到(只需要考慮每一項怎么進行相乘的):
$\sum_{(a_1,a_2,\dots,a_n)\in I_n}q^{a_1+a_2+\cdots+a_n}=(\sum_{i=0}^{n-1}q^i)(\sum_{i=0}^{n-2}q^i)\cdots(\sum_{i=0}^{0}q^i)=[n]!$
接下來的工作就是建立這個 $I_n$ 與我們需要的 $S_n$ 之間一個滿足要求的雙射.
$\phi:S_n\rightarrow I_n$ $\pi\rightarrow (a_1,a_2,\dots,a_n)$ 其中 $a_i$ 是以 $i$ 開頭的逆序?qū)Φ膫€數(shù),即 $a_i=|\{j\ |i<j\leq n,\pi_i>\pi_j\}|$ .
那么 $inv(\pi)=a_1+a_2+\cdots+a_n$ .
之后的建立雙射也是顯然的,給定義一串數(shù),你可以通過它的逆序數(shù)來唯一確定這個排列的模樣.(這里可以通過一個計算的算法來說明,鑒于時間原因,這里暫不敘述,有空的時候可以想一個計算的程序.)

拓展:主指標
$\pi=\pi_1\pi_2\dots\pi_n\in S_n$ 的主指標定義為: $maj(\pi)=\sum_{1\leq i<n,\pi_i>\pi_{i+1}}i$ .一個關鍵的定理是:主指標生成函數(shù)滿足 $\sum_{\pi \in S_n}q^{maj(\pi)}=[n]!$ .換句話說,主指標和逆序數(shù)這兩個統(tǒng)計量在 $S_n$ 上式等分布的( $\forall k\in \mathbb{N},|\{\pi\in S_n|maj(\pi)=k\}|=|\{\pi\in S_n|inv(\pi)=k\}|$ ).\

1.1.3 排列的群結構

在抽象代數(shù)中,我們知道排列構成的集合 $S_n$ 在復合下構成一個群,稱為"對稱群"

這個群也是"A型Lie代數(shù)對應的Weyl group".

群就是在一個非空集合上定義了一種運算,這種運算滿足結合律,而且集合中有一個單位元,這個運算下,每個元素都有逆元.(抽象代數(shù)中已經(jīng)學過,此處不再贅述.)

在 $S_n$ 中,這個運算:令 $\pi,\sigma\in S_n$ ,那么
$\pi ·\sigma:i\rightarrow \pi(\sigma(i)),1\leq i\leq n$ 容易驗證這是一個滿足群的定義的運算.

1.1.4 重集上的排列

我們經(jīng)常需要研究含有多個重復元素的排列個數(shù),這時候就需要研究一下重集上的排列.

允許元素重復的集合稱為重集,我們這里研究的重集可以表示為
$\{1^{m_1},2^{m_2},\dots,n^{m_n}\}$ 其中 $m_i$ 表示 $i$ 出現(xiàn)的次數(shù).

定理重集 $\{1^{m_1},2^{m_2},\dots,n^{m_n}\}$ 上的排列個數(shù)為
$\frac{(m_1+m_2+\cdots+m_n)!}{m_1!m_2!\cdots m_n!}$ 證明先將所有元素視為不同得到(m_1+m_2+\cdots+m_n)!,之后只需要除以重復的個數(shù)即可得到. $\square$

類似普通排列,可以定義重集排列的逆序數(shù),和之前定義的逆序數(shù)完全相同.

類似上面關于逆序數(shù)的生成函數(shù)的定理,我們這里也有:
定理重集 $\{1^{m_1},2^{m_2},\dots,n^{m_n}\}$ 上的排列的逆序數(shù)的生成函數(shù)滿足以下公式:
$\sum_{\pi}q^{inv(\pi)}=\frac{[m_1+m_2+\cdots+m_n]!}{[m_1]![m_2]!\cdots [m_n]!}$ 這里 $\pi$ 取遍所有排列.
證明有空了再寫.

1.2 排序算法

一般來講,排序算法指的是將字符按照一定順序重新排列.

漢諾塔（Tower of Hanoi）局蚀，又稱河內(nèi)塔，是一個源于印度古老傳說的益智玩具恕稠。大梵天創(chuàng)造世界的時候做了三根金剛石柱子琅绅，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上谱俭。并且規(guī)定奉件，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤昆著。
用遞歸的方法計算一下便可知,移動 $n$ 個圓盤至少需要 $2^n-1$ 次.

1.2.1 堆棧排列

給定一個排列 $\pi=\pi_1\pi_2\dots \pi_n$ ,一個"棧"指的是將一個排列按照一定算法轉(zhuǎn)化為新的排列.

堆棧排序.PNG

規(guī)則:
第一步:將

\pi_1

放入棧內(nèi)
第二步:取

\pi_2

,如果

\pi_2<\pi_1

,就將

\pi_2

放在

\pi_1

上面;如果

\pi_2>\pi_1

,就將

\pi_1

取出,

\pi_2

放進去(這是一個排列,顯然不會有相同的情況.)
繼續(xù)重復這個操作,到最后一步時,如果棧內(nèi)還有好多個元素,那么就將這些元素從上至下一個一個輸出.
經(jīng)過堆棧排序后可以得到一個新的排列

s(\pi)=\sigma_1\sigma_2\cdots\sigma_n

實例.PNG

任何時候棧內(nèi)的排列都是上面小下面大的.

下面我們關心一個問題:什么時候 $s(\pi)=123\cdots n?$

定義如果 $\pi$ 滿足 $s(\pi)=12\cdots n$ ,那么就稱 $\pi$ 是可堆棧排序的.
定理 $\pi$ 是可堆棧排序的 $\iff$ $\pi$ 不包含 $231-pattern$ .也就是說,不存在三個元素同時滿足以下兩個條件 1)a<b<c; 2)b在a前面,a在c前面.

先證明一條結構性的引理:
引理如果 $\pi$ 可以記為 $\pi_L n \pi_R$ ,那么 $s(\pi)=s(\pi_L)s(\pi_R)n$ .
證明這是顯然的.在 $n$ 之前的元素先進入棧中進行排列轉(zhuǎn)化為 $s(\pi_L)$ . $n$ 進入之后,這些元素全部從棧中輸出出來.之后 $n$ 進入, $n$ 后面的元素在 $n$ 上面的椣孛玻空間進行排列得到 $s(\pi_R)$ ,那么輸出后即為 $s(\pi_L)s(\pi_R)n$ .

下面我們來證明上面這個定理
證明 ( $\Rightarrow$ )要證明若 $s(\pi)=12\cdots n$ ,那么 $\pi$ 不包含 $231-pattern.$ 考慮它的逆否命題即可. 使用歸納法,設排列元素個數(shù) $<n$ 時結論成立,那么考慮有 $n$ 個元素的排列.將 $\pi$ 分解為 $\pi_L n \pi_R$ ,考慮兩種情況:

$\pi_L$ 中的元素均比 $\pi_R$ 中的小(有一者為空的情況其實也包含在內(nèi)),那么二者至少一者中含有 $231-pattern$ ,則 $s(\pi_L)$ 和 $s(\pi_R)$ 中至少有一個不是遞增排列,那么 $s(\pi_L)s(\pi_R)n$ 不是遞增排列,可得結論成立.
$\pi_L$ 中的某個元素比 $\pi_R$ 中的某個元素大,那么 $s(\pi_L)$ 中有元素比 $s(\pi_R)$ 中的元素大,所以 $s(\pi_L)s(\pi_R)n$ 不是遞增排列.結論成立.

( $\Leftarrow$ )如果 $\pi$ 不包含 $231-pattern$ ,那么 $\pi$ 形成的排列是遞增排列.類似上面的歸納法,這個是顯然的.

接下來考慮 $S_n$ 中不包含 $231-pattern$ 的排列的個數(shù):
$c_n=|\{\pi\in S_n|s(\pi)=12\cdots n\}|$ 定理令 $c_0=1$ ,當 $n\geq 1$ 時, $c_n=\sum_{i=1}^nc_{i-1}c_{n-i}.$
證明我們?nèi)匀皇褂蒙厦娴慕Y構引理. $\pi=\pi_L n \pi_R$ ,那么 $\pi_L,\pi_R$ 中沒有 $231-pattern$ ,且 $\pi_L,\pi_R$ 中的元素分別為 $\{1,2,\dots,i\},\{i,i+1,\dots,n-1\}$ ,由此可得所求公式. $\square$

$c_n$ 即為大名鼎鼎的Catalan數(shù)( $c_n=\frac{1}{n+1}\binom{2n}{n}$ ),不過我們這里不予證明.

令 $u$ 是 $S_3$ 中的任一元素,一個經(jīng)典的結論是 $|\{\pi\in S_n|\pi 不包含 pattern u\}|$ 的值為 $c_n$ ,與 $u$ 無關.

1.2.2 耐心排序

撲克牌游戲:取一副撲克牌,標號為 $1,2\dots,n$ ,經(jīng)過一定的洗牌之后隨機得到一個排列,自上而下記做 $\pi=\pi_1\pi_2\dots\pi_n$ .按如下規(guī)則將 $\pi$ 中的 $n$ 張牌分成一些"堆":每次取一張牌,可以

放到已有的堆的上方,但要求該張牌必須小于要放置的堆的最上面的牌.
放到所有的堆的右側(cè),形成一個新的堆.

目標:取完 $n$ 張牌后,盡可能形成堆的數(shù)目最少.

對任意的序列,能否找到一個算法使得堆的數(shù)目最少?

耐心排序給出一個答案."貪婪"策略:當一張牌可以放在已存在的堆的上方時,選取最左側(cè)可以放置的堆.

定理耐心排序形成的堆的數(shù)目最小.

堆的數(shù)目和排列的"遞增子列"密切相關.定義排列( $\pi=\pi_1\pi_2\cdots\pi_n$ )的子列是: $\pi_{i_1}\pi_{i_2}\cdots\pi_{i_k}$ ,且 $i_1<\cdots< i_n$ .
遞增子列指的是子列是遞增的.令 $in(\pi)$ 為 $\pi$ 的最長遞增子列長度.

引理任意合法策略下形成的堆的數(shù)目 $\geq in(\pi)$ .
證明考慮這個最長的遞增序列,那么這里面的每個元素都不在一個堆中,否則就會有一個堆中上面的元素大于下面的元素的情況,與堆的定義矛盾.故至少有 $in(\pi)$ 個堆.

引理耐心排序形成的堆的個數(shù)恰好為 $in(\pi)$ .
證明由耐心排序定義可得,每個時刻,所有的堆的最上面的元素滿足從左到右逐次遞增的關系,因為這樣的話才滿足每個元素都放在可以放的最左邊的堆.假設形成了 $k$ 個堆,在這個情況下設第 $k$ 個堆的最上面的元素為 $\pi_{i_k}$ .考察 $\pi$ 的前 $i_k$ 個元素放置完之后形成的堆.令第 $k-1$ 個堆的頂部元素為 $\pi_{i_{k-1}}$ ,則 $\pi_{i_{k-1}}<\pi_{i_k}$ .繼續(xù)對 $\pi_{i_{k-1}}$ 繼續(xù)這個操作,可以得到 $\pi_{i_{k-2}}$ ,以此類推,即可得到一個遞增子列: $\pi_{i_1}\pi_{i_2}\cdots\pi_{i_k}$ .因此, $k\leq in(\pi).$ 結合上一個引理可得 $k=in(\pi).$

1.3 Robinson-Schensted算法

Robinson-Schensted算法建立了排列和楊表之間的對應關系。

1.3.1 楊表

楊表是在楊圖中填充數(shù)字得到的凑懂。楊圖以及整數(shù)分拆我們在離散結構與算法筆記（三）中有具體定義煤痕，這里不再贅述。

定義(楊表) 令 $\lambda$ 是 $n$ 的一個分拆.將 $k$ 個不同的正整數(shù)填充到 $\lambda$ 對應的楊圖中使得:

每行元素從左到右遞增;
每列元素從上到下遞增;

稱滿足以上填充為形狀為 $\lambda$ 的一個楊表.

楊表在代數(shù)組合論接谨、不變量理論摆碉、表示論中有著重要的作用.

NOTE:如果填充的數(shù)字為 $\{1,2,\dots,n\},$ 那么稱其為一個標準楊表;形狀為 $\lambda$ 的標準楊表個數(shù)記為 $f^{\lambda}$ .

問題在于 $f^\lambda=?$

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市脓豪，隨后出現(xiàn)的幾起案子巷帝，更是在濱河造成了極大的恐慌，老刑警劉巖扫夜，帶你破解...
沈念sama閱讀 222,627評論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件楞泼，死亡現(xiàn)場離奇詭異，居然都是意外死亡笤闯，警方通過查閱死者的電腦和手機堕阔，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,180評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來颗味，“玉大人超陆，你說我怎么就攤上這事∑致恚” “怎么了时呀？”我有些...
開封第一講書人閱讀 169,346評論 0贊 362
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長捐韩。經(jīng)常有香客問我退唠，道長，這世上最難降的妖魔是什么荤胁？我笑而不...
開封第一講書人閱讀 60,097評論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮屎债，結果婚禮上仅政，老公的妹妹穿的比我還像新娘垢油。我一直安慰自己，他們只是感情好圆丹，可當我...
茶點故事閱讀 69,100評論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布滩愁。她就那樣靜靜地躺著，像睡著了一般辫封。火紅的嫁衣襯著肌膚如雪硝枉。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,696評論 1贊 312
城市分裂傳說
那天倦微，我揣著相機與錄音妻味，去河邊找鬼。笑死欣福，一個胖子當著我的面吹牛责球，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播拓劝，決...
沈念sama閱讀 41,165評論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼雏逾，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了郑临？” 一聲冷哼從身側(cè)響起栖博，我...
開封第一講書人閱讀 40,108評論 0贊 277
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎厢洞，沒想到半個月后仇让，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,646評論 1贊 319
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡犀变，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,709評論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年妹孙，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片获枝。...
茶點故事閱讀 40,861評論 1贊 353
活死人
序言：一個原本活蹦亂跳的男人離奇死亡蠢正，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出省店，到底是詐尸還是另有隱情嚣崭，我是刑警寧澤，帶...
沈念sama閱讀 36,527評論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布懦傍，位于F島的核電站雹舀，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏粗俱。R本人自食惡果不足惜说榆，卻給世界環(huán)境...
茶點故事閱讀 42,196評論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧签财，春花似錦串慰、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,698評論 0贊 25
一樁弒父案邦鲫，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至神汹，卻和暖如春庆捺，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背屁魏。一陣腳步聲響...
開封第一講書人閱讀 33,804評論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工滔以，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人蚁堤。一個月前我還...
沈念sama閱讀 49,287評論 3贊 379
代替公主和親
正文我出身青樓醉者，卻偏偏與公主長得像，于是被迫代替她去往敵國和親披诗。傳聞我的和親對象是個殘疾皇子撬即，可洞房花燭夜當晚...
茶點故事閱讀 45,860評論 2贊 361