考前复习-p考试安排

考试安排时间：1月13日晚6点半-9点地点：建馆报告厅答疑时间：–

1月10日下午2pm-5pm，东主楼8-402–

1月13日下午2pm-4:30pm，东主楼8-402考试题型5道解答或者证明题,一题中可能有多问五章内容不考全排列生成:

myc@mai

考卷上请写明学号，

，

号码，1第一章排列与组合计数基本原理–加法法则:若|A|=m,|B|=n,AB=

,则|AB|

=m

+n在加法法则中要注意事件A

和事件B

的互斥乘法法则:若|A|=m,|B|=n,AB={(a,b)

|

a

A,b

B},

则|A

B|=

m·

n在乘法法则中要注意事件A

和事件B

的相互独立性排列–从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当

r=n时称为全排列。(n-r+1)–P(n,r)=n(n-1)······组合–从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示，–C(n,r)=P(n,r)/r!=n!/(r!(n-r)!)允许重复的排列(多重集排列):–求r1个1，r2个2，…，rt个t的排列数，设r1+r2+…+rt=n,设此排列数为P(n;r1,r2,…,rt),对1，2，…，t分别加下标，得到P(n；r1,r2,…,rt)·r1!·r2!·…·rt!

=

n!∴P(n；r

,r

,…,r)圆周排列–从n个中取r个的圆排列的排列数为P(n,r)/r,项链排列2≤r≤nP(n,r)/2r

,

3≤r≤n向上两种方式放置各–在圆排列的基础上，正面向上和个数是同一个排列。n!r1!r2!…rt!n1

2 t)=

————

=(

r1

r2

…

rt允许重复的组合(多重集的组合)n个不同的元素中取r个做允许重复的组合,其组合数为C(n+r-1,r)线性方程非负整数解x1+x2+…+xn=b的非负整数解的个数C(n+b-1,b)不相邻的组合n个数中取r个作不相邻的组合,组合数为C(n-r+1,r)多重集的组合给三个孩子发水果,一共12个一样的苹果,每个孩子至少有一个水果,问有多少种分法?解:设分给第i个孩子的水果数为xi,

xi≥1x1+x2+x3=12令y1=x1-1,y2=x2-1,y3=x3-1y1+y2+y3=9

yi≥0非负整数解的个数为C(9+3-1,9)=55不考的内容排列，组合的生成Stirling公式第二章递推关系与母函数二项式定理(x+y)n=∑C(n,k)xn-kyk(1+x)n=

∑C(n,k)xn-k多项式定理k=0-nk=0-n–

(x1+x2+…+xt)n=∑C(n;r1,r2,….rt)x1r1x2r2…xtrtr1+r2+…+rt=n因式分解一元二次方程求解多项式长除法母函数指数型母函数对于序列a0

,a1

,a2构,造,一函数：0

1

2G(

x)

a

a

x

a

x

2

,称函数G(x)是序列a0

,a1

,a的2

,母函数求解组合问题求解排列问题对于序列，函数a0

,

a1

,

a2

,

ak2!

3!xkk!1!G

(x)

a

a1

x

a2

x2

a3

x3e

0称为是序列的指数型母函数a0

,

a1

,

a2

,常用母函数数列{1}n

≥0

母函数1/(1-x)=

1+x+x2+…指数型母函数ex数列

{cn}n≥0

母函数1/(1-

cx)=1+cx+c2x2+…

sin

x

x

3!

5!(1

x)2指数型母函数ecx1

2x

3x2

4x3

1k

0

21

3x

6x2

10

x3

(kk

02!x33!x5

,e

1

x

x2

x3

x递推关系Hanoi问题Fibonacci数列铺砖N位序列中符合某些性质的排列数放球问题………..线性常系数递推关系定义如果序列an

满足

Ck

ank

0,

C1an1

C2

an2an2

5

1

11002

5

2C1

,

C2

,Ck及

d0

,

d1

,dk

1是常数，Ck

0

，则2

5

1称为

an

的k阶常系数线性递推关系，2

5

2称为an

的初始条件，C(x)

xk

C

xk

1

C

x

C1

k

1

k称为an

的特征多项式线性常系数递推关系确定特征多项式判断特征方程根的情况非重根共轭复根多重根利用系数an的前若干项求解待定系数确定an14总结线性常系数递推关系根据特征多项式C(x)的非零解的情况1)有k个不同非零实数解C

x

x

a1

x

a2

x

ak

a

l

an

l

an

l

ann

1

1

2

2

k

k其中l1

,l2

,,lk

,是待定系数2)有一对共轭复根和时，i

e1i

e2na

A

cos

n其中A，B是待定常数。3)有k重根。不妨设1是k重根。是k个待定常数。n1k

1(A0

A1n

Ak

1n

)

或0

1

k

1其中A

,A

,,Ann12

311

2

3)k

1

...

A

n

A

n

A

n

(

A0

Ak

1母函数法求多重集的组合给三个孩子发水果,一共12个一样的苹果,每个孩子至少有一个水果,问有多少种分法?解:母函数为,G(x)=(x+x2+x3+x4+…)(x+x2+x3+x4+…)(

x+x2+x3+x4+…)•

=(x/(1-x))3求x12的系数,即1/(1-x)3中的x9的系数.x=1是三重根2a0=1,a1=3,a2=3+3=6A=1;

A+B+C=3,A+2B+4C=6A=1

B=1.5

C=0.5an=1+1.5n+0.5n2a9=1+1.5*9+0.5*81=55则n位数/字母组成排列求n位二进制数相邻两位不出现11的数的个数。第n位为0或1:是0，有an-1；是1，则n-1位为0,有an-2.设n-1位不出现11的个数为an

1n-2位不出现11的个数为an

2n位不出现11的个数为anan

an

1

an

2an

an

1

an

2

0,

a0

1,

a1

2,

a2

3特征方程为25

,

x

1

52

x

1

021

x

1

x2设Ax

n

Bx

n1

2代入得

B

A

105

3

55

3

510n(10

25)n

5

3

5

1

5)n(10

2a

5

3

5

1

母函数和递推关系例题：铺砖题方砖1*1，长砖1*2，给1*n的路铺路面，求1）方案数，2）总砖数1）设方案数为an,以最后一块砖分类

an1

an2ana0

1，a1

1，a2

2，a3

3，a4

5，a5

8an-1an-2an

Fn1

51

(

n1

n1

)2）总砖数设总砖数为bn,以最后一块砖分类an

an1

an2an

Fn1

anbn

bn1

an1

bn2

an2

bn1

bn2。bn-1

。。an-1。bn-2

。。an-2

(Cn)

n特解是(An)

n

(Cn)

nα,β是特征根，m=1bn的形式是(An)n(

An

B

n

(Cn

Db

代1立方程组太复杂(

An

B

n

(Cn

D

(

A(n

1)

B)

n1

(C

(

A(n

2)

B)

n2

(C(

n1

n1

)511(

n1

n1

)

(

A(n

1)

B)

n1

(C(n

1)

D)

n1

(

A(n

2)

B)

n2

(C(n

2)

D)

n22

1

51

5

2

2

1

5

,1

5

2

(

An

B)

n

(Cn

D)

n

n

n1

n2

,

n

n1

n255An

n

A(n

1)

n1

A(n

2)

n2

1

n15An

n

An

n1

A

n1

An

n2

2

A

n2

1

n1

05A

n1

2

A

n2

1

n15C

n1

2C

n2

1

n1251C

5A

2

A

1

35A

1

25A

1

25

5B

1

5C

1

25

5D

1

n5

51

)

n55

5

512

(

1

2

n

b

(

n

1

)

n0b

0代入得B

D

0

)

)

B(33151b

1代入得1

(不考内容第一类Stirling数Catalan数第三章容斥原理和鸽巢原理容斥原理棋盘多项式有限制的排列:如错排广义容斥原理鸽巢原理不考内容Ramsey数反演容斥原理容斥原理:...nnAii

1

i

1

j

iA1

A2

...

An

AiAjAjAk

...nA

ni=1

j>i

k>j+

Ai(4)A1

A2A2

...12

(1)n

AAnAn

1(1)n

1

A

A1

2...

An

N

A1n

ni

1i

1

j

iAi

AjAj

Ak

...

N

AinA...

A

ni=1

j>i

k>j-

Ai(5)整数整除求从1到500的整数中被3和5整除但不被7整除的数的个数.解设A3：被3整除的数的集合

A5：被5整除的数的集合

A7：被7整除的数的集合所以｜A7∩A5∩A3｜＝｜A3∩A5｜－

｜A7∩A5∩A3｜＝500/3*5－

500/3*5*7

＝33－4＝29求1-10,000中不是完全平方数,且不是完全立方数的所有整数个数解:A1为完全平方数集合1002=10000,所以|A1|=100A2为完全立方数集合213=9261 223=10648,

所以|A2|=21A1∩A2为完全6次方数集合

46=4096,56=15625,所以|A1∩A2|=4所求数为10000-(100+21)+4=9883三论多重集组合6个a,6个b,3个c中取12个的组合数?可以转化为xa+xb+xc=12,

0≤

xa≤6,

0≤

xb≤6

0≤

xc≤3S为无限个a,b,c中取12个的集合,共C(12+3-1,12)=91A1=至少7个a;A2=至少7个b;A3=至少4个c|A1|=|A2|=C(5+3-1,5)=21;

|A3|=C(8+3-1,8)=45|A1∩A2|=0;

|A1∩A3|=

|A2∩A3|=C(1+3-1,1)=3所求组合数=91-(21+45+21)+(0+3+3)=10令rk（C）表示k个棋子布到棋盘C上的方案数。定义

设C为一棋盘，称R(C)=

∑

rk(C)

xk为C的棋盘多项式。k=0n规定r0(C)=1，包括C=Ф时。定理

设

ri

为

i个棋子布入

的方案数，i内=1,2,3,···,n。有

的布子方案数（即不布子的方案数）为n!

－r1(n－1)!

＋

r2(n－2)!－···

＋(－1)nrn解

可得如下的带 的棋盘其中有阴影的表示

．A

B

CⅠⅡⅢ的棋子多项式为：R(

)=R( )R(

)=(1+x)(1+3x+x2

)=1+4x+4x2+

x3故方案数＝3!－4·2!+4

·1!－1

·0!＝1A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有(n+1)/n=2个鸽子。”出现ak

+ak+1

+···+al累加,多半要构造Sj

=

∑aii

=1出现奇偶性,整除,多半要取mod整点问题反证法内点问题多次利用鸽巢j证明：在平面直角坐标系中，33个整点中必有9个整点的重心仍是整点。证：先证明9个整点中必有3个整点的重心的仍是整点。（证明方法请参照整点问题ppt）33个整点中必有9个3点组，每组的重心仍是整点。33个中有3个整点为重心整点，剩下30个，取3个整点为重心整点，剩下27个，取3个整点为重心整点，。。。剩下9个，取3个整点为重心整点，而这9个重心中必有3个的重心仍是整点，从而就证明了33个整点中必有9个整点的重心仍是整点。9组221在边长为1的正方形内任取5个点试证22其中至少有两点，其间距离小于

1正方形．如下图：证

把１×１正方形分成四个－1

×－1

的2

2则这５点中必有两点落在同一个小正方形内．而小正方形内的任两点的距离都小于第四章Burnside引理:设G={a1,a2,…ag}是目标集[1,n]上的置换群每个置换都写成不相交循环的乘积。G将[1,n]划分成l个等价类.c1(ak)是在置换ak的作用下不动点的个数。l=[c1(a1)+c1(a2)+…+c1(ag)]/|G|Pólya

定理设G={P1,P2,…,Pg}是n个对象的一个置换群，C(Pk)是置换Pk的循环的个数，用m种颜色对n个对象

,方案数为|G|母函数型Pólya定理k

kSk=(b1k+b2

+…+bm

),k=1,2…nl=—1

[mC(P1)+m

C(P2)+…+m

C(Pg)

].熟悉各种凸多面体的转动群欠角和的概念平面多边形的转动群注意不动图象4.6

举例足球：正5边形内角108o，正六边形内角120o欠角=360o

–(108o720

/12=60(个顶点)60·3/2=90(条棱)60/5=12(个5边形)60·2/6=20(个6边形)·

o

)=12o10根红、10根蓝、10根绿火柴搭一个正20面体，有多少方案？解：正20面体有正3角形组成，12个顶点，30条棱，20个面置换群为：不动：(1)30

1个

(30!/10!10!10!)*230（30根火柴的可重排列,火柴头两个方向,相当于二）•顶点—顶点:

(5)6

24个

(6!/2!2!2!)*26（12个顶点，6个轴，4个转动角度）(5根火柴一组,共6组，每组中5根火柴颜色必须相同，才有不动图象)•面心—面心

(3)10

20个

（20个面，10个轴，2个转动）（每组3根火柴,一共10个组，3根火柴颜色必须相同，才有不动图象,颜色无法平分,故无不动图象）棱中—棱中(1)2(2)1415个（火柴有方向，无不动图象）方案数：L=((30！/10！10！10！)*230+24*(6！/2！2！2！)*26)/60第六章线性规划标准形式二阶段法若第一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解大M法如果是求极大值，需加-M；如果是求极小值，需加M。如基变量中还存在M，就不能实现极值。约束条件：

p

j

x

j

p

x

p

j

x

j

b

加入松弛变量j

j

b

加入人工变量

b

先减去

x再s

加上axxasxmaxmin最优解λj

≤

0λj

≥

0换入变量λj>0或者max(λj)找λj<0或min(λj)换出变量c

jc1

cmcm1

cnicBXBP0P1

Pm

Pm1

Pnc1x1b11

0

0

1a1,m1

am,m1

a1n1

amn

mcmxmbmZ

cibi00

j

cj

ciaij31

2

x32122

xx1

2

x1

2

x3

4

x

例：

min

Z

3

x

x

x1

,

x2

,

x3

0min

Z

3

x1x1

2

x212

x1

,

x2

,

x3

1x

4

x

第一阶段：将人工变量迭代出去，从而找到原问题的基础可行解，构造如下模型：若W=0,说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。min

W

x6

x7⑵.两阶段法：

x1

,

x2

,

x3

011

2xx

x

2xx1

2x2

cj0000011icBxBbP1P2P3P4P5P6P70x4111-211000111x63-4120-1103/21x71-20100011Z46-1-301000x4103-20100-1—1x610100-11-210x31-2010001—Z10-1001030x4123001-22-50x210100-11-20x31-2010000Z00000011cj00000110x4123001-20x210100-10x31-20100Z000000cj-31100cBxBbx1x2x3x4x50x4123001-241x210100-1—1x31-20100—Z2-10001第二阶段1x1

2

x

4x1

x21

,

x2

,

x3

,

x5

,

x6第一阶段最后的表格第二阶段第一个表格Z在Cj的系数变化后需要重新算，z1=-3-1*(-2)=-1;z2=1-1=0……z5=0-1*(-1)=1cj-31100icBxBbP1P2P3P4P50x4123001-241x210100-1—1x31-20100—Z2-10001-3x141001/3-2/31x210100-11x390012/3-4/3Z-20001/31/3∴最优解为（4

1

9

0 0），目标函数

Z=

-2第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为

第二阶段计算的初始表（用单纯形法计算）。min

Z

3xmin

Z

3

x1

x31

2

x212

x1

,

x2

,

x3

02

xx

x1

2

x34

x

人工变量引入仔细消元检查根据个人喜好看是否采用改善的单纯形法对偶单纯形法不做要求Project总结ProjectI:内容算法效率分析与改进算法

相关评分标准：清晰，完整创新：抓眼球评分标准如果你是助教，你怎么给分？–实验图证明分析格式清晰抓眼球重点突出工作量象一篇晚交无实验，或实现简单分析简单创新不足亮点参考文献广泛涉猎L.

Jiang,

M.

Yu,

M.Zhou,

X.

Liu,

and

T.

Zhao,

2013,

Minimal

and

RandomGeneration

of

Permutation

and

Matrix

Groups,

Journal

of

Algebra,

387(2013),

pp.195–214.Leticia

Hernando,

Alexander

Mendiburu

and

Jose

A.

Lozano,

2013,

GeneratingCustomized

Land

Scrapes

in

Permutation-based

Combinatorial

OptimizationProblems,

Technical

Report,

University

of

the

Basque

Country

UPV/EH.发散思维STL，旋转移位二叉树GPUMPI…….请相信看你论过分的谦虚让人迷惑是个黑盒子题目点评Accelerating

Permutation

Generation

withGPUPUXin

Yi,

ChongShanGPU加速，体系结构设计描述清晰Permutation

Generation:

Comparison

and

InnovationMing

Han,

Qi

Li,Shuang

Hu背景调研充分，

9种方法比较，形式好，清晰二分索引树在全排列生成算法中的应用，

，来延涛数据结构在全排列算法分析基础上的新算法研究传，

，分析角度：波动性Project

I:

Best

Paper

AwardProjectII:

百花齐放106个有效提交幻方Fibonacci之美数独格点数八皇后（棋盘多项式）互不 的象Polya应用于ACM竞赛解题DNA拼接安卓 图案 方案二维装箱打印店找零问题比特币鸽巢和字符相似度无线传感器部署用母函数方法证明组合恒等式

•

国际象棋Mobius反演Ramsey数有用的建议可不可以在课上适当多讲一些组合数学在计算机领域背景下的问题，望老师考虑第二三节课之间不下课是不科学的，应该给休息的时间。科学研究表明，人的注意力不可能长时间保持。Project

II：Best

Paper

Award题目随机图与Ramsey理论之间情话鸽巢原理在字符串相似连接方面的应用，

，浅析大数学家，

，群论与魔方相关问题研究综述，

，本文结合自然语言处理和数据挖掘相关知识，深入探究挖掘了 老师组合数学课程中出现过的59位数学家的详细信息，通过解析自然语言处理得到的 分布、国籍分布、分布和人物关系等数据进行了处理和归纳，得出了一些初步结论。由人物关系分析可知，Colonel

Augustus

De

Morgan对于许多数学家都有着深刻的影响。一方面是ColonelAugustusDeMorgan在数学领域的研究工作有着深刻的历史影响。另一方面，他一生致力于 教育方式、打破旧有考试制度，以其富有创新的教学理念培育了许多伟大数学家。通过对组合数学