從不定方程的非負整數解個數談起

2021 年 5 月 1 日
筆記
OI, 學習筆記

序

求將 \(n\) 個無標號元素用 \(m-1\) 個隔板分入 \(m\) 個有標號可空集合的方案數。

或

求不定方程

\[x_1 + x_2 + \dots + x_m = n \quad (m,n \in N_+, m \le n)
\]

的非負整數解的個數。

是一個非常經典的組合問題，眾所周知其答案為組合數 \({n+m-1 \choose m-1}\) ，這可以根據其組合意義結合隔板法容易的得到。

然而，筆者發現還有很多有趣的方法可以得到上式，值得探討一番。

組合意義

如上文所說，組合意義可以結合隔板法容易的得到。考慮將 \(n\) 個無標號元素用 \(m-1\) 個隔板分入 \(m\) 個有標號非空集合，其方案數為 \({n-1 \choose m-1}\) 。然而我們需要的是各集合可空情況下的方案數。考慮新增 \(m\) 個元素，先給每個集合放一個元素墊底，再做各組可空的分配。這個小Trick讓我們將問題轉化為求 \(n+m\) 個無標號元素分入 \(m\) 個非空有標號集合的方案數。再用隔板法，得到答案 \({n+m-1 \choose m-1}\) 。

形式化的，我們令 \(y_i = x_i + 1\) ，則我們現在只需求 \(y_1 + y_2 + \dots + y_m = n + m\) 的正整數解，隔板法得到答案 \({n+m-1 \choose m-1}\) 。

枚舉空位——范德蒙德卷積公式

我們使用另一種方法將隔板法應用到可空集合上。

枚舉 \(m\) 個集合中有幾個是空集，可以得到下式

\[\mathrm{ans} = \sum_{k=0}^{m-1} {m \choose k} {n-1 \choose m-k-1}
\]

又由范德蒙德卷積公式

\[{n+m \choose k} = \sum_{i=\max(0,k-m)}^{\min(n,k)} {n \choose i} {m \choose k-i}
\]

（范德蒙德卷積公式易由 \((1+x)^{n+m} = (1+x)^n (1+ x)^m\) 的二項式展開說明）

可直接得到（ \(k’ = m-1\) ， \(n’ = m\) ， \(m’ = n-1\) ）

\[\mathrm{ans} = \sum_{k=\max(0,(m-1)-(n-1))}^{\min(m,m-1)} {m \choose k} {n-1 \choose m-k-1} = {n+m-1 \choose m-1}
\]

遞推——楊輝三角

這固然很妙，但要是我想不到這些Trick怎麼辦？

不會通項就設狀態dp唄（~~反正是OIer有電腦幫我算~~

設狀態 \(f(n,m)\) 表示將 \(n\) 個無標號元素放入 \(m\) 個有標號可空集合的方案數。

考慮當前正在為第 \(n\) 個元素確定所屬集合。既然元素是無標號的，不妨按升序排列集合。於是放入新的元素時，只需決定要先跳過多少個集合再放入。易得下面的遞推式

\[f(n,m) = \sum_{k=1}^m f(n-1,k)
\]

初始狀態滿足

\[\begin{aligned}
&f(0,m)=1 \\
&f(n,0)=[n=0]
\end{aligned}
\quad (n,m \in N)
\]

（中括弧是艾弗森括弧）

不妨列出 \(f\) 的前幾項——

n\m	m0	m1	m2	m3	m4
n0	1	1	1	1	1
n1	0	1	2	3	4
n2	0	1	3	6	10
n3	0	1	4	10	20

很熟悉…這是楊輝三角！

可以由遞推式得到楊輝三角的特徵——

\[\begin{aligned}
f(n,m) &= f(n-1, m) + \sum_{k=1}^{m-1} f(n-1,k) \\
&= f(n-1, m) + f(n, m-1)
\end{aligned}
\]

那麼，只需觀察並將表格的每一項映射到楊輝三角，我們就能得到 \(f(n,m) = {n+m+1 \choose m-1}\) 。

生成函數——廣義二項式定理

~~要是我連楊輝三角都沒看出來怎麼辦~~

方便起見，此處我們不研究 \(m=0\) 的情況。不妨設

\[g(n,m) = f(n,m+1)
\]

顯然， \(g\) 的遞推式為

\[g(n,m) = \sum_{k=0}^m g(n-1,k)
\]

據此我們發現，每一排是其前一排的前綴和數組，或者換句話說，每一排是其後一排的向前差分數組。我們先拿出 \(n=0\) 一排的OGF

\[g_0(x) = \frac{1}{1-x}
\]

又根據差分

\[g_n(x) = g_{n+1}(x) – x g_{n+1}(x) \iff g_{n+1} = \frac{1}{1-x} g_n(x)
\]

得

\[g_n(x) = (1-x)^{-(n+1)}
\]

又由廣義二項式定理

\[(x+y)^\alpha = \sum_{k=0}^{\infty} {\alpha \choose k} x^k y^{\alpha – k}
\]

其中

\[{\alpha \choose k} = \frac{\alpha(\alpha-1)\dots(\alpha-k+1)}{k!}\\
\]

展開，得到

\[g_n(x) = \sum_{k=0}^{\infty} {-n-1 \choose k} (-1)^k x^k
\]

故

\[\begin{aligned}
g_n(x)[x^k] &= (-1)^k {-n-1 \choose k} \\
&= (-1)^k \frac{(-n-1)(-n-2)\dots(-n-k)}{k!} \\
&= \frac{(n+1)(n+2)\dots(n+k)}{k!} \\
&= {n+k \choose k}
\end{aligned}
\]

即

\[g(n,k) = {n+k \choose k}
\]

換回 \(f\) 表示就得到答案

\[f(n,m) = g(n,m-1) = {n+m-1 \choose m-1}
\]

Burnside——第一類斯特林數

如果要分組的 \(n\) 個元素是有標號的，問題將會簡單很多——直接枚舉每個元素的所屬集合即可，顯然方案數為 \(m^n\) 。

但關鍵是它們沒有標號。

無標號的本質是認為任意置換標號前後是同構的。這啟發我們將所有 \(n\) 元置換（即置換群）作為變換集，使用等價類計數Burnside來解決該問題。

根據Burnside定理

\[\mathrm{ans} = \frac{1}{|G|} \sum_{f \in G} C(f)
\]

其中 \(G\) 是變換集， \(C(f)\) 是變換 \(f\) 的不動點。

可以寫出

\[\mathrm{ans} = \frac{1}{n!} \sum_{p \in \mathrm{perm}(n)} m^{\mathrm{cyc}(p)}
\]

其中 \(\mathrm{perm}(n)\) 表示所有 \(n\) 元置換的集合，而 \(\mathrm{cyc}(p)\) 指置換 \(p\) 的形成的置換圖中環的個數。

在外層枚舉 \(\mathrm{cyc}(p)\) ，得

\[\mathrm{ans} = \frac{1}{n!} \sum_{k=1}^n m^k \sum_{p \in \mathrm{perm}(n)} [\mathrm{cyc}(p) = k]
\]

\(\sum_{p \in \mathrm{perm}(n)} [\mathrm{cyc}(p) = k]\) 是什麼？

第一類斯特林數 \({n \brack k}\) 表示將 \(n\) 個有標號元素分成 \(k\) 個無標號圓排列的方案數。

在置換圖中， \(p_i\) 表示節點 \(i\) 的下一個節點是 \(p_i\) 。而枚舉置換的過程，正是枚舉置換圖的過程，也正是枚舉圓排列的過程！而 \([\mathrm{cyc}(p) = k]\) 則為我們確定了環，或者說圓排列的個數。

驚訝的，我們發現

\[{n \brack k} = \sum_{p \in \mathrm{perm}(n)} [\mathrm{cyc}(p) = k]
\]

帶入其中，答案式變為

\[\mathrm{ans} = \frac{1}{n!} \sum_{k=1}^n {n \brack k} m^k
\]

於是，根據第一類斯特林數性質之一

\[\sum_{k=1}^n {n \brack k} m^k = m(m+1)\dots(n+m-1)
\]

我們愉快的得到了答案

\[\mathrm{ans} = \frac{m(m+1)\dots(n+m-1)}{n!} = {n+m-1 \choose m-1}
\]

用Burnside解決無標號問題的思路極具啟發性，例如烷基計數問題的Burnside解法。

後記&致謝

~~同分異構體計數帶我重回OI~~

感謝TbYangZ菊苣全程提供技術支援。

感謝神仙化學老師提供組合意義解釋。

2021/05/01

Tags: OI 學習筆記