考前復習-p考試安排

考試安排時間：1月13日晚6點半-9點地點：建館報告廳答疑時間：–

1月10日下午2pm-5pm，東主樓8-402–

1月13日下午2pm-4:30pm，東主樓8-402考試題型5道解答或者證明題,一題中可能有多問五章內(nèi)容不考全排列生成:

myc@mai

考卷上請寫明學號，

，

號碼，1第一章排列與組合計數(shù)基本原理–加法法則:若|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)表示。排列的個數(shù)用P(n,r)表示。當

r=n時稱為全排列。(n-r+1)–P(n,r)=n(n-1)······組合–從n個不同元素中取r個不重復的元素組成一個子集，而不考慮其元素的順序，稱為從n個中取r個的無重組合。組合的全體組成的集合用C(n,r)表示，組合的個數(shù)用C(n,r)表示，–C(n,r)=P(n,r)/r!=n!/(r!(n-r)!)允許重復的排列(多重集排列):–求r1個1，r2個2，…，rt個t的排列數(shù)，設r1+r2+…+rt=n,設此排列數(shù)為P(n;r1,r2,…,rt),對1，2，…，t分別加下標，得到P(n；r1,r2,…,rt)·r1!·r2!·…·rt!

=

n!∴P(n；r

,r

,…,r)圓周排列–從n個中取r個的圓排列的排列數(shù)為P(n,r)/r,項鏈排列2≤r≤nP(n,r)/2r

,

3≤r≤n向上兩種方式放置各–在圓排列的基礎(chǔ)上，正面向上和個數(shù)是同一個排列。n!r1!r2!…rt!n1

2 t)=

————

=(

r1

r2

…

rt允許重復的組合(多重集的組合)n個不同的元素中取r個做允許重復的組合,其組合數(shù)為C(n+r-1,r)線性方程非負整數(shù)解x1+x2+…+xn=b的非負整數(shù)解的個數(shù)C(n+b-1,b)不相鄰的組合n個數(shù)中取r個作不相鄰的組合,組合數(shù)為C(n-r+1,r)多重集的組合給三個孩子發(fā)水果,一共12個一樣的蘋果,每個孩子至少有一個水果,問有多少種分法?解:設分給第i個孩子的水果數(shù)為xi,

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

yi≥0非負整數(shù)解的個數(shù)為C(9+3-1,9)=55不考的內(nèi)容排列，組合的生成Stirling公式第二章遞推關(guān)系與母函數(shù)二項式定理(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因式分解一元二次方程求解多項式長除法母函數(shù)指數(shù)型母函數(shù)對于序列a0

,a1

,a2構(gòu),造,一函數(shù)：0

1

2G(

x)

a

a

x

a

x

2

,稱函數(shù)G(x)是序列a0

,a1

,a的2

,母函數(shù)求解組合問題求解排列問題對于序列，函數(shù)a0

,

a1

,

a2

,

ak2!

3!xkk!1!G

(x)

a

a1

x

a2

x2

a3

x3e

0稱為是序列的指數(shù)型母函數(shù)a0

,

a1

,

a2

,常用母函數(shù)數(shù)列{1}n

≥0

母函數(shù)1/(1-x)=

1+x+x2+…指數(shù)型母函數(shù)ex數(shù)列

{cn}n≥0

母函數(shù)1/(1-

cx)=1+cx+c2x2+…

sin

x

x

3!

5!(1

x)2指數(shù)型母函數(shù)ecx1

2x

3x2

4x3

1k

0

21

3x

6x2

10

x3

(kk

02!x33!x5

,e

1

x

x2

x3

x遞推關(guān)系Hanoi問題Fibonacci數(shù)列鋪磚N位序列中符合某些性質(zhì)的排列數(shù)放球問題………..線性常系數(shù)遞推關(guān)系定義如果序列an

滿足

Ck

ank

0,

C1an1

C2

an2an2

5

1

11002

5

2C1

,

C2

,Ck及

d0

,

d1

,dk

1是常數(shù)，Ck

0

，則2

5

1稱為

an

的k階常系數(shù)線性遞推關(guān)系，2

5

2稱為an

的初始條件，C(x)

xk

C

xk

1

C

x

C1

k

1

k稱為an

的特征多項式線性常系數(shù)遞推關(guān)系確定特征多項式判斷特征方程根的情況非重根共軛復根多重根利用系數(shù)an的前若干項求解待定系數(shù)確定an14總結(jié)線性常系數(shù)遞推關(guān)系根據(jù)特征多項式C(x)的非零解的情況1)有k個不同非零實數(shù)解C

x

x

a1

x

a2

x

ak

a

l

an

l

an

l

ann

1

1

2

2

k

k其中l(wèi)1

,l2

,,lk

,是待定系數(shù)2)有一對共軛復根和時，i

e1i

e2na

A

cos

n其中A，B是待定常數(shù)。3)有k重根。不妨設1是k重根。是k個待定常數(shù)。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母函數(shù)法求多重集的組合給三個孩子發(fā)水果,一共12個一樣的蘋果,每個孩子至少有一個水果,問有多少種分法?解:母函數(shù)為,G(x)=(x+x2+x3+x4+…)(x+x2+x3+x4+…)(

x+x2+x3+x4+…)?

=(x/(1-x))3求x12的系數(shù),即1/(1-x)3中的x9的系數(shù).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位數(shù)/字母組成排列求n位二進制數(shù)相鄰兩位不出現(xiàn)11的數(shù)的個數(shù)。第n位為0或1:是0，有an-1；是1，則n-1位為0,有an-2.設n-1位不出現(xiàn)11的個數(shù)為an

1n-2位不出現(xiàn)11的個數(shù)為an

2n位不出現(xiàn)11的個數(shù)為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

母函數(shù)和遞推關(guān)系例題：鋪磚題方磚1*1，長磚1*2，給1*n的路鋪路面，求1）方案數(shù)，2）總磚數(shù)1）設方案數(shù)為an,以最后一塊磚分類

an1

an2ana0

1，a1

1，a2

2，a3

3，a4

5，a5

8an-1an-2an

Fn1

51

(

n1

n1

)2）總磚數(shù)設總磚數(shù)為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

(不考內(nèi)容第一類Stirling數(shù)Catalan數(shù)第三章容斥原理和鴿巢原理容斥原理棋盤多項式有限制的排列:如錯排廣義容斥原理鴿巢原理不考內(nèi)容Ramsey數(shù)反演容斥原理容斥原理:...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)整數(shù)整除求從1到500的整數(shù)中被3和5整除但不被7整除的數(shù)的個數(shù).解設A3：被3整除的數(shù)的集合

A5：被5整除的數(shù)的集合

A7：被7整除的數(shù)的集合所以｜A7∩A5∩A3｜＝｜A3∩A5｜－

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

500/3*5*7

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

所以|A2|=21A1∩A2為完全6次方數(shù)集合

46=4096,56=15625,所以|A1∩A2|=4所求數(shù)為10000-(100+21)+4=9883三論多重集組合6個a,6個b,3個c中取12個的組合數(shù)?可以轉(zhuǎn)化為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所求組合數(shù)=91-(21+45+21)+(0+3+3)=10令rk（C）表示k個棋子布到棋盤C上的方案數(shù)。定義

設C為一棋盤，稱R(C)=

∑

rk(C)

xk為C的棋盤多項式。k=0n規(guī)定r0(C)=1，包括C=Ф時。定理

設

ri

為

i個棋子布入

的方案數(shù)，i內(nèi)=1,2,3,···,n。有

的布子方案數(shù)（即不布子的方案數(shù)）為n!

－r1(n－1)!

＋

r2(n－2)!－···

＋(－1)nrn解

可得如下的帶 的棋盤其中有陰影的表示

．A

B

CⅠⅡⅢ的棋子多項式為：R(

)=R( )R(

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

)=1+4x+4x2+

x3故方案數(shù)＝3!－4·2!+4

·1!－1

·0!＝1A、B、C三種材料用作產(chǎn)品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不允許用A作原料，問有多少種安排方案？（假定每種材料只做一種產(chǎn)品的原料）“若有n個鴿子巢，n+1個鴿子，則至少有一個巢內(nèi)有至少有(n+1)/n=2個鴿子。”出現(xiàn)ak

+ak+1

+···+al累加,多半要構(gòu)造Sj

=

∑aii

=1出現(xiàn)奇偶性,整除,多半要取mod整點問題反證法內(nèi)點問題多次利用鴿巢j證明：在平面直角坐標系中，33個整點中必有9個整點的重心仍是整點。證：先證明9個整點中必有3個整點的重心的仍是整點。（證明方法請參照整點問題ppt）33個整點中必有9個3點組，每組的重心仍是整點。33個中有3個整點為重心整點，剩下30個，取3個整點為重心整點，剩下27個，取3個整點為重心整點，。。。剩下9個，取3個整點為重心整點，而這9個重心中必有3個的重心仍是整點，從而就證明了33個整點中必有9個整點的重心仍是整點。9組221在邊長為1的正方形內(nèi)任取5個點試證22其中至少有兩點，其間距離小于

1正方形．如下圖：證

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

×－1

的2

2則這５點中必有兩點落在同一個小正方形內(nèi)．而小正方形內(nèi)的任兩點的距離都小于第四章Burnside引理:設G={a1,a2,…ag}是目標集[1,n]上的置換群每個置換都寫成不相交循環(huán)的乘積。G將[1,n]劃分成l個等價類.c1(ak)是在置換ak的作用下不動點的個數(shù)。l=[c1(a1)+c1(a2)+…+c1(ag)]/|G|Pólya

定理設G={P1,P2,…,Pg}是n個對象的一個置換群，C(Pk)是置換Pk的循環(huán)的個數(shù)，用m種顏色對n個對象

,方案數(shù)為|G|母函數(shù)型Pólya定理k

kSk=(b1k+b2

+…+bm

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

[mC(P1)+m

C(P2)+…+m

C(Pg)

].熟悉各種凸多面體的轉(zhuǎn)動群欠角和的概念平面多邊形的轉(zhuǎn)動群注意不動圖象4.6

舉例足球：正5邊形內(nèi)角108o，正六邊形內(nèi)角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個轉(zhuǎn)動角度）(5根火柴一組,共6組，每組中5根火柴顏色必須相同，才有不動圖象)?面心—面心

(3)10

20個

（20個面，10個軸，2個轉(zhuǎn)動）（每組3根火柴,一共10個組，3根火柴顏色必須相同，才有不動圖象,顏色無法平分,故無不動圖象）棱中—棱中(1)2(2)1415個（火柴有方向，無不動圖象）方案數(shù)：L=((30！/10！10！10！)*230+24*(6！/2！2！2！)*26)/60第六章線性規(guī)劃標準形式二階段法若第一階段結(jié)束時，人工變量仍在基變量中，則原問題無（可行）解大M法如果是求極大值，需加-M；如果是求極小值，需加M。如基變量中還存在M，就不能實現(xiàn)極值。約束條件：

p

j

x

j

p

x

p

j

x

j

b

加入松弛變量j

j

b

加入人工變量

b

先減去

x再s

加上axxasxmaxmin最優(yōu)解λ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

第一階段：將人工變量迭代出去，從而找到原問題的基礎(chǔ)可行解，構(gòu)造如下模型：若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的系數(shù)變化后需要重新算，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∴最優(yōu)解為（4

1

9

0 0），目標函數(shù)

Z=

-2第二階段：在第一階段的最終表中，去掉人工變量，將目標函數(shù)的系數(shù)換成原問題的目標函數(shù)系數(shù)，作為

第二階段計算的初始表（用單純形法計算）。min

Z

3xmin

Z

3

x1

x31

2

x212

x1

,

x2

,

x3

02

xx

x1

2

x34

x

人工變量引入仔細消元檢查根據(jù)個人喜好看是否采用改善的單純形法對偶單純形法不做要求Project總結(jié)ProjectI:內(nèi)容算法效率分析與改進算法

相關(guān)評分標準：清晰，完整創(chuàng)新：抓眼球評分標準如果你是助教，你怎么給分？–實驗圖證明分析格式清晰抓眼球重點突出工作量象一篇晚交無實驗，或?qū)崿F(xiàn)簡單分析簡單創(chuàng)新不足亮點參考文獻廣泛涉獵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.發(fā)散思維STL，旋轉(zhuǎn)移位二叉樹GPUMPI…….請相信看你論過分的謙虛讓人迷惑是個黑盒子題目點評Accelerating

Permutation

Generation

withGPUPUXin

Yi,

ChongShanGPU加速，體系結(jié)構(gòu)設計描述清晰Permutation

Generation:

Comparison

and

InnovationMing

Han,

Qi

Li,Shuang

Hu背景調(diào)研充分，

9種方法比較，形式好，清晰二分索引樹在全排列生成算法中的應用，

，來延濤數(shù)據(jù)結(jié)構(gòu)在全排列算法分析基礎(chǔ)上的新算法研究傳，

，分析角度：波動性Project

I:

Best

Paper

AwardProjectII:

百花齊放106個有效提交幻方Fibonacci之美數(shù)獨格點數(shù)八皇后（棋盤多項式）互不 的象Polya應用于ACM競賽解題DNA拼接安卓 圖案 方案二維裝箱打印店找零問題比特幣鴿巢和字符相似度無線傳感器部署用母函數(shù)方法證明組合恒等式

?

國際象棋Mobius反演Ramsey數(shù)有用的建議可不可以在課上適當多講一些組合數(shù)學在計算機領(lǐng)域背景下的問題，望老師考慮第二三節(jié)課之間不下課是不科學的，應該給休息的時間?？茖W研究表明，人的注意力不可能長時間保持。Project

II：Best

Paper

Award題目隨機圖與Ramsey理論之間情話鴿巢原理在字符串相似連接方面的應用，

，淺析大數(shù)學家，

，群論與魔方相關(guān)問題研究綜述，

，本文結(jié)合自然語言處理和數(shù)據(jù)挖掘相關(guān)知識，深入探究挖掘了 老師組合數(shù)學課程中出現(xiàn)過的59位數(shù)學家的詳細信息，通過解析自然語言處理得到的 分布、國籍分布、分布和人物關(guān)系等數(shù)據(jù)進行了處理和歸納，得出了一些初步結(jié)論。由人物關(guān)系分析可知，Colonel

Augustus

De

Morgan對于許多數(shù)學家都有著深刻的影響。一方面是ColonelAugustusDeMorgan在數(shù)學領(lǐng)域的研究工作有著深刻的歷史影響。另一方面，他一生致力于 教育方式、打破舊有考試制度，以其富有創(chuàng)新的教學理念培育了許多偉大數(shù)學家。通過對組合數(shù)學