组合数学课件：反演公式

反演公式4.1第一反演（inversion）定理

4.2Mobius反演定理

4.3筛法公式（Sieveformula）

4.4棋盘多项式与有限制排列

4.5树的计数..4.1第一反演（inversion）定理

定义1设P0(x),P1(x),P2(x),…是实变元x的一族多项式，其中P0(x)=1，且当n>0时，Pn(x)是n次多项式，Pn(0)=0,则称这样的多项式族为正规族。

定义2若算子D把多项式φ(x)映成一个多项式Dφ(x)，且满足条件：(1)若n≠0若n=0(2)D(λφ(x)+λφ′(x))=λDφ(x)+λDφ′(x)，λ为常数。则称D为伴随多项式族Pn(x)(n=0,1,…)的微分算子。命题1

对于多项式的每个正规族Pn，恰存在一个微分算子。

证明易证每个n次多项式φn(x)都可以唯一地表示为其中an,an-1,…,a0是常数。事实上，取an为φn(x)中xn的系数除以Pn(x)中xn的系数所得的商，则φn-1(x)=φn(x)-anPn(x)至多是n-1次的，再取an-1为φn-1(x)中xn-1的系数除以Pn-1(x)中xn-1的系数所得的商，接着考虑

由它可定出an-2，如是而下，可唯一确定an,an-1,…,a0这些常数。由此，公式就唯一确定了算子D。

命题2（Taylor公式）设Pn(x)是多项式的一个正规族。若φ是x的一个n次多项式，则φ(x)可唯一地展开为(4.1.1)证明由命题1，有令x=0，可得φ(0)=a0，作用算子D，得再令x=0,可得Dφ(0)=a1，再作用算子D，得D2φ(x)=2a2P0(x)+2·3a3P1(x)+…+(n-1)·nanPn-2(x)因此如是而下，一般有

若设Pn(x)=xn，则伴随这一正规族Pn(x)的微分算子D就是通常的微商d/dx，上述命题中的公式，就是标准的Taylor-Maclaurin展开式。

1.二项式公式令y为一常数，考虑多项式φ(x)=(x+y)n，取Pn(x)=xn(P0(x)=1,Pn(0)=0,n≥1)

这时，伴随族Pn(x)的微分算子就是通常的微商：于是φ(0)=yn

Dφ(0)=nyn-1D2φ(0)=n·(n-1)yn-2

…Dkφ(0)=n(n-1)…(n-k+1)yn-k

公式（4.1.1）变为此即二项式公式。2.Δ二项式公式（Vandermonde）考虑相对于多项式族Pn(x)=［x］n=x(x-1)(x-2)…(x-n+1)(Pn(0)=0,n≥1)的Taylor公式。由Δφ(x)=φ(x+1)-φ(x)定义的（向前差分）算子Δ就是伴随多项式族Pn(x)=［x］n的微分算子，因为

Δ［x］n=［x+1］n-［x］n=(x+1)［x］n-1-(x-n+1)［x］n-1=n［x］n-1

使用［x］n的Taylor公式展开φ(x)=［x+y］n，注意到Δkφ(0)=n(n-1)…(n-k+1)［y］n-k

就有Δ二项式公式：3.二项式公式（Norlund）考虑相对于多项式族(Pn(0),n≥1)的Taylor公式。由

定义的（向后差分）算子,就是伴随多项式族Pn(x)=［x］n的微分算子，因为展开多项式φ(x)=［x+y］n，并注意到可得二项式公式：命题3(第一反演定理）设φn(x)和ψn(x)是满足(4.1.5)的n次多项式族，其中n=0,1,2,…,m，则n=0,1,…,m

证明记列向量(4.1.6)则（4.1.5）式等价于φ(x)=Aψ(x),ψ(x)=Bφ(x)(4.1.7)其中方阵A=(αnk),B=(βnk)都是m+1阶的下三角阵。因此，φ(x)=Aψ(x)=ABφ(x)，于是AB=I，I为m+1阶单位阵，即（αnk）与（βnk）互逆。换言之，向量等式a=(αnk)b等价于 b=(βnk)a

其中， 都是m+1维空间的列向量。亦即（4.1.6）式成立。推论1（二项式反演公式)(4.1.8)证明取φn(x)=xn，ψn(x)=(x-1)n,则由二项式定理若设an与bn的指数生成函数为A(x)及B(x)，则由乘法公式可见（4.1.8）式实即A(x)=B(x)ex

B(x)=A(x)e-x的另一种形式。

例1(重排（也称更列，错排）问题)集合{1，2，…，n}的n！个排列a1a2…an中，满足ai≠i(i=1,2,…,n)的排列有多少个？这一问题也可叙述为：有n个学生坐在n个不同的座位上，今重新安排各人的座位，使每个人不至于回到原先的座位上，问有多少种重排方式？

解如当n=4时，共有9个这样的排列：214323412413314234123421412343124321

而如4132，因a3=3，故不属此种排列。

设Dn为问题的解，易见CknDn-k为恰有k个ai=i的排列a1a2…an之个数，又全排列数为n！，则应用二项式反演公式解得n个数的错排由此可见错排与全排列的比值几乎与n无关。“错排”问题最初由N.Bernoulli提出，原意是：“某人写了若干封信和相应的信封，问所有的信都装错了信封的情形有多少种”，该问题后由Euler解决。例2因p元集X到n元集A的映射数是对照（4.1.8）式，有或（Stirling公式）推论2(Stirling反演公式）证明取φn(x)=xn,ψn(x)=［x］n,因为由第一反演定理即得（4.1.9）式。由第一反演定理知(Skn)与(skn)互逆，再利用第一类Stirling三角，不难求得第二类Stirling三角。推论3（Lah反演公式）其中L(n,k)称为Lah数。证明注意到［-x］n=(-1)n［x］n是x的n次多项式，故必可展开成在上式中以-x代x，便得由第一反演定理即知（4.1.10）式为真。（4.1.10）如下推导L(n,k)的显式，由2.7节公式（2.7.19），有因此或所以4.2Mobius反演定理..寻求一般形式的反演公式(4.2.1)归结为求（上）三角阵C=(cij)的逆阵D=(dij)。对任一（上）三角阵C，只要主对角线元cii≠0，其逆阵可由下面的递推公式求出：首先由CD=I得(4.2.2)其中δij为Kronecker函数：(4.2.3)

因C、D均为上三角阵，故对i>k，cik=0,对k>j,dkj=0,于是（4.2.2）式可化为(4.2.4)对i=j，即得ciidii=1，由此得dii=c-1ii

(4.2.5)而对j>i，由δij=0及（4.2.4）式推得(4.2.6)

（4.2.5)、（4.2.6）两式给出了由下而上依次计算上三角阵的元素dij的递推算法。

计算dij的算法如下：(请留意出口判别循环结构中下标出界的现象。)

№1定义数组C(0:N,0:N),D(0:N,0:N)

№2输入或求算上三角阵C；№3对i=N,0，步长取-1，做

№3.1D(i,i)

1/C(i,i);

№3.2对j=i+1,N，做

№3.2.1S

0;

№3.2.2对k=i+1,j,做

S

S+C(i,k)*D(k,j);

№3.2.3D(i,j)

-S/C(i,i);№4按行打印上三角阵：C，D；

№5结束。以上算法并不能给出dij的解析式，若g(n)也不要求给出解析解时，亦可通过算法求得离散数据。（4.2.5）、4.2.6）两式中出现的变元i，j，k可推广到更一般的集合P中，关系式i≤k≤j

等可推广为P中一种意义更广泛的序关系，从而反演公式（4.2.1）可推广成更一般的形式，并从中引出若干有用的结果。

定义1设(P,

)为一偏序系统（Poset），其中“”是定义在P上的偏序关系,即

x,y,z∈P,x

x,x

y∧y

x

x=y,x

y∧y

z

x

z

若对x,y∈P,［x,y］={u|u∈P∧x

u

y}是有限集，则称(P，)为局部有限偏序系统。例如：

(1)设P为自然数集N，P上的偏序关系“”就定义为通常的小于等于“≤”。

(2)设P为正整数集Z+，P上的偏序关系“”定义为整除“|”，即对a,b∈P，a

b∷=a|b(“∷=”取自BNF，读做“定义为”)

(3)设P={1,2,…,n}，则2P连同其上的包含关系“”构成一局部有限偏序系统。

注1

偏序系统中的任两个元素并不总是有序关系，亦即对a,b∈P，可能a

b,b

a都不真，如上面举例的(2)中，5

7∧7

5；(3)中，{1,2}

{2,3},{2,3}

{1,2}。但(1)中，对a,b∈P总有a

b或b

a，这种偏序系统称为线序系统（Loset）。

注2对于一个偏序系统(P，)，总可假定其中有最小元0，满足0

a(

a∈P)(如果P中不含有最小元，那么总可以附上这样一个元素）。

定义2

设G是定义在偏序集P的叉积集合P×P上的满足下列条件的实值函数的集合（其值域不限）：f(x,y)≠0,若x=yf(x,y)=0,若x≤y

此处x≤y表示x与y不可比较，对f(x,y)的这一限制类似于前面对上三角阵（cij）的限制；cii≠0,cij=0(j<i)。仿照（4.2.4）式，在G中引进“卷积”运算“*”：

命题1（G，*）构成一群（group），常称之为算术函数群。

证明

(1）先证（G，*）为一半群。只需证结合律，由定义（2）再证（G，*）为一幺半群。不难确定Kronecker函数若x=y若x≠y

是（G，*）的幺元。由定义加之有（1），即知（G，*）为一幺半群。

（3）注意到幺半群中任一元素a，若其有左逆a-1，则该左逆就是a的右逆（由于幺半群具有结合律）。事实上，有aa-1=f=δf=f-1ff=f-1aδa-1=f-1aa-1=f-1f=δ

因已有（1），(2)，为证（G，*）是群，只需再证对f∈G,f均有左逆元。对每个给定的x,f-1(x,y)关于y可归纳定义（比较（4.2.5）,（4.2.6）式）如下：当y=x时，则(4.2.9)当y

x时，则(4.2.10)(4.2.10)式也可以隐式给出如下：

注意到对G的限制f(y,y)≠0,故1/f(y,y)有定义；又因满足x

u

y的元素是有限的，故上述和式仅有有限项，所以上述两步定义的f-1(x,y)是确定的。下证f-1*f=δ

事实上，当x=y时，有(f-1*f)(x,x)=f-1(x,x)f(x,x)=1而当x

y∧x≠y时，有因此，可得f-1*f=δ

这就证明了（G，*）是一个群。

由逆元的定义，若f=g*a,则g=f*a-1（反演公式的雏形）。故若记α-1=β,f(x)=f(0,x),g(x)=g(0,x)，则由“*”运算的定义有(4.2.11)此式概括了一类广泛的反演公式。为将Mobius反演公式推广到一般情形，取α(x,y)=ζ(x,y),这里..(4.2.12)ζ函数称作Riemann函数，其逆ζ-1(x,y)称作Mobius函数，记做μ(x,y)。由（4.2.9）,（4.2.10）式可见，μ(x,y)可按下式算出..(4.2.13)由（4.2.11）式即得下面重要的反演公式。

命题2（Mobius反演定理）设(P,

)为局部有限的偏序系统，f(x)与g(x)为定义于p上取值于某一域中的函数，则..

例1

设N为自然数集，N上的偏序关系定义为通常的小于等于。局部有限偏序系统（N，≤）的Hasse图如图4.2.1所示。因从k到n的路只有一条，故由（4.2.13）式可以算得相应的Mobius函数为..于是的反演公式为图4.2.1例1图图4.2.2例2图

例2设Z+为正整数集，a,b∈Z+,a

b∷=a|b(“∷=”取自BNF，读做“定义为”)。偏序系统（Z+,）的Hasse图如图4.2.2所示。由图不难求得相应的Mobius函数..若n=d

若n=p1p2…pkd

其它情形其中pi(i=1,2,…,k)是互不相同的素数。由此的反演公式为这个函数μ(d,n)(通常写成 是Mobius在1832年为研究素数分布而首次引入的经典的Mobius函数。....

例3设A为一有限集，(2A,

)的Hasse图如图4.2.3所示，其上的序关系即A的子集间的包含关系。由图4.2.3及（4.2.13）式不难求得对应的Mobius函数为..由此的反演公式为

例4设πs,πt分别为把n元集A划分成s个类和t个类的划分（其中,s≤t），πt≤πs∷=πt

细分πs（即对Ai∈πt

Bj∈πs∧Ai

Bj)，令Γ(A)为A上的划分的全体，则局部有限偏序系统(Γ(A),≤)的Hasse图（以A={a,b,c,d}为例）如图4.2.4所示。令πp是把A划分成p个类的划分，它使每个Ai∈πp包含πs(πs≤πp)的ni个类,则利用Mobius函数的可乘性，可用简单的Mobius函数合成复杂的Mobius函数，简述如下：......

定义3设(P1,1)与(P2,

2)为两个局部有限偏序系统，对a,b∈P=P1×P2，有a

b∷=a1

1b1∧a2

2b2

其中a=(a1,a2)，b=(b1,b2)。

命题3设(P1,

1),(P2,

2),(P,

)上的Mobius函数分别为μ1，μ2与μ，则μ((x1,x2),(y1,y2))=μ1(x1,y1)μ2(x2,y2)

证明略。

设A={a1,a2,…,an}，令Σn={b|b=(b1,b2,…,bn)∧(bi=0∨bi=1)},Σn上的偏序关系定义为t≤r

ti≤ri(i=1,2,…,n)。不难证得（2A,）与（Σn,≤）同构。事实上，对S,S

A对应于f(S)=(b1,b2,…,bn)，其中bi=1

ai∈S。又显见f为保序映射，因此，为计算（2A,）上的Mobius函数，只需计算（Σn,≤）上的Mobius函数。但Σn=Σ1×Σ1×…×Σ1，对于Σ1,x≤y无非是x=y或x=0∧y=1，故μ(x,y)=(-1)y-x。由命题3知

但当S，A分别与(x1,x2,…,xn)和(y1,y2,…,yn)对应时,

故而对S

A的情形，由μ的定义知μ(S,A)=0。

例5(环状字（圆排列）计数问题)从有m个字母的字符集Σm中任取n个字母（允许重复），按顺时针方向排成环状A1a2a3…ai…an…an+i…,an+i=ai则称w=a1a2…an为长为n的环状字。由于环状排列可选其中任一文字为a1,故a1a2…an与ana1a2…an-1等都视为同一环状字。例如当m=2,n=4,T={a,b}时，计有6个环状字aaaa,bbbb,abab,aabb,aaab,bbba其中，aabb也可写成abba，bbaa，baab。

如对i有ai=a(i+p)(modn)，则称该环状字w有周期p。最小的周期p称为w的元周期。例如,abcabcabc的元周期p=3。易证元周期既是周期的因子，又是n的因子。显见一个元周期为p的环状字对应于p个不同的（线状）排列，若记M(p)为元周期是p的环状字的个数，则总的排列数利用例2中的Mobius函数μ(d,n)..若n=p1p2…pkd

其它情形反解上述公式，得到因此，长为n的环状字总数是

例6设多重集S={∞·a,∞·b,∞·c}，求（1）元周期为4的4-可重圆排列的个数M(4)。（2）所有4-可重排列的个数T(4)。

解本例中，m=3,n=4。（1）由于μ(1,4)=μ(4/1)=μ(22)=0

μ(2,4)=μ(4/2)=μ(2)=-1

μ(4,4)=μ(1)=1故18个元周期为4的4-可重圆排列罗列如下:

不含a:⊙bbbc⊙bccc⊙bbcc(⊙bcbc元周期是2)

不含b: ⊙aaac⊙accc⊙aacc

不含c:⊙aaab⊙abbb⊙aabb

1a1b2c:⊙abcc⊙acbc⊙accb

1a1c2b:⊙acbb⊙abcb⊙abbc

1b1c2a:⊙bcaa⊙baca⊙baac

（2）元周期为1的4-可重圆排列:⊙aaaa,⊙bbbb,⊙cccc。元周期为2的4-可重圆排列:⊙abab,⊙acac,⊙bcbc。因M(4)=18在（1）已求得,故

T(4)=3+3+18=24

例7红,蓝,黄三种珠子,每种充分多,从中取出9个摆成一个圆环,求不同的摆法数。

解这里m=3,n=9,问题是求T(9)。从而T(9)=3+8+2184=2195

对每种颜色珠子的数目不加限制的圆形排列的计数，由前边的讨论已经解决；现若对各种珠子的颜色加以限制，例如，S={2·r,3·b,4·y}表示有2个红珠，3个蓝珠，4个黄珠，则求S的圆排列数就成为有限多重集的圆排列问题。一般情况下，设S={r1·e1,r2·e2,…,rm·em}为m元有限多重集，其中，各元重数满足r1+r2+…+rm=n。由这n个元素构成的n-圆排列称为(r1,r2,…,rm)型圆排列。下面来推算求这种圆排列的计数公式。

易知(r1,r2,…,rm)型圆排列对应(r1,r2,…,rm)型的线排列数目为

又若⊙a1a2…an为一(r1,r2,…,rm)型的圆排列，d为该圆排列的周期，则d|n,且⊙a1a2…an可视为k个a1a2…ad首尾相接而形成的，即有n/d=k。此外，k|ri(i=1,2,…,m)，这是因为若在a1a2…ad中的第i个元素重复次数为ri′，则在⊙a1a2…an中，该元素重复次数便是kri′

=ri′，且有r1′+r2′+…+rm′=d。(r1,r2,…,rm)表示r1,r2,…,rm的最大公约数，则k|(r1,r2,…,rm)

若用M(r1′,r2′,…,rm′)表示长度为d，周期也是d的圆排列的个数，由此，周期为d的所有n个元素的(r1′,r2′,…,rm′)型圆排列所对应的n-可重线排列的个数便是d·M(r1′,r2′,…,rm′)。对所有可能的周期求和便得到即

现在的问题是如何从上式解出未知数M来，因M为一多元函数，故需对Mobius公式作如下推广。..（4.2.15）

命题4(多元函数的Mobius公式)

设f,g是以自然数为变量的m元函数，则..证明令kd=s,则因s|(r1,r2,…,rm),对某一固定的s,k要遍历s的所有因子,故上式又可写为由于故结果为g(r1,r2,…,rm)

推论1设S={r1·e1,r2·e2,…,rm·em}，r1+r2+…+rm=n，则

（1）周期为n的(r1、r2、…、rn)型圆排列的个数为

（2）所有(r1,r2,…,rm)型的圆排列的总数目为证明（1）假设g(r1,r2,…,rm)=(r1+r2+…+rm)M(r1,r2,…,rm)由关系式（4.2.15）,有即由多元函数Mobius反演公式..即(2)令d/d′=k,由于d|n

kd′|n

d′|n/k及从而,上述和式的求和范围有等价式：又因因此，上述和式可写为（1/d换为1/k）推论2

若(r1,r2,…,rm)=1，则

例8对最初提出的问题S={2·r,3·b,4·y}，求所有的长为9的圆排列的数目。

解由于(r1,r2,r3)=(2,3,4)=1，即2、3、4互素（不是两两互素），由推论2知

例9

设S={2·x,4·y}，求（1）周期和长度都是6的（2，4）型圆排列的个数；（2）长为6的所有（2，4）型圆排列的个数。

解（1）由推论1的（1）知这2个（2，4）型圆排列是⊙xxyyyy，⊙xyxyyyy。（2）由推论1的（2）知其中d=1,2,φ(1)=1,φ(2)=1,所以

长为6的（2，4）型圆排列除上述2个（周期亦为6）外，还有1个周期为3的圆排列：⊙xyyxyy。例10

设S={3·x,6·y}，求（1）周期为9的（3，6）型圆排列数；（2）所有的（3，6）型圆排列数。

解（1）据推论1的（1）知9个圆排列罗列如下：⊙xxxyyyyyy⊙xxyyyyyxy⊙xxyxyyyyy

⊙xyxyxyyyy⊙xxyyxyyyy⊙xyxyyxyyy

⊙xxyyyxyyy⊙xyxyyyxyy⊙xxyyyyxyy（2）据推论1的（2）知由于d=1,3,φ(1)=1,φ(3)=2，所以

这10个圆排列除（1）中的9个（周期为9）外，还有1个周期为3的圆排列：⊙xyyxyyxyy。4.3筛法公式（Sieveformula）

定义设X为一有限集，定义X上的一个非负实值函数w，使对x∈X,w(x)≥0，称w为x的测度（或权）函数。若A

X，记则称w(A)为集合A的测度。例如，若对x∈A,w(x)=1,则w(A)=|A|是集合A的基数。若w(x)是概率分布而A是具有某性质的事件的集合，则w(A)表示这种事件的概率。命题1

设A,B

X,A表示A的补集X\A，则命题2

设Ai(i∈Q={1,2,…,q})是X的子集，并记则(4.3.1)

证明令A=A1∪A2,则Q={1,2},K1={1},K2={2},K3=Q,显见有

下面对|Q|=q>2作归纳：假定对任意q-1个子集A1,A2,…,Aq-1的集合命题为真,则对q个子集A1,A2,…,Aq有这就完成了归纳法对（4.3.1）式的证明。命题3设Ai(i∈Q={1,2,…,q})都是X的子集，则用Mobius反演定理，反解（4.3.1）式，得..证明（4.3.1)式对应的Mobius函数由下式给出（见4.2节例3）：

μ(I,J)=(-1)|J|-|I|..因此(4.3.2）式也可由（4.3.1）式取补而得。

推论（包含排斥原理A）若对定义w(A)=|A|，则（4.3.2）式变为(4.3.3)命题4(Sylvester公式）设Ak

X(k∈Q={1,2,…,q})，记则 的测度是(4.3.4)证明由命题2，有

推论1（包含排斥原理B）对定义w(A)=|A|则（4.3.2）式变为(4.3.5)推论2（包含排斥原理B′）注意到故有(4.3.6)

命题5（筛法公式）

设Ak(k∈Q={1,2,…,q})

X，则恰属于其中p个子集的元素所成之集的测度是(4.3.7)

证明设P为Q={1,2,…,q}的任一p元子集，把Sylvster公式（4.3.4）中的X换作 ，并把Aj(j∈Q)换为 ，则得到因此显见Sylvester公式是筛法公式当p=0时的特殊情况。

推论（包含排斥原理C）

若令w(A)=|A|，则X中恰属于A1,A2,…,Aq中p个子集的元素的个数为(4.3.8)

命题3,4及5的几个推论是集合运算中常用的几种形式的包含排斥原理（Inclusion

exclusionPrinciple），也常被称为容斥原理或入与出原理。事实上，上述几个命题本身就是更广泛意义上的容斥原理。

例1设S={a,b,c,d},求由S中的字符构成的长为n的字符串中a,b,c,d均至少出现一次的字符串的数目。

解设A1,A2,A3,A4分别表示不出现a,b,c,d的n位字符串的集合。题目实际上是要求 。不加限制时，因n位字符串中的每一位均可选a,b,c,d4个字符之一，故S中字符构成的n长字符串共有4n个；不出现a时，因每位只能选b,c,d之一，故这种n长字符串共有3n个，即同理从而

例2求多重集S={3·a,4·b,5·c}中元素的10组合数。

解设T={∞·a,∞·b,∞·c}，令T10={x={x1,x2,…,x10}|xi∈T,i=1,2,…,10}T10即为T中元素的10组合所成之集。设S10为S的10组合所成之集，则S10

T10。记a,b,c在10组合x中出现的次数分别为d(a)，d(b)，d(c)，并设A1={x|x∈T10∧d(a)>3}A2={x|x∈T10∧d(b)>4}A3={x|x∈T10∧d(c)>5}则S10可表示为S10={x|x∈T10∧d(a)≤3∧d(b)≤4∧d(c)≤5}={x|x∈T10}\{x|x∈T10∧(d(a)>3∨d(b)>4∨d(c)>5)}=T10\({x|x∈T10∧d(a)>3}∪{x|x∈T10∧d(b)>4}∪{x|x∈T10∧d(c)>5})=T10\(A1∪A2∪A3)从而|S10|=|T10|-|A1∪A2∪A3|=|T10|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)-|A1∩A2∩A3|

下面分别计算上式右端各项：（1）由生成函数的讨论已知|T10|=C103+10-1=66;

（2）因A1是T中a至少出现4次的10组合，故从A1中任一元素取掉4个a即为T中元素的一个6组合,反之对于T中元素的任一6组合,若向其添加4个a即为A1中的一个元素。从而A1与T的6组合之集形成双射，故|A1|=C63+6-1=28同理，A2与T中的5组合之集存在双射，A3与T中的4组合之集存在双射。故

（3）A1∩A2中的元素是T中至少出现4个a，5个b的10组合，从A1∩A2的任一元素取掉4个a，5个b，即得T的一个1组合；反之，对T的任一1组合中添加4个a和5个b，便得A1∩A2中的一个元素。即A1∩A2与T的1组合之集形成双射。故同理总之

例3

设x+y+z+w=20,其中，0≤x≤6，0≤y≤7,0≤z≤8,0≤w≤9，求该不定方程的非负整数解的个数。

解设X={(x,y,z,w)|x+y+z+w=20,x≥0,y≥0,z≥0,w≥0}，并设题给不定方程的非负整数之集为S，则S=X-{t|t∈X∧(x>6∨y>7∨z>8∨w>9)}

=X-{t|t∈X∧x>6}∪{t|t∈X∧y>7}∪{t|t∈X∧z>8}

∪{t|t∈X∧w>9}令A1={t|t∈X∧x≥7},A2={t|t∈X∧y≥8A3={t|t∈X∧z≥9},A4={t|t∈X∧w≥10}从而|S|=|X|-|A1∪A2∪A3∪A4|

下面分别求|X|,|Ai|(1≤i≤4)，|Ai∩Aj|(1≤i<j≤4),|Ai∩Aj∩Ak|(1≤i<j≤k≤4),|A1∩A2∩A3∩A4|。（1）易知

（2）为求|A1|,令x′=x-7，则x+y+z+w=20(x>6,y,z,w≥0)成为x′+y+z+w=13(x′≥0,y≥0,z≥0,w≥0)

设此不定方程的非负整数解集为A1′，则A1与A1′间存在双射。因此同理

（3）为求|A1∩A2|,令x′=x-7,y′=y-8，则x+y+z+w=20成为x′+y′+z+w=5。记此不定方程的非负整数解集为A12′，则A1∩A2与A12′间存在双射。由于同理可得

（4）为求|A1∩A2∩A3|，令x′=x-7,y′=y-8，z′=z-9，则x+y+z+w=20成为x′+y′+z′+w=-4。显见后一方程不存在非负整数解，又A1∩A2∩A3与x′＋y′＋z′+w=-4非负整数解集间存在双射，故|A1∩A2∩A3|=0同理

|A1∩A2∩A4|=|A2∩A3∩A4|=|A1∩A2∩A3∩A4|=0

综上讨论，可得

例4设A={1,2,…,n}，对于A的排列，记不出现12,23,…,n(n-1)形式的排列数为Qn。例如A={1,2,3,4,5}，54321及21345均是满足要求的排列，而32451却不是，因为出现了45。试证：

证明设X为A中所有排列之集，则|X|=n!，令Ai为A中含有i(i+1)形式的排列之集，i=1,2,…,n-1，则A中不含12，23，…,(n-1)n形式的排列之集为 。从而

（1）为求|Ai|，将i(i+1)看作一个整体，与另外n-2个元素所成的排列共有(n-1)!个，即有(n-1)!个含有i(i+1)的排列，从而|Ai|=(n-1)!,i=1,2,…,n-1。（2）为求|Ai∩Aj|，分别将i(i+1)，j(j+1)看作两个整体，与其余n-4个元素形成的排列数有(n-2)!个，故|Ai∩Aj|=(n-2)!,1≤i<j≤k。一般地，有|Ai1∩Ai3∩…Aik|=(n-k)!,k=1,2,…,n-1。注意到这种k组合数为Ckn-1，故对固定的k，所有满足有k项前后（前数＝后数－１）相邻的排列数为Ckn-1(n-k)!。这就得到了Qn满足的等式。

例5(相遇（保位）问题（Montmort）)

设 是（1，2，…，n）的一个置换，如果φ(i)=i,则称φ在i处有一次“相遇”。求在n阶置换中恰有q个相遇的置换数。

解设D(n)是没有相遇的置换数，并设Ai是在i处有一个相遇的(n-1)!个置换的集合。由Sylvester公式，有其中，若令|K|=k，则因此亦即显见，恰有q个相遇的置换数是

特别地，当q=0时，D(n)即为错排数。从而问题归结为求算D(n)，而后者是易于用下列公式计算的：由此递推式可得

例6(入座问题（Touchard）)“入座问题”是求编号为1~n的n个丈夫和他们各自的妻子（编号为1′~n′）围着一个圆桌入坐，要求男女间隔但却不得与自己的妻子相邻的入座方式数T(n)。

解显见满足上述要求的每种坐法都可用一双射函数φ来描述：设A2i-1(i∈{1,2,…,n})为满足φ(i)=i′的双射φ的集合；并设A2i为满足φ(i)≡((i+1)modn)′的双射φ的集合。由Sylvester公式，“入座问题”的解1φ(1)2φ(2)3φ(3)…nφ(n)其中Q={1,2,…,2n}。

当|K|=k时，如果K不含有序列（1，2，…，2n，1）中的前后相邻的整数时，有其它情形下，有但由前边对Fibonacci数的讨论而知，不含有序列（1，2，…，2n，1）中二相邻整数的集合K（|K|=k）的数目是因此

例7

与例6相似，根据筛法公式，n个丈夫与n个妻子围一圆桌入座，使得男女相间且恰有q个丈夫与他们的妻子相邻的坐法数目是

例8设n是正整数，a1,a2,…,aq是q个两两互素的正整数，则满足0<t≤n∧ai

t,i=1,2,…,q的整数t的个数等于

证明令X={1,2,…,n}，Ai表示X中能被ai(i=1,2,…,q)整除的元素所成之集，由于ai两两互素，因此在筛法公式中是满足关系式的整数t的个数，它等于故由筛法公式推得题设公式。例9

设n是正整数，则有其中，φ(n)为Euler函数，乘积遍历n的素因子p。

证明在例8中把ai取为pi,并假定p1,p2,…,pq是n的全部素因子，则Euler函数事实上，设当d|n∧d≠1时，即对n的某个非1因子d，若则由Mobius函数定义..不难推得将其代入公式φ(n)中，即有(其中，和式遍取n的正因子d)4.4棋盘多项式与有限制排列

1.再提错排问题

n个元素1,2,…,n的全排列中，求每个元素都不在自己原来位置的排列数。设Ai为n个数中数i在第i位上的所有排列所成之集，i=1,2,…,n，因数字i不动，这相当于只有n-1个数的全排列，故|Ai|=(n-1)!，i=1,2,…,n

若对i,j=1,2,…,n且i≠j,数字i,j分别固定在第i、第j位时，同理，这相当于只求n-2个数的全排列，故|Ai∩Aj|=(n-2)!,i,j=1,2,…,n,i≠j从而，每个元素都不在原来位置上的排列数为

例1数1,2,…,9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。#;

解实际上，因偶数都不动，只剩下1,3,5,7,9五个数进行排列，又各数都不在相应的位置，即又转化为1,3,5,7,9五个数的错排问题。总数为5对夫妇，成对排成一排，女士不动，男士不在原先位置上的排列数问题同上。

例28个字母A,B,C,D,E,F,G,H的全排列中，求使A,C,E,G4个字母不在原来位置上的错排数目。

解此题未限制B,D,F,H动与不动，即其可在对应位置，也可不在对应位置。8个元素的4个错排与例1有所不同。设A1,A2,A3,A4分别表示A,C,E,G在原来位置上的排列，则

例3求8个字母A，B，C，D，E，F，G，H的全排列中只有4个元素不在原来位置上的排数。（其中另外4个保持不动。）

解先求4个元素的错排故8个元素只有4个不在原来位置上的排列数应为

例44个x,3个y，2个z（4个红球，3个黄球，2个蓝球）的全排列中，求不出现xxxx,yyy,zz图样的排列数。

解n个字母的全排列共有n!个。出现xxxx图样者记为Ax：出现yyy图样者记为Ay：出现zz图样者记为Az：4个x，3个y，2个z的全排列中不同者共有9!/(4!3!2!)个。

例5任给正整数n,求2到n之间的素数的个数。解决这一问题，需借用如下引理：

引理对任给n∈Z+，设{q1,q2,…,qs}为2到n之间的所有素数，从2到n中筛划掉qi(i=1,2,…,s)的倍数后，余下的数即为到n之间的素数。

证明只需证2到n中的任一合数均为{q1,q2,…,qs}中某一素数qt的倍数。事实上，设m∈{2,3,…,n}，若m不是素数,由算术基本定理有其中p1<p2<…<pk，pi为素数，αi为正整数(i=1,2,…,k)。可证 ，因为若 ，则会有 ,即m>n，这与m的来历不符，故 。又因p1为素数，故qt∈{q1,q2,…,qs}使p1=qt。从而m为qt的倍数，或qt可以整除m。引理得证。由此引理，在一个很小范围 中的素数不难给出，进而再求n以内的全部素数，可以大大减少计算工作量。对于计数问题，所关心的是序列划掉qi(i=1,2,…,s)的倍数后，还剩下多少个数（由引理知剩下的无疑都是素数）。下面求该数目的表达式。

令π(n)表示{2,3,…,n}上的所有素数，利用筛法引理， ,上的素数个数应为 。从而问题转化为求{2,3,…,n}中不是qi(i=1,2,…,s)的倍数的数的个数，即求{2,3,…,n}中不能被任一qi(i=1,2,…,s)整除的数的个数。即有利用Mobius函数μ(n)，上式可写为..例如：求{2,3,…,120}中素数的个数。容易求出小于等于的素数共有4个，它们是2,3,5,7，于是最后得到π(120)=26+4=30

2.棋盘多项式

n个元素的一种排列，可视为n个棋子在n×n棋盘上的一种特殊布局，即当某棋子放到棋盘的某一格内时，则该棋子所在的行和列不允许再放棋子。例如,排列2314和图4.4.1所示的布局对应，即1,2,3,4各行的棋子分别布于2,3,1,4各列。记棋盘为C，它可以是小方格拼成的任意形状，但在棋盘上布子时，要求每行每列有且只有一个棋子。令rk(C)表示k个棋子布放到棋盘C上，且满足上面要求的禁位放法数。对图4.4.2所示棋盘C，则用1枚棋子布放时的方案数r1(C)=4，用2枚棋子布放时的方案数r2(C)=3。明显地，还有r3(C)=0。图4.4.1排列2314对应布局图4.4.2残缺棋盘对某个给定的棋盘C，引入数列r0,r1,…,rn的生成函数为且规定R(￠)=1,r0(C)=1其中，R(C)称为棋盘C的棋盘多项式，表示空集（即无棋盘）,r0(C)表示有盘无子。例如，对上面的棋盘C的棋子多项式为R(C)=r0(C)x0+r1(C)x1+r2(C)x2=1+4x+3x2

假设给定一棋盘C，现任选其中的某个格子定义两个棋盘记号Ce和Ci。令Ce表示C取掉该格剩余的棋盘，Ci表示取掉该格所在行及所在列后剩余的棋盘。则用k枚棋子对棋盘C进行布局的方案，可按选定格子放子与不放子划分为两类：第一类：对选定格子中放一枚子，其禁位放法有rk-1(Ci)种;

第二类：对选定格子中不放棋子，其禁位放法有rk(Ce)种。显见，对棋盘C，总的布局方案为选定格子有子的方案与选定格子无子的方案之和。由加法原理应有由此，棋盘C的棋子多项式R(C)可整理为

这一重要的递推关系式，给出了把部分复杂棋盘的棋盘多项式分解为简单棋盘的棋盘多项式进行求解的方法。例如：

值得注意的是，当棋盘C由互相分离的两部分C1和C2组成时（即C1和C2不存在同行同列的公共格子），有从而

注意到上式的乘积中，高于n次幂的项为零。于是有R(C)=R(C1)R(C2)

此式与R(C)=xR(Ci)+R(Ce)联合或分别使用，即可将任意复杂棋盘化简并求解。例如

3.有禁区的排列设有一4个元素的排列a1a2a3a4，并限制a1≠1，a2≠1,a2≠4,a3≠2,a4≠3。可以把这些限制画成一个棋盘图，用带阴影的格子表示禁区，如图4.4.3所示。4个元素有禁位的排列问题从而转化为4枚棋子放到有禁区的棋盘上的问题。图4.4.3有禁区棋盘

定理n个元素有禁位的排列t=n!-r1(C)(n-1)!+r2(C)(n-2)!-…+(-1)nrn(C)

其中C为禁区所组成的棋盘，rk(C)为k枚棋子在C上的放法数。

证明令pi表示第i枚棋子放到禁区所组成的棋盘C上。由于1枚棋子放到C上的方法数为r1(C)，而剩余的n-1枚棋子没有限制条件，其排列数为(n-1)!，故至少有一枚棋子放到C上的方法数为r1(C)(n-1)!。同理，有2枚棋子放到C上的方法数为r2(C)(n-2)!……最后根据包含排斥原理，n枚棋子无一放入禁区的方法数应为

例6上面提出的禁位排列问题,其禁区组成的棋盘C可分解为两个简单棋盘C1,C2,如图4.4.4所示。图4.4.4例6图利用公式R(C)=R(C1)R(C2)，可得R(C)=(1+3x+x2)(1+2x+x2)=1+5x+8x2+5x3+x4

即r1=5，r2=8，r3=5，r4=1。根据定理，问题所求的排列数应是t=4!-r1(C)·3!+r2(C)·2!-r3(C)·1!+r4(C)=4!-5×3!+8×2!-5×1!+1=66个满足条件的排列为231423413214324142314312

例7错排问题在这里可转化为一个在n×n的棋盘上,以对角线上方格为禁区棋盘C的布局问题。如以图4.4.5为禁区棋盘C的棋子多项式为其中,对应可得因此，错排数为

例8甲，乙，丙，丁4个人对应有A，B，C，D4项工作，但甲不会做A，乙不会做A和B，丙不会做B和C，丁不会做C，若要求每人必须做一项不同的工作，问有多少不同的安排方案？

解该问题可归结为禁位排列问题，首先求出以禁区为棋盘的棋子多项式（如图4.4.6所示）：对应可得r0(C)=1,r1(C)=6,r2(C)=10,r3(C)=4再根据有禁区的排列数定理可得t=4!-6×3!+10×2!-4=4图4.4.6例8图4.5树的计数

定义1设G=(V,E)为一无向图，其中V为图G的点集，E为图G的边集。若G连通且无圈，则称G为树（Tree），常记作T=(V,E)。

命题1

设G=(V,E)为一图，|V|=n,|E|=m，则G为树当且仅当G连通且m=n-1。

推论在p个树构成的森林G=(V,E)中，若|V|=n，则p=n-|E|。

定义2设G=(V,E)为一图，对G中任一点v∈V,v的度（数）定义为与v关联的边的条数，记作d(v),d(v)=1的v称为悬挂点，相应的与v相连的边称为悬挂边。

命题2设G=(V,E)为一图，|V|=n,|E|=m,对vi∈V(i=1，2，…，n),d(vi)=di为结点vi的度，则

证明因G中每条边都可向顶点贡献2度，故m条边提供的度之和 为2m。

推论1设T=(V,E)为一树，V={v1,v2,…,vn}，|E|=m,则

推论2任一顶点数不少于2的树T=(V,E)，至少有两条悬挂边（或两个悬挂点）。

命题3

（Moon）设T(n;d1,d2,…,dn)为以v1,v2,…,vn为顶点，以d(v1)=d1,d(v2)=d2,…,d(vn)=dn为度数的树的数目,则

证明不失一般性，可假定d1≥d2≥…≥dn，否则可重新编号。由命题2的推论2得dn=1，即vn为一悬挂点。令