觀前提示：本文并不含任何多項(xiàng)式內(nèi)容。

本文疑似要成科普文章了。

圖計(jì)數(shù)

有向有標(biāo)號(hào)有向圖數(shù)量：\(2^{n \choose 2}\)。后面叫做 \(g(n)\)

證明：顯然。

有向有標(biāo)號(hào)連通圖數(shù)量：設(shè)答案叫做 \(f(n)\)

方法一：

考慮容斥，枚舉點(diǎn) \(1\) 所在的連通塊大小。

就是 \(f(n)=g(n)-\sum\limits_{i=1}^{n-1} {{n-1} \choose {i-1}} g(i) g(n-i)\)

復(fù)雜度 \(O(n^2)\)

方法二： 考慮 GF，嘟嘟嘟。

這個(gè)東西好像是 Exp 的組合意義。

P6596

非常好題目，讓我容斥旋轉(zhuǎn)。

有向有標(biāo)號(hào)有向圖數(shù)量：\(2^{n \choose 2}\)。后面叫做 \(g(n)\)

證明：顯然。

有向有標(biāo)號(hào)連通圖數(shù)量：設(shè)答案叫做 \(f(n)\)

考慮容斥，枚舉點(diǎn) \(1\) 所在的連通塊大小。

就是 \(f(n)=g(n)-\sum\limits_{i=1}^{n-1} {{n-1} \choose {i-1}} g(i) g(n-i)\)

復(fù)雜度 \(O(n^2)\)

一個(gè)結(jié)論：一個(gè) \(n\) 個(gè)點(diǎn) \(m\) 條邊的帶標(biāo)號(hào)無向圖有 \(k\) 個(gè)連通塊。我們希望添加 \(k-1\) 條邊使得整個(gè)圖連通，求方案數(shù)。

答案是 \(n^{k-2} \prod s_{i}\)， 其中 \(s_i\) 是每個(gè)連通塊的數(shù)量。

證明見OI-wiki。

意思就是說：我們只是關(guān)心后面的那一坨。考慮 dp，設(shè) \(H_{i,j}\) 表示有 \(i\) 個(gè)點(diǎn)，\(j\) 條割邊，后面的東西的乘積。還是要考慮枚舉連通塊 \(H_{i,j}=\sum\limits_{k=1}^{i-1} H_{i-k,j-1} \times H_{k,0}\)。 注意下這里因?yàn)槲覀儧]有欽定邊雙的順序，最后的時(shí)候要除以一個(gè)\((j+1)!\)。

那我們的邊界條件怎們做啊！！

實(shí)際上很簡(jiǎn)單，只需要用 \(g(n)\) 減去其他的就行了。

此時(shí) \(H_{i,0}= \texttt{邊雙連通圖} \times i\)

緊急加更 LGV 引理

點(diǎn)雙連通計(jì)數(shù)

無向圖三元環(huán)計(jì)數(shù)

樹計(jì)數(shù)

Prufer

一棵有標(biāo)號(hào)無根的樹與 一個(gè) \(n-2\) 的排列構(gòu)成雙射。

然后就沒了。

擴(kuò)展結(jié)論：一個(gè) \(n\) 個(gè)點(diǎn) \(m\) 條邊的帶標(biāo)號(hào)無向圖有 \(k\) 個(gè)連通塊。我們希望添加 \(k-1\) 條邊使得整個(gè)圖連通，求方案數(shù)。

答案是 \(n^{k-2} \prod s_{i}\)， 其中 \(s_i\) 是每個(gè)連通塊的數(shù)量。

Matrix Tree

楊表

寫不動(dòng)題目，只能來看論文了/ll。

速通的。

楊圖

每一行（或者是列） 單調(diào)遞減。

我們用整數(shù)分拆的符號(hào) \(\lambda\) 表示 楊圖。

下面是一個(gè) \(\lambda =(5,4,1)\) 的楊圖。

臂長(zhǎng)，腿長(zhǎng)，鉤長(zhǎng)

臂長(zhǎng)：?jiǎn)卧裼疫叺膯卧駭?shù)，記作 $ a_\lambda(x,y)$。

腿長(zhǎng)：?jiǎn)卧裣逻叺膯卧駭?shù)，記作 $ l_\lambda(x,y)$。

鉤長(zhǎng)：上面兩個(gè)加起來，加上本身。記作 $ h_\lambda(x,y)$。

顯然 \(h_\lambda(x,y)=a_\lambda(x,y)+l_\lambda(x,y)+1\)

楊表

在楊圖中填上集合內(nèi)的元素。一般是數(shù)字。

標(biāo)準(zhǔn)楊表是滿足每列數(shù)字嚴(yán)格遞增、每行數(shù)字嚴(yán)格遞增的楊表。

半標(biāo)準(zhǔn)楊表是滿足每列數(shù)字嚴(yán)格遞增、每行數(shù)字非嚴(yán)格遞增的楊表。

標(biāo)準(zhǔn)楊表的 RSK 算法

Aim：將一個(gè)數(shù) \(k\) 插入一個(gè)標(biāo)準(zhǔn)楊表。

• 移動(dòng)至第一行。
• 遍歷，從左往右找到一個(gè) \(> k\) 的數(shù) \(x\)。
• 如果沒有，放在最后一個(gè)，否則交換兩個(gè)數(shù)。
• 繼續(xù)執(zhí)行第二個(gè)操作。

正確性顯然。

其實(shí)并不。

楊表的性質(zhì)

直接開始賀了，不演了

LIS：最長(zhǎng)上升子序列，LDS：最長(zhǎng)下降子序列。

將排列\(P_{1},P_{2} \dots P_{n}\)按 RSK 算法依次插入得到楊表 \(S\)，有性質(zhì)：

• 第一行長(zhǎng)度 \(S_1\)為排列的 LIS 長(zhǎng)度（內(nèi)容不一定）。
• 第一列長(zhǎng)度為排列的 LDS 長(zhǎng)度（內(nèi)容不一定）。
• 若將排列 \(P_{n},P_{n-1} \dots P_{1}\) 插入楊表 \(S'\)，則 \(S′\) 是 \(S\) 交換行列得到。

感性理解不難。

鉤長(zhǎng)公式

沒有證明哦。

對(duì)于一個(gè)楊圖 \(\lambda\)，填入一個(gè) \(\left[1,n\right]\) 的排列，設(shè) \(D_\lambda\) 表示合法的標(biāo)準(zhǔn)楊表數(shù)，我們有：

Robinson–Schensted correspondence

和拆分?jǐn)?shù)有映射關(guān)系。

實(shí)際上，和排列是雙射的。

其中\(P_{n}\) 是和為 \(n\) 的拆分?jǐn)?shù)形成的集合。

注意有一個(gè)關(guān)鍵近似 $ |P_{n}| \sim \frac{1}{4\sqrt{3}n} e^{\sqrt{\frac{2n}{3}} \pi}$

抽象。

楊表和LGV引理有一點(diǎn)相同之處。