组合数学归纳

组

合

数

学

1

组合数学部分知识点归纳 作者 曾志伟

2

组合数学部分知识点归纳 作者 曾志伟

组合数学归纳

第一章 排列和组合

§1.1计数的基本原则 一、 相等原则 二、 加法原则 三、 乘法原则

§1.2 排列

一、n元集的r-排列 1、n元集的r-排列个数：

n!nr!

2、n元集的全排列个数：n! 二、n元集的r-可重复排列 1、n元集的r-可重复排列个数：nr 三、多重集的排列

1、多重集Mn!1•a1,n2•a2,....,n1n2...nkk•ak的全排列数为：

nn1!n2!...nk!2、多重集Mn1•a1,n2•a2,....,nk•ak的r-子集的全排列个数： ⑴列出多重集M的r- 子集：M1,M2,...,Ms ⑵分别求出多重集Mi的全排列个数，再求和

§1.4 组合

一、n元集的r-组合

1、n元集的r-组合个数：nn!rr!nr!

二、n元集的r-可重复组合

1、n元集的r-可重复组合个数：nr1 r

2、不定方程x...xnr11x2nr的非负整数解的个数： r

3、不定方程x...xr11x2nr的正整数解的个数：rn



3

组合数学部分知识点归纳 作者 曾志伟

三、组合数的基本性质

n nnn1n11.1、 1.2、

knkk kk1nnn1nnk1 n1.3、 1.4、

kk1kk1kknnn11.5、

knk knmnnk2、

mkkmk四、多项式定理

1、多项式定理：x1x2...xknn1n2...nkn(ni0,i1,2...,k)n!n2x1n1x2...xknk

n1!n2!...nk!2、二项式定理：xynnnknkxy k0knn3、推论：1xxk

k0knnn4、推论1：112n

k0knknn推论2：1110

k0kn五、组合恒等式（e.g.）

n1in例1.18（P24） 

kii0kknk例1.19（P25） 1k0

k1kn例1.20（P25） n1n12n11 n1k0k1knnk例1.21（P25） 1kmnk1,若nm; km0,若nm. 4

组合数学部分知识点归纳 作者 曾志伟

sn1例1.22（P26） 

smmm1nnn2nnmnm例1.23（P26）  kn

krkrk0k0r2例1.24（P27） k1n1kk1nn1 kk1knn2n例1.25（P28） 

k0kk1n1n1§1.5 二项式反演公式

1、二项式反演公式：

nnnkn 若anbk，ns 那么bn1ak，ns.

kskskkn

第二章 容斥原理及其应用

1、容斥原理：

⑴设S是有限集，AiS,i1,2,...,n，则

ni1Ai1k1nk11i1...iknAi1Ai2...Aik

⑵设S是有限集，AiS,i1,2,...,n，则

nSi1AiS1k1nk1i1...iknAi1Ai2...Aik

⑶设S是有限集，a1,a2,...,an是n个性质，以Nai1ai2...aik表示S中同时具有性质a1,a2,...,an的元素的个数，以Na'i1a'i2...a'ik表示S中同时不具有性质

a1,a2,...,an的元素的个数ai1,ai2,...,aik是a1,a2,...,an一个k组合，则

Na'1a'1...a'nS1k1nk1i1...iknkNai1ai2...aik

2、容斥原理的应用：

⑴n元集重排不保位的重排数：Dnn!k0nn1k!

⑵DnnDn11 ⑶Dnn1Dn1Dn2

5

组合数学部分知识点归纳 作者 曾志伟

第三章 递推关系

§3.1 差分

1、△=E - I；E=△+ I 2、牛顿公式：

n EIj

j0jnnnEI1nj0nnnjnjE jn3、多项式的差分

设fn是n的m次多项式，则k0n1jfkf0

j1j0m

§3.2 递推关系

1、常系数齐次递推关系

una1un1...akunk,nk 已知：u0,u1,...,uk1

求解步骤：

①解出xka1xk1...ak1xak的特征根1,2,m;mk，其中i为ei重特征根； ②递推关系具有通解：unci1mei1ncn..cn i1i2ieii③把u0,u1,...,uk1代入通解，分别求出k个cij的值即可。 2、常系数非齐次递推关系

una1un1...akunkfn,nk 已知：u0,u1,...,uk1

求解步骤： ①解出xa1xkk1...ak1xak的特征根1,2,m;mk，其中i为ei重特征根；

mei1nuccn..cnn②齐次递推关系具有通解：i1i2ieii

i1③非齐次递推关系特解的求法

1）若fn是n的m次多项式，且数字1为齐次递推关系特征方程的s重特征

*smm1unAnAnmm1...An根，则特解具有形式n1A0，并把它代入非齐

次递推关系un值；

a1un1...akunkfn,nk 求出A0,A1,...,Am的

6

组合数学部分知识点归纳 作者 曾志伟

2）若fncan，且a为齐次递推关系特征方程的s重特征根，则特解具有 形式

*unAnsan，并把它代入非齐次递推关系

una1un1...akunkfn,nk求出A的值；

3）综上，1）和2）的特解已求，至此，unmci1mei1n*cn..cnui1i2iein i*④把u0,u1,...,uk1代入unci1ci2n..cieinei1inun，求出k个cij的值即可。

i1

§3.3 斐波那契数

1、斐波那契数的递推关系：fnfn1fn2，初值f0f11；

1152、斐波那契数的通项公式：fn25n111525n1

nknnk3、斐波那契数的通项公式（级数形式）：fn

k0kk0k4、斐波那契数的应用：

①以gn表示登上n级台阶（其中每步只能登1级或2级）的不同方法数，令

n2g01有 gnfn ②定理：fkfn21

k0n③定理：fnmfnfmfn1fm1 （应用于求解较大的斐波那契数）

④阵列I的SDR数

1阵列I= 1223

n2n1n1n 的SDR数unfn； n7

组合数学部分知识点归纳 作者 曾志伟

§3.4 两类Stirling数 1、第一类Stirling数

定义：xnxx1x2...xn1S1n,kxk，S1n,k为第一类Stirling

k0n数.

性质：S1n1,kS1n,k1nS1n,k

证：

xn1xnxnxxnnxnS1n1,kS1n,k1nS1n,k

组合意义：恰可表示成k个互不相交的轮换乘积的n元置换一共有1种.

2、第二类Stirling数

定义：xnS1n,kxxS2n,kxk，S2n,k为第二类Stirling

knk0k0nnnkS1n,k数.

性质：S2n1,kS2n,k1kS2n,k

证：

n1nnSn1,kx2k0nk0kxn1x•xx•S2n,kxkS2n,kxkkxknk0k0n1nS2n,kxk1kS2n,kxkS2n,k1xkkS2n,kxkk0k1k0nS2n1,kS2n,k1kS2n,k组合意义：n件相异物放到k个相同的盒子的非空方法有S2n,k种.

第四章 生成函数

§4.1 常生成函数

1、定义：an为一数列，则Atantn为an的常生成函数

n02、常生成函数级数函数与初等函数的转化公式： 定理4.2 1atmmnnat n0nmmm1m2...mn1推广定义：

n!n

8

组合数学部分知识点归纳 作者 曾志伟

转化公式： 1tt；1atat；1tnnnn0n011knk1nt ； n0n1atknk1nn112n2n1/2；at1t1t 2n1nn1n0nn02 转化应用：an与Atantn的初等形式的相互求解

n03、组合意义：

以Mk表示n元集中元素ai的可重复的次数值所组成的集合，则n元集r-有的可重复组合数为At

§4.3 指数生成函数

nk1xkMktxk展开式中tr的系数.

antn1、定义：an为一数列，则Et为an的指数生成函数

n0n!rntn2、指数生成函数级数函数与初等函数的转化公式：e

n!n0rtantn 转化应用：an与Et的初等形式的相互求解

n0n!3、组合意义：

以Mk表示n元集中元素ai的可重复的次数值所组成的集合，则n元集r-有的可重复排列数为At数.

第五章 整数的分拆

§5.1 分拆的计数

1、分拆数Prn的递推公式：

n定理5.1： P2n

2nk1xkMktxktr展开式中的系

r!xk!定理5.2： PrnPknr,nr

k1r 9

组合数学部分知识点归纳 作者 曾志伟

定理5.3： PrnPr1nrkr1,nr2

k1nrk2k0,n2Pn定理5.4： k 22kkkkPnnk22nkn引理5.1：P3n,n4 3k12nkmnm 引理5.2：2k12mn32n23定理5.5： P3n 122、分拆数Prn的递推关系：PknPk1n1Pknk §5.2 完备分拆

1、n-完备分拆的个数：

k12p2...pk 设n+1的质因数分解式为n1p1，则n-完备分拆的个数为：

N1..km11j1mmjji1 i1ik2、一个n-完备分拆nq11q1q21q1q2q31...q1q2..qt1qt1对应着一个n1q1q2...qt的分解 3、部分数最小的完备分拆

k12p2...pk 设n+1的质因数分解式为n1p1，则部分数最少的n-完备分拆的

k部分数为：部分数最少的n-完备分拆的个数为：ipi1，

i112...k!1!2!...k!

第六章 鸽笼原理

鸽笼原理：

设A是m（m>1）元集，AiAi1,2,...,n且

m11. k1kn，使得Akn

10

nAiA，则必有正整数

i1组合数学部分知识点归纳 作者 曾志伟

组合数学的七类问题

一、n件相异物放到m个不同的盒子

1、n件相异物放到m个不同的盒子的不同方法数：mn

2、n件相异物放到m个不同的盒子，且每个盒子至少有1件的不同方法数： 解：设n件相异物放到m个不同的盒子的不同方法之集为S，则Smn，以

Nai1ai2...aik表示S中第i1,i2,..,ik个盒子都为空的元素的个数，以Na'i1a'i2...a'ik表示第i1,i2,..,ik个盒子都不为空的元素的个数，其中（i1,i2,..,ik为1,2,..,m的一个k-子集，1km），根据容斥原理，题目所求的个数为：

Na'1a'1...a'mS1k1mk1i1...ikmNai1ai2...aik

另一方面，由于第i1,i2,..,ik个盒子都为空，故Nai1ai2...aikmk，因此

Na'1a'1...a'mS1k1mnmkn1i1...ikmmknkmn m1mkk1km1kmn 1mkk0k

即n件相异物放到m个不同的盒子，且每个盒子至少有1件的不同方法数为：

kmn1mkm!S2n,m k0km1

二、n件相异物放到m个相同的盒子

1、n件相异物放到m个相同的盒子的不同方法数为：

m1i11kin 1ikS2n,i

i1i!k0i1i!km2、n件相异物放到m个相同的盒子，且每个盒子非空的不同方法数为：

1m1kmn 1mkS2n,m

m!k0k

11

组合数学部分知识点归纳 作者 曾志伟

三、n件相同的物体放到m个不同的盒子

1、n件相同的物体放到m个不同的盒子的不同方法数为：

mn1不定方程x1x2...xmn的非负整数解的个数，即

 n2、n件相同的物体放到m个不同的盒子且每个盒子非空的不同方法数为：

n1xx...xn不定方程12的正整数解的个数，即m

nm3、n件相同的物体放到m个不同的盒子，以Mii1,2,..m表示第i个盒子可以放的个数的集合，求不同放法的种数： 解：设所求为N，则N等于Atmk1xkMktxk的展开式中tn项的系数.

四、n件相同的物体放到m个相同的盒子

1、n件相同的物体放到m个相同的盒子的不同方法数为：

NPminPrn

i0r1m1m2、n件相同的物体放到m个相同的盒子，且每个盒子非空的方法数为：Pmn

五、把Mn1•a1,n2•a2,....,nk•ak抽出元素放到m个不同的盒子 1、把Mn1•a1,n2•a2,....,nk•ak放到m个不同的盒子的不同方法数： 解：设所求方法数为N，根据题意，分k步完成：

第ii1,2,...k步的操作为：把ni个ai放到这m个不同的盒子，设第j个盒子有xj个ai，则x1x2...xkni，即把ni个ai放到这m个不同的盒子的不同方

kni1法数等于不定方程x1x2...xkni的非负整数解的个数，即；

 nimni1根据计数的乘法原则，N

ni1ik

12

组合数学部分知识点归纳 作者 曾志伟

2、把Mn1•a1,n2•a2,....,nk•ak放到m个不同的盒子且盒子非空的方法数：

mni1解：设所求为N，设题1的方法之集为S，则S，以Nai1ai2...aisi1 nik表示S中第i1,i2...is个盒子都为空的元素的个数，根据容斥原理，有

NNa'1a'1...a'mS1s1ms1i1...isnNai1ai2...ais

另一方面由题1可知，Nai1ai2...aismsni1，因此

ni1ikmsni1 ns11i1...isni1ikkmmni1msni1sm1  ns ni1i1iis1km1msni1sm1s ns0i1iNNa'1a'1...a'mS1msk

3、把Mn1•a1,n2•a2,....,nk•ak抽出r个放到m个不同的盒子的不同方法数： 解：设所求为N ，N为Mn1•a1,n2•a2,....,nk•ak的所有r-子集

x1•a1,x2•a2,...,xk•ak|x1x2...xkr放到

km个不同的盒子的不同方法数之

和，由题1

mxi1，事实上得先列出知：N xx1x2...xkri1i每一个r-子集x1•a1,x2•a2,...,xk•ak|x1x2...xkr，有点麻烦。

4、把Mn1•a1,n2•a2,....,nk•ak抽出r个放到m个不同的盒子且盒子非空的不同方法数：

解：与题3同理，设所求为N，则利用题2的结论，有

mkmsxi1N1，事实上得先列出每一

s xx1x2...xkrs0i1im1s个r-子集x1•a1,x2•a2,...,xk•ak|x1x2...xkr，有点麻烦。

13

组合数学部分知识点归纳 作者 曾志伟

六、把Mn1•a1,n2•a2,....,nk•ak抽出元素放到m个相同的盒子 1、把Mn1•a1,n2•a2,....,nk•ak放到m个相同的盒子的不同方法数 解：由于n件相同的物体放到m个相同的盒子的不同方法数为：Pmin

i0m1故分k步，第i步把ni个ai放到m个相同的盒子，不同方法数为Pminj；

i0m1设所求为N，根据计数的乘法原则，NPminj

j1i0km12、把Mn1•a1,n2•a2,....,nk•ak放到m个相同的盒子且盒子非空的不同方法数 解：n件相同的物体放到m个相同的盒子且盒子非空的不同方法数为Pmn

具体参照第五类中的题2，运用容斥原理，哥撑不下去了。

3、把Mn1•a1,n2•a2,....,nk•ak抽出r个放到m个相同的盒子的不同方法数：

解：

Nx1x2...xkrj1i0Px

mijkm14、把Mn1•a1,n2•a2,....,nk•ak抽出r个放到m个相同的盒子且非空的方法数： 解：把题2的结论中改为ni改为xi，前面再配多一个

x1x2...xkr。

七、对n个数进行操作，必有s个数满足特定的性质（灵活应用鸽笼原理）

七类组合问题的概述 1、第一类主要应用容斥原理，不同的性质ai对应着第i个盒子的不同，难度在于求Nai1ai2...aik的值

2、第二类只有非空的方法才是对应的第一类的方法数除以m！

3、第三类是最容易解决的，因为第三类无论给定何种，都可以应用常生成函数求解

4、第四类主要应用整数的分拆

5、第五、六类主要涉及到多重集，要转化成前四类 6、第七类要神一般的运用鸽笼原理。

14

