離散結構與算法筆記(一)

一弊仪、排列

排列是一個很重要的對象循帐,在代數(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,考慮兩種情況:

  1. \pi_L中的元素均比\pi_R中的小(有一者為空的情況其實也包含在內(nèi)),那么二者至少一者中含有231-pattern,則s(\pi_L)s(\pi_R)中至少有一個不是遞增排列,那么s(\pi_L)s(\pi_R)n不是遞增排列,可得結論成立.
  2. \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}),不過我們這里不予證明.

uS_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張牌分成一些"堆":每次取一張牌,可以

  1. 放到已有的堆的上方,但要求該張牌必須小于要放置的堆的最上面的牌.
  2. 放到所有的堆的右側(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ù)分拆我們在離散結構與算法筆記(三)中有具體定義煤痕,這里不再贅述。

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

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

稱滿足以上填充為形狀為\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
  • 文/蒼蘭香墨 我猛地睜開眼雏逾,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了郑临?” 一聲冷哼從身側(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
  • 正文 年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

推薦閱讀更多精彩內(nèi)容