隔板法的三种题型是:标准型、多分型、少分型。再来看一下隔板法都有哪些题型特征 隔板法一共有三种题型:①标准型、②多分型、③少分型,后两种都需要基于“标准型”来解题,隔板法是组合数学的方法,用来处理n个无差别的球放进k个不同的盒子的问题。可一般化为求不定方程的解数,并利用母函数解决问题。
隔板法与插空法的原理一样。首先大家应该明确隔板法适用的题型为相同物体平均分配的问题,其次隔板法之所以不好掌握,就是因为这类题型有三种不同的变形,每一种变形都有其快速的解法。
排列组合隔板法用法:
隔板法就是在n个元素间插入(b-1)个板,即把n个元素分成b组的方法。在排列组合中,对于将不可分辨的球装入到可以分辨的盒子中而求装入方法数的问题,常用隔板法。
隔板法就是把m个相同单元分配成n组。这样m个单元中间有m-1个空格,分成n组需要n-1块隔板,所以就是C(m-1,n-1)种方法。
注意:隔板法的单元必须是相同的。
你的两个问题在数学界早有人探索过了叫做拆分数问题是组合数学研究的课题
你的第一个问题等价于将整数s拆分为n个正整数的拆分数关于这个问题有几个定理:
1将整数r拆分为k个正整数的拆分数,等价于将r拆分为最大数为k的拆分数证明略,你有兴趣可以去搜索下费勒斯图像
2将整数r拆分为重复度不超过k的拆分数,等价于将r拆分为不能被k+1整除的拆分数可以用母函数证明
所以你的第一个问题可以等价成将s拆分为最大数为n的拆分数,或者将s-n拆分为最大数不超过n的拆分数
关于该拆分数的编程上的计算方法目前有很多,但是据我所知,在数学上目前还没有公式可以表示递推公式也没有
你的第二个问题中的k很容易求,这个k叫做一般拆分数,记做p,例如p(5)=7
有如下递推关系:
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)++(-1)^(m-1)p(n-1/2m(3m+或-1)),这个也可以用母函数证明一句多余的话,母函数是组合数学中的重要工具
还有关于拆分数的穷举,在数学上也没有有效的办法,还是需要借助计算机
如果你希望获得关于拆分数穷举的程序或者算法,可以再联系我本人是学计算机的
1有200本相同的书,欲摆放在四个不同的书柜里,使得每个书柜摆放的书的数目只可能是20,40,60,80,100本,问有多少种摆放的方法?
答:总共有7中方案,每种方案方法数如下:
方案1: 20 20 60 100
先选定2个存放20的,剩下的2个不同的数做排列
C(4,2) P(2,2) = 12
方案2: 20 40 60 80
做全排
P(4,4) = 24
方案3: 20 40 40 100
先选定2个存放40的,剩下的20个不同的数做排列
C(4,2) P(2,2) = 12
方案4: 20 60 60 60
先选定3个存放60的,剩下的自然存放20
C(4,3) = 4
方案5: 20 80 80 20
先选定2个存放20的,剩下的两个自然存放80
C(4,2) = 6
方案6: 40 40 40 80
先选定3个存放40的,剩下的自然存放80
C(4,3) = 4
方案7: 40 40 60 60
先选定2个存放60的,剩下的两个自然存放40
C(4,2) = 6
总数 = 12 + 24 + 12 + 4 + 6 + 4 + 6 = 68种
2已知 A 是由 54 的所有因子组成的集合, 设%为 A 上的整
除关系,
(1) 画出偏序集<A,%>的哈斯图。
(2) 确定 A 中最长链的长度, 并按字典序写出 A 中所有最长的链。
(3) A 中元素至少可以划分成多少个互不相交的反链, 并完整写出
这些反链
答: A 的集合 = {1,2,3,6,9,18,27,54}
1)COVER(|)={(1,2),(1,3),(2,6),(3,6),(3,9),(6,18),(9,18),(9,27),(18,54),(27,54)}
2)有4个包含元素最多的全序子集: 最长链长为5
L1={54,27,9,3,1}
L1={54,18,9,3,1}
L1={54,18,6,3,1}
L1={54,18,6,2,1}
3)至少可以划分成3个互不相交的反链: {2,3},{6,9},{18,27}
3. 求方程 t1+t2+t3+t4=20 整数解的个数, 其中 t1≥3,t2≥1,t3≥0,t4≥5。
答:
由于t1≥3,t2≥1,t3≥0,t4≥5先取t1为3,t2为1,t3为0,t4为5,此时取值后和为9,也就是说将20-9的差值分配给t1,t2,t3,t4 就是所有的整数解个数
此时:t1'+t2'+t3'+t4' = 11
因此有C(11+4-1,11) = C(14,11)。
4 设 S={∞·2,∞·4,∞·5,∞·7,∞·9}是给定的重集, 其中 2,4,5,7,9
是 S 中的五个不同元素, 且每个元素在集合中可以有无穷多。 设 hn
表示从 S 中取 n 个元素(可以重复取) 且要求 2 和 4 出现偶数次的
排列数, 求 hn
解:已知2,4两个元素只出现偶数次,5,7,9三个元素出现任意次数,根据重拍母函数等式有:
设G(x) = (1 + x^2/2! + x^4/4! + + x^n/n!)^2 (1 + x + x^2/2! + x^3/3! ++x^n/n!)^3
= (e^x + e^(-x))/2 e^3x
= 1/4(e^x + 2 e^3x + e^5x)
= 1/4 (∑ x^n/n! + 2 ∑ (3x)^n/n! + ∑ (5x)^n/n!)
= 1/4 ∑(1 + 2 3^n + 5^n) x^n/n!
Hn = 1/4(1 + 2 3^n + 5^n)
5 4名同学参同时参加英语和德语面试,要求每门科目只能面试1人,2门科目先后顺序不同,有多少种次序?
解:本题可以理解为4名学生以任意顺序去参加英语面试,于此同时不能在同一时刻去参加德语面试,
即原来某位的同学不能在同一位置上(错排问题)。
因此该题的解为 4!D_{4} = 4!4!(1-1/1!+ 2/2!-3/3!+4/4!) = 249 = 216。
6 一个饭店有3种甜点,而且无限多。小王选取四个甜点的方法有?
解: t1+t2+t3=4
C(3+4-1,4) = C(6,4) = 15种
7 (2x1 -3x2 +x3)^6 展开式中,求X1^3X2X3^2的系数。
解:
(2x1 -3x2 +x3)^6 = (2x1 -3x2 +x3)(2x1 -3x2 +x3)(2x1 -3x2 +x3)(2x1 -3x2 +x3)(2x1 -3x2 +x3)(2x1 -3x2 +x3)
展开式相当于是6项多项式乘积。每一项都是看成加法原理是或的关系。
由于x1是3次幂,因此6项多项式中有3项选择2x1,因此有C(6,3)2^3
由于x2是1次幂,因此从剩下的3项多项式中取一项选择-3x2,因此有C(3,1)(-3)
由于x3是2次幂,因此从剩下的2项多项式中都选x3即可,因此有C(2,2)
所以X1^3X2X3^2的系数 = C(6,3)2^3 C(3,1)(-3) C(2,2) = -1440
解法2:
6项多项式,由于x1 + x2 + x3的幂之和是6,因此可以理解为从3个x1,一个x2和2个x3 组成的有限全排。
6!/(3! 2! 1!) 2^3 (-3) 1^2 = -1440
8、 如果1/(1-2x)^2 = ∑akx^k 则ak =
解:
根据泰勒公式
f(x) = f(0) + f1(0)/1! x + f2(0)/2!x^2 +
第二项展开式: f1(0) = (-2)(1-2x)^(-3)(-2) = (-2)(-2) f1(0)/1! = (-1)^1 (1+1)(-2)^1
第三项展开式: f2(0) = (-2)(-3)(1-2x)^(-4)(-2)^2 = (-2)(-3)(-2)^2 f2(0)/2! = (-1)^2 (2+1) (-2)^2
因此第k项展开为:fk(0)/k! = (-1)^k (k+1) (-2)^k
方法二:
由于公式(1-x)^(-n) = ∑ C(n+k-1,k)x^k
代入n=2 x = 2x得到系数: C(K+1,K)2^K
9 把4个不同的球,放到3个相异的盒子里,使得不出现空盒,有多少种不同的放法?
解:
先取2个球 C(4,2),再将剩下的球全排。于是答案为C(4,2)P(3,3) = 36
10 5个文科生和5个理科生交叉排成一排有多少中排法?
解:
先排列5个文科生,有5!种,再将理科生插到文科生的间隙中,于是有5!种插入排列, 由于两头的位置可以在左边也可以在右边
所以总共有2 5! 5! 种排列。
11 求方程x1+x2+x3+x4=10 正整数解的个数
解:
由于求正整数解,那要求x1>0,x2>0,x3>0,x4>0
由此原式可以理解为: (x1+1)+(x2+1)+(x3+1)+(x4+1) = 6
于是正整数解的个数为 C(6+4-1,6) = C(9,3) = 84
12 求将函数f(x)=(1+x+x^2+x^3+)^2 (x^2+x^3+x^4+)^3 展开后x^14系数
解:
此种情况可以理解为有5种不同颜色的球(如黑,白,红,绿,蓝)每种球无限制。现在要求取出14个球,其中至少有2个红球,2个蓝球和2个绿球。
则可以先分配2个红球,2个篮球,2个绿球,14个球中剩下的8个球,从5种颜色的球中取。
设取白球x1个,黑球x2个,绿球x3个,红球x4个,蓝球x5个。 则取法有:
x1+x2+x3+x4+x5 = 8
则有C(8+5-1,8) = C(12,4) = 495
13 有2个红球,1个白球,1个黄球,试求有多少种不同的组合方案?
解:1)母函数法:
f(x) =(1+x+x^2)(1+x)(1+x) = 1+3x+4x^2+3x^3 + x^4
所以有组合数 = 1+3+4+3+1 = 12种
2)分情况讨论:
红:0,1,2
白:0,1
黄:0,1
一个不选方法:0,0,0
选1个球的组合: (0,0,1)(0,1,0),(1,0,0)
选2个球的组合:(0,1,1)(1,0,1),(1,1,0)(2,0,0)
选3个球的组合: (1,1,1)(2,1,0),(2,0,1)
选4个球的组合: (2,1,1)
总共组合方案 = 1+3+4+3+1=12
14 把4个相异的球,放到3个相异的盒子中,使得不出现空盒,有多少中不同的放法?
解: 分两步完成,第一步先把4个相异的球分成三组,即选2个作为一组。 有C(4,2)种方法。
第二步,把分成3组的球放进3个不同的盒子,做全排, 有P(3,3)中方法。
因此方法数为: C(4,2) P(3,3) = 6 6 = 36 (种)
15求方程x+y+z+k = 10正整数解的个数
解: (x+1) + (y+1) + (z+1) + (k+1) = 6
C(6+4-1,6) = C(9,6) = C(9,3)
f(x)=1/(1-x+x^2)=(1+x)/(1+x^3)=a0+a1x+anx^n+
1+x=(1+x^3)f(x)=(a0+a1x+anx^n+)+(a0x^3+a1x^4++anx^(n+3)+)
=a0+a1x+a2x^2++[an+a(n-3)]x^n+
因此a0=1,a1=1a2=0,n>=3时,an+a(n-3)=0
你的问题相当于下面这个数论中的问题:
在正整数领域,一个数n可以表达成多少种不多于k个数相加的形式?
例如,n=5,k=4时,
=5(这种情况可以认为是分解成一个数相加;相当于把球都放进同一个盒中)
=4+1=3+2(分解成两个数相加;相当于把球放进两个盒中)
=3+1+1=2+2+1(分解成三个数相加;相当于把球放进三个盒中)
=2+1+1+1(分解成四个数相加;相当于把球放进四个盒中)
共有6种形式。
(此外还有,5=1+1+1+1+1,分解成五个数相加;相当于把球放进五个盒中,只不过不符合k=4的要求)
这个问题是数论中整数分拆的问题,我们把能够得到的方法数目记作p(k,n)。例如,刚才的p(4,5)=6。其中,当k=n时,简记为p(n)。
再用p_k_(n)表示把n表达成刚好k个数相加的方法。(两个下划线之间的数为下角标)
则显然p(n)=p_k_(n)的求和(其中k=1,2,3……,n)。因此,问题转化为求p(n)与p_k_(n)表达式(前者减去后者的若干项就是你的问题的结果)。
下面请看(如果感觉太小,可以保存到电脑上)。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)