下载文档原格式
二项式定理12(1)1(1)k kx x x x −+=−+++−+L L§2.2 递推关系§2.2 递推关系§2.2 递推关系•假定n-1个盘子的转移算法已经确定。
§2.2 递推关系令h(n)表示n个圆盘所需要的转移盘次。
§2.2 递推关系或利用递推关系(2-2-1)有如何从母函数得到序列？L ),2(),1(h h§2.2 递推关系例2. 求n位十进制数中出现偶数个5的正整数的个数。
+++=2)( x a x a a x A 9 :+=b a a x§2.2 递推关系故得关于母函数A(x)和B(x)得连立方程组：§2.2 递推关系解法二：n-1位的十进制数的全体共9×10n-1个(最高位不为0)，§2.2 递推关系§2.2 递推关系§2.2 递推关系因，故令100!!k k k k ==§2.3 母函数的性质一个序列和它的母函数一一对应。
给了§2.3 母函数的性质{b{a}}不特别说明,下面假设k<l性质2：a b =若性质3：k x(A)1x−1∑∞收敛若 ∑∞a 性质4b ac+abbbaa=L+++§2.3母函数的性质1§2.4 Fibonacci数列L++=2)(x F x F x G 设=+B A 0=+B A§2.4.4在选优法上的应用设函数y=f(x)在区间(a,b)上有一单峰极值点，§2.4.4在选优法上的应用设函数在点取得极大值。
要求)(x f ξ=x§2.4.4在选优法上的应用§2.4.4在选优法上的应用§2.4.4在选优法上的应用x可见做两次试验，至少可把区间缩至原§2.4.4在选优法上的应用§2.4.4在选优法上的应用§2.4.4在选优法上的应用§2.4.4在选优法上的应用定理：测试n次可将包含单峰极值点的区间§2.4.4在选优法上的应用§2.4.4在选优法上的应用§2.4.4在选优法上的应用定理：设在给定区间内有单峰极值点。
第三章容斥原理与鸽巢原理§3.1 容斥原理引论§3.1 容斥原理引论§3.1 容斥原理引论§3.2 容斥原理BA§3.2 容斥原理§3.2 容斥原理§3.2 容斥原理§3.2 容斥原理§3.2 容斥原理§3.2 容斥原理§3.2 容斥原理§3.3 举例§3.3 举例§3.3 举例§3.3 举例1204A A A⎢⎥==I I，§3.3 举例§3.3 举例例6。
求完全由n个布尔变量确定的布尔函数的个数。
§3.3 举例例7。
欧拉函数Φ(n)是求小于n且与n互素的数的个数。
§3.3 举例•例7续。
欧拉函数Φ(n)是求小于n且与n互素§3.3 举例A,B,C,D,E,F,G,H的全排列中只§3.4 棋盘多项式和有限制排列§3.4 棋盘多项式和有限制排列§3.4 棋盘多项式和有限制排列§3.4 棋盘多项式和有限制排列n§3.4 棋盘多项式和有限制排列§3.4 棋盘多项式和有限制排列§3.4 棋盘多项式和有限制排列§3.4 棋盘多项式和有限制排列§3.4 棋盘多项式和有限制排列３．有禁区的排列设对于排列P=P 1 P 2 P 3 P 4，规定P 1≠３，２≠１、４，P ３≠2、４，P 4≠2。
这样的排列对应于有禁区的布子。
如图中有影线的格子表示禁区。
定理设r i 为i 个棋子布入禁区的方案数，i =1,2,3,···,n 。
有禁区的布子方案数（即禁区内不布子的方案数）为n! －r 1(n －1)! ＋r 2(n －2)!－···＋(－1)n r n 设A i 为第i 个棋子布入禁区，其他棋子任意布的方案集，i =1 , 2 , 3, …,n 。
Combinatorics第章排列与组合第一章马昱春MA Yuchunmyc@1内容回顾•全排列生成算法(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法•全排列：P是[1,n]的一个全排列。
P=P 1P 2…P n •序号：先于此排列的排列的个数。
–字典序中将先于此排列的排列按前缀分类，得到排列的序号n-1(n-i)!小的数的个数i=1,2,,n-1∑k i (n i)! k i ：P i 的右边比P i 小的数的个数i 1,2,…,n 1i=1•中介数：每个排列对应的中介数即k 1k 2…k n-1–递增/递减进位制数–记录排列的结构全排列序号中介数对应2–全排列，序号，中介数一一对应字典序下的对应关系n-1排列：P=P 1P 2…P n序号：∑k i (n-i)! i=1中介数：k 1k 2…k n-11230(00)()↑1321(01)↑ (321)n!-1=5 (21)………………()↑=2*2!+1*1!=5共有n!个排列0到(n!-1)0到(n!-1)个中介数3中介数的特点：记录当前数字右边比当前数字小的数字的个数•给定一个排列求后面或者前面的某个排列给定个排列求后面或者前面的某个排列–“原排列”→“原中介数”→“新中介数”“新排列”→新排列递增/递减进位制数加减法序号(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法0 123 (00)↑ 123 (00)↑ 123 (00)↓ 123 (00)↓1 132 (01)↑ 213 (01)↑ 132 (01)↓ 132 (01)↓2213(10)132(10)312(02)312(02)2 213 (10)↑ 132 (10)↑ 312 (02)↓ 312 (02)↓3 231 (11)↑ 231 (11)↑ 213 (10)↓ 321 (10)↓4 312 (20)↑ 312 (20)↑ 231 (11)↓ 231 (11)↓5321(21)321(21)321(12)213(12)5 321 (21)↑ 321 (21)↑ 321 (12)↓ 213 (12)↓对中介数的不同解释算法构成了不同的排列顺序4常用排列生成工具_p,•C++标准程序库中有两个函数next permutation, prev_permutation，可以生成字典序排列#include algorithm•#include<algorithm>bool next_permutation( iterator start, iterator end ); bool prev_permutation( iterator start, iterator end ); bool prev permutation(iterator start iterator end);–The next_permutation() function attempts to transform thegiven range of elements [start,end) into the nextgiven range of elements[start end)into the nextlexicographically greater permutation of elements. If itsucceeds, it returns true, otherwise, it returns false.•/blog/stl_next_permutation.html5•Matlab中也支持排列的生成–用命令perms得到排列,用法：perms(vector) 给出向量vector的所有排列，例如perms([2 3 5]) 运行结果：5 3 2，5 2 3，3 5 2，3 2 5结果532523352325，2 3 5，2 5 3–此函数值只能适用于n < 15的情况下。
容斥原理§3.6 广义的容斥原理§3.6 广义的容斥原理ii=0•例某校有１２个教师，已知教数学的有８位，教物理的§3.7 容斥原理应用举例(10,5)§3.7 容斥原理应用举例(10,5)例第二类Stirling数的展开式•例第二类Stirling数的展开式§3.7 容斥原理应用举例§3.7 容斥原理应用举例§3.7 容斥原理应用举例§3.7 容斥原理应用举例§3.7 容斥原理应用举例设A为a= i 或i+ 1 (1≤i ≤n－1 )，a= n 或1的排列§3.7 容斥原理应用举例•从1 , 2 , 2 , 3 ,3 ,4, ···,n－1, n－1, n , n , 1§3.8 Mǒbíus反演§3.8 Mǒbíus反演与Mǒbíus函数密切相关的另一类数论函数是Euler函数§3.8 Mǒbíus反演∑∑nd nd dd| |∑∑nd nd dd||“⇐”：设（M）成立。
则§3.8 Mǒbíus反演nf ( n ) = ∑g (d ) = ∑g ( ) (M)§3.8 Mǒbíus反演§3.8 Mǒbíus反演§3.8 Mǒbíus反演§3.8 Mǒbíus反演§3.8 Mǒbíus反演§3.8 Mǒbíus反演设长度为n 的圆排列的个数为T( n )，则T( n ) ＝∑M( d )d ｜n例m = { 1 , 2 } ，n = 7 则M ( 7 ) = ( 27－2 ) = 18T ( 7 ) = ∑M( d ) = M (1 ) + M ( 7) = 20d ｜717例m = { 1 , 2 , 3} ，n = 4 则M ( 4 ) = 1/4( 34－32) = 18T ( 4 ) = ∑M( d ) = M (1 ) + M(2) + M (4) = 24d ｜4d=1,2,4周期为1且长度为1的圆排列个数周期为2且长度为2的圆排列个数∑=nd dn md nn M |)()(μ1鸽巢原理（pigeonhole principle）是组合数学中最简单也是最基本的原理，也叫抽屉原理。
Combinatorics第章排列与组合第一章马昱春MA Yuchunmyc@1内容回顾•全排列生成算法(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法•全排列：P是[1,n]的一个全排列。
P=P 1P 2…P n •序号：先于此排列的排列的个数。
–字典序中将先于此排列的排列按前缀分类，得到排列的序号n-1(n-i)!小的数的个数i=1,2,,n-1∑k i (n i)! k i ：P i 的右边比P i 小的数的个数i 1,2,…,n 1i=1•中介数：每个排列对应的中介数即k 1k 2…k n-1–递增/递减进位制数–记录排列的结构全排列序号中介数对应2–全排列，序号，中介数一一对应字典序下的对应关系n-1排列：P=P 1P 2…P n序号：∑k i (n-i)! i=1中介数：k 1k 2…k n-11230(00)()↑1321(01)↑ (321)n!-1=5 (21)………………()↑=2*2!+1*1!=5共有n!个排列0到(n!-1)0到(n!-1)个中介数3中介数的特点：记录当前数字右边比当前数字小的数字的个数•给定一个排列求后面或者前面的某个排列给定个排列求后面或者前面的某个排列–“原排列”→“原中介数”→“新中介数”“新排列”→新排列递增/递减进位制数加减法序号(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法0 123 (00)↑ 123 (00)↑ 123 (00)↓ 123 (00)↓1 132 (01)↑ 213 (01)↑ 132 (01)↓ 132 (01)↓2213(10)132(10)312(02)312(02)2 213 (10)↑ 132 (10)↑ 312 (02)↓ 312 (02)↓3 231 (11)↑ 231 (11)↑ 213 (10)↓ 321 (10)↓4 312 (20)↑ 312 (20)↑ 231 (11)↓ 231 (11)↓5321(21)321(21)321(12)213(12)5 321 (21)↑ 321 (21)↑ 321 (12)↓ 213 (12)↓对中介数的不同解释算法构成了不同的排列顺序4常用排列生成工具_p,•C++标准程序库中有两个函数next permutation, prev_permutation，可以生成字典序排列#include algorithm•#include<algorithm>bool next_permutation( iterator start, iterator end ); bool prev_permutation( iterator start, iterator end ); bool prev permutation(iterator start iterator end);–The next_permutation() function attempts to transform thegiven range of elements [start,end) into the nextgiven range of elements[start end)into the nextlexicographically greater permutation of elements. If itsucceeds, it returns true, otherwise, it returns false.•/blog/stl_next_permutation.html5•Matlab中也支持排列的生成–用命令perms得到排列,用法：perms(vector) 给出向量vector的所有排列，例如perms([2 3 5]) 运行结果：5 3 2，5 2 3，3 5 2，3 2 5结果532523352325，2 3 5，2 5 3–此函数值只能适用于n < 15的情况下。
–全排列生成算法??Project IProject I•全排列生成算法的研究和实现–分10–必作每–每组1-3人–C/C++ or Java–11月11日前网络学堂提交•目标–Research and Novelty•在实现和研究4种全排列生成算法基础上进行创新•算法效率和复杂度分析•新的算法•任何相关内容的创新点•评分标准Paper (80%)：3-6页–Paper(80%)–代码以及可执行文件(20%)161.6组合的生成•字典序中组合的先后关系{128}A ={2378}B={23567}–{1, 2 ,…,8}中选5个数的组合,A = {2,3,4,7,8}, B= {2, 3 ,5 ,6 ,7}. –A 在B 之前•设从[1,n ]中取r 元的组合全体为C (n ,r ).•某个组合c 1c 2…c r ∈C (n ,r ).不妨设c 1＜c 2＜…＜c r ≤n •c r -1 ≤n -1, c r -2≤n -2….c 1≤n -r +112•c 1≥1,c 2≥2…..c r ≥r •i ≤c i ≤(n －r +i ), i =1,2,…,r •i =c 则是第一个组合；字典序中如果所有的i 则是第个组合；•如果所有的c i =(n －r +i ), 则是最后一个组合•则满足条件c i <(n －r +i ), 就有可替换的余地寻找下个组合希望是从可能替换的位置中最右侧的开始替换•寻找下一个组合希望是从可能替换的位置中最右侧的开始替换–n =5,r =3–(1 2 5)5, n -r +i =5-3+3=5, 8()先找最右侧的,,不可以替换–再找2，n -r +i =5-3+2=4，可以替换；–从2开始替换成从3开始的递增序列；1 3 4求个合的算法描•求下一个组合的算法描述如下令j max{i|c i＜n r+i}.•=－}•则c1c2…c r的下一个组合为•c1c2…c j-1(c j+1)(c j+2)…(c j+r－j+1)•这等于给C(n,r)的元素建立了字典序。
的元素建立了字典序•{1,2,…r}的序号为0，{n-r+1,n-r+2,…n}的序号为C(n,r)－19161.6 组合的生成•1，2，3，4，5中取3个做组合，组合数从个做组合组合数是C(5,3)=10•(1 2 3)(1 2 4)(1 2 5)•(134)(135)(1 3 4)(1 3 5)•(1 4 5)•(2 3 4)(2 3 5)•(2 4 5)()•(3 4 5)10Matlab组合生成•combntns(set,subset) 在集合set中取subset个元素的所有组合例如：例如在[2 3 5 9 7]中取3个元素的所有组合为：•[23597]combntns([2 3 5 9 7],3)11171.7可重组合•可重组合：从A ={1,2,3….n }中取r 个元素{a 1,a 2,…a r },a i ∈A ，12记为i =1,2,..r ,且允许a i =a j , i ≠j ，记为C(n ,r )。
•多重集：元素可以多次出现的集合。
t i =0,1,…∞表示元素a i 可n t ·a , 以出现的次数，含有个不同元素的多重集可以记为{11,t 2·a 2…,t n ·a n }•上述可重组合可以定义为t i = ∞多重集组合.{123}•A ={1,2,3}中取2个元素•无重组合：C(3,2)=3 {1 2}{1 3}{2 3}•可重组合：•{1 2}{1 3}{2 3}•{11}{22}{33}1234•可重组合模型：取r 个无标志的球，n 个有区别的盒子，每个盒子允许放多于一个球个球是有区别的个盒子是无区别的12•无重组合的模型：n 个球是有区别的，r 个盒子是无区别的，取r 个球放入盒子，每个盒子一个球。
123412340 1 2 3 4{1，1，3，3，4}•在n 个不同的元素中取r 个进行组合，若允许重复的组合1{1，2，5，6，8}数为C(n +r -1,r )•证明1：构造与无重组合C(n +r -1,r )的一一对应关系•假设n 个元素为{1,2…n 得到的某个可重复的组合为{,},{a 1,a 2..a r }, a 1≤a 2≤… ≤ a r •构造a 1,a 2+1,a 3+2…..a k +k-1,…a r +r -1，证明该数列中的数字各自不同•证明该数列中的数字各自不同：–假设存在i <j , a i +i -1=a j +j -1，则a i >a j ，而i <j 时,a i <a j ,矛盾，构造出来的序列共r 个不同的数，范围为[1,n+r-1]•故构造的序列为从n +r -1个不同的数中取r 个构成的无重序列,1•反过来可以从n +r -1个不同的数中取r 个构成的无重序列中每个元素变换产生一组可重序列，故构造的组合序列和原序列一一对应；13和原序列对应；•构造的序列最小是1，最大是n +r -1,相当于从n +r -1个不同的数中取r 个进行无重组合，其组合数为C(n +r -1,r )1.7 可重组合17线性方程整数解线性的负数的个数•线性方程x 1+x 2…+x n =b 的非负整数解的个数是C(n+b -1,b (,)11111111b 个11 ..1 1.. 1 1..11.. 1n-1个门框x 1个1•其方程解的个数是C(n+b -1,b )15多重集的组合••给三个孩子发水果一共12个一样的苹果给个孩子果,共个样苹果,每个孩子至少有一个水果,问有多少种分法?•解:设分给第i 个孩子的水果数为x i , x i ≥1•x 1+x 2+x 3=12•令y 1=x 1-1,y 2=x 2-1,y 3=x 3-1•++=9 ≥0y 1y 2y 3y i •非负整数解的个数为C(9+3-1,9)=5516171.7 可重组合•例题(x+y+z)4有多少项？有多解(x+y+z) (x+y+z) (x+y+z) (x+y+z) (x+y+z)•4=()()()(•A={x,y,z}三个元素中取r=4个做可重组合•C(n+r-1,r)=C(3+4-1,4)=C(6,4) = 15•相当于总共4个无区别的球投到x,y,z三个盒子x y z中，每盒球数不限–x4表示4个球都投到x盒子中17181.8不相邻组合•不相邻的组合是指从A={1,2,…n}中取r个不相邻的数进行组合(不可重)，即不存在相邻的两个数j,j+1的组合•例n=6,r=3的不相邻组合有•{1 3 5}{2 4 6}•从A={1,2,…n}中取r个不相邻的数进行组合，其组合数为C(n-r+1,r)180 1 2 3 4B: {1，3，5，7，9}C {1}•从A ={1,2,…n }中取r 个不相邻的数进行组合，其组合+1C: {1，2，3，4，5}数为C(n -r +1,r )•证明：设B ={b 1,b 2…b r }是一组不相邻的组合，•<==-1=-r n-r +1假定b 1<b 2….<b r ,令c 1b 1, c 2 b 21,…c r b r r +1≤n r +1,则c 1<c 2…<c r ,{c 1,c 2…c r }为从{1,2,…n-r +1}中取r 个进行不可重组合•反之，从{1,2,…n-r +1}中取r 个进行不可重组合构成{d 1,d 2…d r },假定d 1<d 2…<d r d d 111•c 1=d 1, c 2=d 2+1,…c r =b r +r -1≤n-r+1+r-1=n•c 1<c 2…<c r ，c i +1-c i = (d i +1+i )-(d i +i -1)=d i +1-d i +1>1,故c i +1不相邻={12和c i 不相邻。
