【组合数学】 02 - Möbius反演公式

  计数问题种类繁多,为了避免陷入漫无目的烧脑运动,我们先需要关注一些常用方法和结论。数学的抽象性和通用性是我们一直推崇的,从诸多特殊问题中发现一般性的方法,也总会让人兴奋和慨叹。一般教材多是以排列组合开篇,采用了一些技巧性很强的初等方法来讨论组合计数,我倒觉得可以直接先掌握一些锋利的工具,到时再看那些问题,会有快刀斩乱麻之快感。

1. 关联代数

1.1 一个例子

  为了对反演公式有个直观的认识,我们从一个简单的问题说起,考察数列的求和公式(1)。左式表示当知道数列的每一项\(a_n\)时,就可以得到前\(n\)项的和\(s_n\),右式表示知道和\(s_n\)也可以反推到项\(a_n\)。整理一下这段陈述中的要素,有两个定义在自然数集上的函数\(f(n),g(n)\),\(f(n)\)可以由\(g(1),\cdots,g(n)\)线性表出,\(g(n)\)也可以由\(f(1),\cdots,f(n)\)线性表出,结论是这两个线性表出是等价的,由其中一个可以推导出另一个。

\[s_n=a_1+a_2+\cdots+a_n\;\Leftrightarrow\;a_n=s_n-s_{n-1}\tag{1}\]

  这样的互逆推导现象被称为反演,现在来深入寻找其中的模式。有了线性代数的知识,以上推导式其实就是一个简单的线性方程组(式(2))。有两点需要强调,一点是由于递推式的特点,两边的矩阵都是下三角可逆矩阵。另一点是,这个表达式对任意的\(n\)都成立,其中的向量和方阵都可以看成是无限维的。第二点让我们把注意力吸引到了方阵上(设两边分别为\(A,B\)),因为不管\(n\)是多少,两边的方阵在\(a_{ij},b_{ij}\)的取值都是相同的!

\[\begin{bmatrix}s_1\\s_2\\\vdots\\s_n\end{bmatrix}=\begin{bmatrix}1&&&\\1&1&&\\\vdots&\vdots&\ddots&\\1&\cdots&1&1\end{bmatrix}\begin{bmatrix}a_1\\a_2\\\vdots\\a_n\end{bmatrix}\;\Leftrightarrow\;\begin{bmatrix}a_1\\a_2\\\vdots\\a_n\end{bmatrix}=\begin{bmatrix}1&&&\\-1&1&&\\&\ddots&\ddots&\\&&-1&1\end{bmatrix}\begin{bmatrix}s_1\\s_2\\\vdots\\s_n\end{bmatrix}\tag{2}\]

1.2 偏序集

  看来我们已经把问题引入到了无限维下三角方阵上来,而讨论的目标则是它的逆元。为了得到这样的扩展,我们用另一种方法来描述下三角方阵。首先它定义在正整数集的二元关系\((x,y)\)上,其次只有当\(x\geqslant y\)时有意义。我们知道正整数集是一个全序集,任意两个数之间都是“可比”的,下三角矩阵就是“可比”关系的函数。既然要扩展定义,我们不妨把这个函数定义在稍弱一点的“序集”上,只需要局部是“可比”的,反演在局部应该也是有意义的。

  具体来说,我们来回顾集合论中的偏序集,定义集合\(X\)的二元关系\(\geqslant\),它满足自反率、反对称性、传递性,并称之为偏序。定义了偏序的集合也称为偏序集(partially ordered set),其中有二元关系的两个元素称为可比的,可比元素之间的所有元素称为截断,记为\([x,y]\)。偏序集可以用Hasse图来直观地表示,图中只连接了直接可比的元素(上大下小),整体看起来呈现网状结构。除了整数集之外,常见的偏序集还有:集合间的包含关系、正整数间的整除关系等。

【组合数学】 02 - Möbius反演公式

  偏序集可以是无限的,但为了便于讨论,我们假定局部是有限的,即\([x,y]\)是有限集。如果把偏序关系全部倒过来,得到的显然还是偏序集,且和原集是同构的,没有本质区别,它们称为对偶的。另外,对于偏序集\(X_1,X_2,\cdots,X_n\),容易知道直积\(X_1\times\cdots\times X_n\)在式(3)定义下也是偏序集。如果记\(n\)元集合的所有子集在包含关系下的偏序集为\(B(n)\),则易知它同构于\(n\)个\(2\)元链\(L_2\)的直积\(L_2^n\)。再记\(n\)之内的整数在整除关系下的偏序集为\(D(n)\),设\(n=p_1^{e_1}\cdots p_k^{e_k}\),则易知它同构于\(L_{e_1+1}\times\cdots\times L_{e_k+1}\)。

\[(x_1,x_2,\cdots,x_n)\geqslant(y_1,y_2,\cdots,y_n)\;\Leftrightarrow\;x_1\geqslant y_1\wedge\cdots\wedge x_n\geqslant y_n\tag{3}\]

1.3 关联代数

  现在在偏序关系\(X\)上定义函数\(\alpha(x,y)\in X\times X\to\Bbb{R}\),当\(x\not\geqslant y\)时\(\alpha(x,y)=0\)。为讨论它们的代数结构,记所有函数的集合为\(I(X)\),在上面定义加法和数乘是平凡的。参考矩阵乘法的定义,可以按式(4)定义函数的乘法\(\alpha\beta\),可以证明乘法满足结合律。在抽象代数中我们知道,这样的结构叫做结合代数,在这里我们称它为偏序集\(X\)的关联代数(incidence algebra),也记作\(I(X)\)。

\[(\alpha\beta)(x,y)=\sum_{x\geqslant z\geqslant y}\alpha(x,z)\beta(z,y)\tag{4}\]

  容易验证以下函数\(\delta\)就是关联代数的单位元,下面讨论关联代数中的逆元。假设\(\beta\alpha=\delta\),固定\(x\)的值,由乘法的定义可有式(6)。如果\(\alpha(x,x)\ne 0\),显然可递推得到任何一个\(\beta(x,y)\),这就得到了\(\alpha\)存在逆元的充要条件:\(\alpha(x,x)\ne 0\)。还可以确定,\(\beta(x,y)\)完全取决于\(z\in[x,y]\)上\(\alpha(z,y)\)的值。另外值得注意的是,逆元\(\beta\)不仅与\(\alpha\)有关,还与偏序集的结构有关。

\[\delta(x,y)=\left\{\begin{matrix}1,&(x=y)\\0,&(x\ne y)\end{matrix}\right.\tag{5}\]

\[\beta(x,x)\alpha(x,x)=1,\;\sum_{x\geqslant z\geqslant y}\beta(x,z)\alpha(z,y)=0\tag{6}\]

  特别地,定义式(7)中的常用函数\(\zeta\)为zeta函数,它的逆\(\mu\)显然存在,被称之为Möbius函数。由式(6)可得到\(\mu\)的递推式(8),它只包含\(0,\pm 1\),具体值与偏序集的结构有关。设偏序集\(X_1,\cdots,X_k\)上有函数\(\delta_i,\zeta_i,\mu_i\),对于它们的直积\(X\),首先显然有式(9)的前两式成立,式(10)的推导和逆元的唯一性也说明了第三式成立。

\[\zeta(x,y)=\left\{\begin{matrix}1,&(x\geqslant y)\\0,&(x\not\geqslant y)\end{matrix}\right.\tag{7}\]

\[\mu(x,x)=1,\;\mu(x,y)=-\sum_{x\geqslant z>y}\mu(x,z)\tag{8}\]

\[\delta(x,y)=\prod_{i=1}^k\delta_i(x_i,y_i);\;\zeta(x,y)=\prod_{i=1}^k\zeta_i(x_i,y_i);\;\mu(x,y)=\prod_{i=1}^k\mu_i(x_i,y_i)\tag{9}\]

\[\delta(x,y)=\prod_{i=1}^k\sum_{x_i\geqslant z_i\geqslant y_i}\zeta_i(x_i,z_i)\mu_i(z_i,y_i)=\sum_{x\geqslant z\geqslant y}\prod_{i=1}^k\zeta_i(x_i,z_i)\mu_i(z_i,y_i)\tag{10}\]

2. Möbius反演公式

2.1 反演公式

  有了以上准备工作,现在把例子中的问题进行扩展。为了避免对无限的讨论,先限定对任意\(x\),小于它的元素有限,这样的偏序集称为下有限的。同样可以定义上有限,以下结论对上有限也有对应的结果。设\(f(x),g(x)\)是定义在偏序集\(X\)上的函数,而\(\alpha,\beta\)是\(I(X)\)中的互逆元,则需要证式(11)成立。

\[f(x)=\sum_{y\leqslant x}\alpha(x,y)g(y)\;\Leftrightarrow\;g(x)=\sum_{y\leqslant x}\beta(x,y)f(y)\tag{11}\]

  为了论证方便,可以把\(\sum\)的下标换成任意值\(y\)(因为当\(y\not\leqslant x\)时\(\alpha(x,y)=0\)),证明\(\Rightarrow\)时,只需把\(f(y)=\sum\limits_z\alpha(y,z)g(z)\)带入右式中的\(\sum\limits_y\beta(x,y)f(y)\)即可。过程从略,同样的方法可以验证\(\Leftarrow\)。特别地,对zeta函数有Möbius反演公式(式(12))成立,而式(11)是它的推广形式,这些结论都是美国数学家Rota在1964年发表的。

\[f(x)=\sum_{y\leqslant x}g(y)\;\Leftrightarrow\;g(x)=\sum_{y\leqslant x}\mu(x,y)f(y)\tag{12}\]

  当偏序集是有限集时,关系代数其实可以表示成方阵,这时反演公式其实就是线性方程组的解。为了显式地表示式(11)的递推关系,我们需要把方阵的行(列)按照偏序集元素的从小到大的顺序排列,这就需要把偏序关系扩展成全序关系。这一点是不难做到的,首先对\(n=1\)的偏序集已经是全序集,当\(n>1\)时先把一个极小值记作\(x_1\),其它\(n-1\)个元素仍然构成偏序集。由归纳法知它们可以扩展成全序集\(x_2\leqslant\cdots\leqslant x_n\),这时全序集\(x_1\leqslant\cdots\leqslant x_n\)就是满足条件的扩展。这个全序集的关联代数的方阵就是下三角矩阵,元素可逆的充要条件是:方阵的对角元素非零。

2.2 反演公式的应用

2.2.1 递推数列

  接下来具体讨论几个常见偏序集,先从最简单的单链\(L_n\)开始,则有式(13)的反演公式。把数列\(f(n),g(n)\)分别看成是行向量\(F,G\),再把它们的递推关系表示为互逆的下三角方阵\(A,B\),反演公式其实就是平凡的\(F=AG\Leftrightarrow G=BF\)。特别地,\(L_n\)的\(\zeta,\mu\)分别可以表示为式(2)中的矩阵。以上结论对\(n=\infty\)同样成立,\(F,G\)就变成无穷维行向量,\(A,B\)就是无穷维下三角方阵。

\[f(n)=\sum_{k=1}^na_{nk}g(k)\;\Leftrightarrow\;g(n)=\sum_{k=1}^nb_{nk}f(k)\tag{13}\]

  有时候我们需要得到除\(\zeta,\mu\)之外的互逆函数(方阵),而利用两个关系简单的数列就可以反过来求互逆函数。这里拿多项式举例(以下假定读者有高中排列组合知识),假设有两个多项式序列\(\{p_n(x)\},\{q_n(x)\}\),其中\(p_k(x),q_k(x)\)的阶都是\(k\),容易证明它们可以互相唯一线性表示。如果能某个关联函数能找到适当的多项式序列,那它的逆也就容易求得。比如考察\(p_n(x)=x^n\)和\(q_n(x)=(x-1)^n\),则显然有下式成立,所以二项式矩阵\(a_{ij}=\binom{i}{j}\)的逆元就是\(b_{ij}=(-1)^{i-j}\binom{i}{j}\),它被称为二项式的反演公式

\[p_n(x)=\sum_{k=0}^n\binom{n}{k}q_k(x);\;\;q_n(x)=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}p_k(x)\tag{14}\]

  二项式是非常常用的数列,利用这个反演公式可以解决一些很难的计数问题。比如考虑把\(n\)封信拆开重装,记有\(k\)封信装错的的装法有\(D_k\)个,这个数称为错位排列数,以后还会讨论。因为\(n\)封信的随意排列有\(n!\)种,而这其中可以分为有\(0,1,\cdots,n\)封装错的情况,从而有式(15)左式,由二项式反演公式就得到式(15)右式。

\[n!=\sum_{k=0}^k\binom{n}{k}D_k\;\Leftrightarrow\;D_n=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k!\tag{15}\]

  特别地,当\(q_n(x)=p_n(-x)\)时,它们的关联函数与自己互逆。以下记\((x)_n=x(x-1)\cdots(x-n+1)\),考察\(p_n(x)=(-x)_n\)和\(q_n(x)=(x)_n\),因为对任意整数\(m\)有式(16)成立。因为多项式之间的线性表示唯一,从而将\(m\)换成\(x\)等式也成立,这就得到了式(17),对应的反演公式被称为Lah反演公式

\[(-1)^n\dfrac{(-m)_n}{n!}=\binom{m+n-1}{n}=\sum_{k=0}^n\binom{n-1}{k-1}\dfrac{(m)_k}{k!}\tag{16}\]

\[(-x)_n=\sum_{k=0}^nl_{nk}(x)_n\;\Leftrightarrow\;(x)_n=\sum_{k=0}^nl_{nk}(-x)_n,\;l_{nk}=(-1)^n\dfrac{n!}{k!}\binom{n-1}{k-1}\tag{17}\]

2.2.2 容斥原理

  本节讨论集合\(A\)的子集簇\(B(A)\)在包含关系下的偏序集,这里只讨论\(\zeta,\mu\)函数。前面已经知道,\(B(A)\)是同构于\(L_2^n\)的,而\(L_2\)的\(\mu\)函数为\(\begin{bmatrix}1&0\\-1&1\end{bmatrix}\)。如果子集\(S\supset T\),则利用公式(9)易知\(\mu(S,T)=(-1)^{|S|-|T|}\),这个结论马上要用到。

  现在要讨论\(B(A)\)的函数\(f(S),g(S)\),并且它们有关系\(f(S)=\sum\limits_{T\subseteq S}g(T)\)。为了使问题直观且有意义,可以建立如下模型:设集合的每个元素有属性集\(X=\{P_1,P_2,\cdots,P_n\}\)中的部分属性,我们比较关心的集合有两种:恰好有属性子集\(T\)中的所有属性元素个数\(N_{=}(T)\),和至少有\(T\)中所有属性的元素个数\(N_{\geqslant}(T)\)。

  这个模型还有一个我们更熟悉描述方法,记所有含有性质\(P_k\)的元素为\(A_k\),则\(A_1,\cdots,A_n\)可以看作是全集\(A\)里\(n\)个子集。把\(n\)种性质简记为\([n]\),属性子集\(T\)则为\([n]\)的一个子集,式(18)说明了两种描述的等价关系。对另一个熟悉的集合\(A_1\cup\cdots\cup A_k\),可以先讨论它的逆\(\bar{A}_1\cap\cdots\cap \bar{A}_k\),将模型缩小为\(k\)个属性,它其实就是\(N_{=}(\varnothing)\)。

\[N_{\geqslant}(T)=\left|\bigcap_{i\in T}A_i\right|;\;N_{=}(T)=\left|(\bigcap_{i\in T}A_i)\cap(\bigcap_{j\not\in T}A_j)\right|\tag{18}\]

  在实际问题中,\(N_{\geqslant}(T)\)更容易求得,因为它只需关注具有属性集\(T\)元素。\(N_{=}(T)\)则比较难计算,但我们容易有式(19)左边的关系。它们满足属性子集的对偶偏序集上的反演公式,则容易有式(19)右边的结论。特别地有式(20)成立,它还有个直观的描述,不含有任何性质的元素可以这样计数:先在全集\(A\)中分别去除\(A_i\)的个数,然后加上被重复去除的\(A_i\cap A_j\),再加上多去除的部分……。这个过程就是在反复地去除再添加,因此式(20)也叫容斥原理

\[N_{\geqslant}(T)=\sum_{S\supseteq T}N_{=}(S)\;\Leftrightarrow\;N_{=}(T)=\sum_{S\supseteq T}(-1)^{|S|-|T|}N_{\geqslant}(S)\tag{19}\]

\[|A|-\left|A_1\cup\cdots\cup A_n\right|=N_{=}(\varnothing)=\sum_{k=0}^n(-1)^k\sum_{|S|=k}N_{\geqslant}(S)\tag{20}\]

  容斥原理是个很古老的结论,这里利用反演公式的证明比任何初等证明都清晰。之前其实我们已经运用过这个结论,这里再举几个例子。先来回顾一下错位排列问题,把第\(i\)位没有排错作为性质\(P_i\)。至少有\(k\)位排列正确的个数有\(\binom{n}{k}(n-k)!\),利用容斥原理并整理得式(21)左,它和式(15)其实是一样的。有趣的是还有式(21)右成立,它说明信封完全装错的概率趋于\(1/e\)。

\[D_n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!};\;\;\lim_{n\to\infty}\dfrac{D_n}{n!}=\dfrac{1}{e}\tag{21}\]

  再来看欧拉函数\(\varphi(n)\),它表示\([n]\)中与\(n\)互素的数的个数。设\(n\)的全部质因数是\(p_1,\cdots,p_k\),以被\(p_i\)整除为性质\(P_i\),\([n]\)中至少被\(m\)个质因数整除的个数是\(\sum \dfrac{n}{p_{i_1}\cdots p_{i_m}}\)。利用容斥原理并整理得式(22),它也有显然的概率论意义:不被\(p_i\)整除 与不被\(p_j\)整除是独立事件。

\[\varphi(n)=n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\cdots(1-\dfrac{1}{p_k})\tag{22}\]

   计算\([n]\)中与\(n\)互素的数之和;(提示:计算能整除\(p_1\cdots p_i\)的数之和,答案\(\dfrac{1}{2}n\varphi(n)\))

   字母\(a_1,\cdots,a_n\)各有两个,用它组成的\(2n\)元字中,相同字母不相邻的字有多少个?

2.2.3 经典反演公式

  最后来讨论正整数集在整除关系下偏序集,其实这是Möbius反演公式的最初原型。当\(d|n\)时,先来计算\(\mu(n,d)\),为此考虑偏序集\(D(n)\),其中\(n=p_1^{e_1}\cdots p_k^{e_k}\)。前面知道它同构于\(L_{e_1+1}\times\cdots\times L_{e_k+1}\),\(\mu_i(n_i,d_i)\)(\(n_i,d_i\)分别是\(n,d\)中\(p_i\)的幂)当\(n_i=d_i\)相等时为\(1\),当\(n_i=d_ip_i\)时为\(-1\),其它为\(0\)。

  利用公式(9)可以证明,\(\mu(n,d)\)只与\(m=\dfrac{n}{d}\)有关,由此可直接记作\(\mu(m)\)。它就是经典Möbius函数,易知它有表达式(23),其下的经典Möbius反演公式便是式(24),之前的反演公式是推广后的结论。

\[\mu(m)=\left\{\begin{matrix}(-1)^r,&\text{all }e^i=1\\0,&\text{others}\end{matrix}\right.,\;\;(m=p_1^{e_1}\cdots p_r^{e_r},\;\text{all }e^i>0)\tag{23}\]

\[f(n)=\sum_{d|n}g(d)\;\Leftrightarrow\;g(n)=\sum_{d|n}\mu(\dfrac{n}{d})f(d)\tag{24}\]

上一篇:Java 图形编程 一:入门


下一篇:SQL Server 2008 R2不支持limit(限制行数)