组合数学.

2024年2月6日发(作者：数学试卷比较基础的是哪种)

组合数学

第一章 排列和组合

1.1 计数的基本原则

相等原则：设A、B是两个有限集，如果存在由A到B上一个一一对应映射（即双射），则 |A|=|B|.

加法原则：设A是有限集，AikA(i1,2,...k),

如果

AAi 且

AiAjφ（1≤i＜j≤k），则

Ai1Ai1ki.

★ 定理1.1 已知做一件事要经过两个步骤，完成第一个步骤的方法有m种，完成第一个步骤之后，完成第二个步骤的方法有n种，则做这件事情的方法共有mn种.

★ 定理1.2（乘法原则）：已知做一件事情要依次经过k个步骤，且在已完成前面i-1（1≤i≤k）个步骤的情况下，完成第i个步骤有ni种方法，则做这件事情的方法共有

n1n2nkni 种.

i1k

1.2 排列

n元集的r-排列

☻ 定义1.1 设A是n元集，如果序列a1a2ar中的r个元

a1,a2,,ar都属于A且彼此互异，则称序列a1a2ar是n元集A的一个r-排列，并称ak（1≤k≤r）是该r-排列的第k个元，或称ak在该r-排列中排在第k位.

☻ 定义1.2 n元集A={a1,a2,,an}的n-排列称为n元集A的一个全排列，亦称为由a1,a2,,an作成的一个全排列.

定理1.3 设n，r（n≥r）是正整数，以P(n,r)表示n元集的r-排列的个数，则

P(n,r)n(n1)(nr1)推论1.1 n元集的全排列的个数为n！

n元集的r-可重复排列

n!

(nr)!☻ 定义1.3 设A为n元集，如果序列a1a2ar的元素都属于A，则称序列a1a2ar是n元集A的一个r-可重复排列.

★ 定理1.4 n元集的r-可重复排列的个数为nr.

多重集的排列

☻ 定义1.4 由n1个a1,n2个a2,,nk个ak组成的集合M记为M{n1a1,n2a2,,nkak}，M称为多重集，也称M是一个n-多重集，其中nn1n2nk.

☻ 定义1.5 设M{n1a1,n2a2,,nkak}，是集合A{a1,a2,,ak}的一个n-可重复排列且中有n1个a1,n2个a2,,nk个ak，则称是多重集M的一个全排列，此时也称是由n1个a1,n2个a2,,nk个ak作成的全排列。

★ 定理1.5 多重集M{n1a1,n2a2,,nkak}的全排列的个数为

(n1n2nk)!

n1!n2!nk!

☻ 定义1.6 设M{n1a1,n2a2,,nkak}和A{s1a1,s2a2,,skak}都是多重

集，且0sini（1≤i≤k），则称A是M的一个子集，如果s1s2skr，则称A是M的一个r-子集.

☻ 定义1.7 设M{n1a1,n2a2,,nkak}是多重集，是M的某个r-子集的全排列，则称是M的一个r-排列.

1.3 T路的计数

☻ 定义1.8 由p×q个单位正方形拼成的长为p，宽为q的长方形叫做一个p×q棋盘.

★ 定理1.6 沿p×q棋盘上的线段，由顶点A到顶点B的最短路的条数为

☻ 定义1.9 在Oxy坐标平面上，横坐标与纵坐标都是整数的点叫做整点.由任一个整点（x，y）到整点（x+1，y+1）或（x+1，y-1）的有向线段叫做一个T步.

☻ 定义1.10 由整点A到整点B的一条T路是指由若干个T步组成的起点为A、终点为B的有向折线.

★ 定理1.7 如果存在由整点A(a,)到整点B(b,)的T路，则：

① b ＞ a.

② b - a ≥ │β-α│.

③ a + α与 b + β的奇偶性相同.

上述三给条件合称为T条件.

★ 定理1.8 设整点A(a,)与整点B(b,)满足T条件，则由A到B的T路的条数为(pq)!.

p!q!(ba)!.

baba()!()!2222

★ 定理1.9（反射定理） 设整点A(a,)与整点B(b,)满足T条件，且0,0,ba,则由A到B且经过x轴（即与x轴有交点）的T路的条数等于由A\'(a,)到B的T路的条数，为(ba)!

baba()!()!2222

★ 定理1.10 设整点A(a,)与整点B(b,)满足T条件，且

0,0,ba,则由A到B且不经过x轴的T路的条数为(ba)!(ba)!

babababa()!()!()!()!22222222

★ 定理1.11 （1）由点O（0,0）到点V（2n，0），中途不经过x轴且位于上半平面的T路的条数为(2n2)!.

n!(n1)!(2n)!.

(n1)!n!（2）由点O（0,0）到点V（2n，0）且位于上半平面的T路的条数为令Cn

(2n2)!(n1,2,3,),Cn叫做Catalan（卡塔兰）数

n!(n1)!★ 定理1.12 以S2n表示满足条件

xxxn2n121xxxj(j1,2,,2n1)12j2xj0或1（j1,2,,2n）

的解(x1,x2,,x2n)的集合，则

S2nCn

★ 定理1.13 以T2n表示满足条件

(2n2)!.

n!(n1)!xxxn2n121xxxj(j1,2,,2n1)

12j2xj0或1（j1,2,,2n）的解(x1,x2,,x2n)的集合，则

T2nCn1

1.4 组合

n元集的r-组合

☻ 定义1.11 集合A的含有r个元素的子集称为A的一个r-组合.

设A{a1,a2,,an}是n元集，则A的任一个r-组合可表成{ai1,ai2,,air}，

其中i1,i2,,ir均是整数，且

1i1(2n)!.

(n1)!n!i2irn.

r以

Cn 或

 表示n元集的r-组合的个数，简称为组合数.

nr

★ 定理1.14 设n是正整数，r是非负整数，则

0,当rn时；n

rn！,当0rn时.r!(nr)!

n元集的r-可重复组合

☻ 定义1.12 从集合A中可重复地选取r个元作成的多重集，称为集合A的一个r-可重复组合.

★ 定理1.15 n元集的r-可重复组合的个数为

nr1.

rnr1推论1.2 不定方程

x1x2xnr 的非负整数解的个数为r.

推论1.3 不定方程

x1x2xnrrn 的正整数解的个数为r1.

rnnn!应用公式

kk!(nk)!nk0 ，容易证明下面两个定理

★ 定理1.16 （1）

nknnk0

nknn1n1 （2）

kkk1nk1

 （3）

nknn1nk1

kk1nnk1nnk1 （4）

kkk1nnn1nk0

 （5）

knkkn★ 定理1.17

m

多项式定理

★ 定理1.18（多项式定理）设n是正整数，x1,x2,,xk是任意k个实变数，则

mnkknkmknmk

(x1x2xk)nn1n2nknni(i1,2,,k)是非负整数n!nkn2x1n1x2xkn1!n2!nk!.

nknk(xy)推论1.4 （二项式定理） 设n是正整数，x和y是任意实数，则kxy.

k0nnkx推论1.5 设n是正整数，x是任一实数，则(1x).

knk0nn推论1.6 设n是正整数，则

n2（1）kk0nnnk(n0).

n（2）(1)k0k0

1.5 二项式反演公式

二项式反演公式

(n1).

引理1.1 设n，s是非负整数且ns，对于每个非负整数k(skn)，ak,i(is,s1,,k)是复数，则ak,iak,i

ksisiskinknn★ 定理1.18 （二项式反演公式） 设

ann0 和

bnn0 是两个数列，s是非负整数，如果对任意的不小于s的整数n，都有anksnk都有bn(1)ak.

ksnnnkbk，则对任意的不小于s的整数n。nk有限集的覆盖

设A是n元集，以P*(A) 表示A的全体非空子集所成之集，则P*(A)2n1，P*(A)共有22n11个非空子集.

F☻ 定义1.13 设A是n元集，P*(A)，如果盖.

FA，则称是n元集A的一个覆☻ 定义1.14 如果是n元集A的一个覆盖且m，则称是n元集A的一个m-覆盖.

多元二项式反演公式

★ 定理1.20 设

s1,s2,,sr 是r个给定的非负整数，又设对任意的r个非负整数n1,n2,,nr(nisi,i1,2,,r)，f(n1,n2,,nr)及g(n1,n2,,nr)都是实数，且f(n1,n2,,nr)sikinii1i1,2,,rrnikg(k1,k2,,kr).

isi,i1,2,,r)，有则对任意r个非负整数n1,n2,,nr(nig(n1,n2,,nr)

sikinii1i1,2,,r(1)rnikinikf(k1,k2,,kr).

i