组合数学题目及答案

组合数学例1将个车”放在8×8的际象棋棋盘上如它们两两均能互吃那么称个车处于一个安全状态。问共有多少种不同的安全状?解8“处于安全状态当且仅当它们处于不同的8行8列上。用一个排列a1,a2,…,a8，应于一个安全状态，ai表第i行列上放置一个车。种对应显然是一对一的。因此，安全状态的总数等于这8个的全排列总8!＝40320。例4：位人在晚上每人与他人握手，是数。证n偶。证由于每一次握手均使握手的两人各增加一与他人握手的次数，因此客人与他人握手次数总和是数握手次数的2倍根据奇偶性，已知奇数，那么必定是偶数。例从n的整数中取n+1个，则这+1个中，至少有一对数，其中一个是另一个的倍数。证设n+1个是a1,a2,···,an+1每数去掉一切2的子，直至剩下一个奇数为止。组成序列r1,r2,,···,rn+1。这个仍[1,n]，且都是奇数。n]中只有个奇数，故必有rirj=r,则=αir,aj=αjrai＞，则是的倍数。例设aaam是整，则至少存在一对k和l≤≤m使得和ak+···+al是m的数。证设Sh

i

≡rh≤rh≤-1，i=1,,若在l≡0则题成立≤rh≤=1,,m鸽巢原理，故存在rk=rl即Sk≡Slmod，不妨设l＞k．则Sl－Sk=+ak++…+≡mod例设aa3是意三个整数b3为a1,a2,a3的任一排列a1－－b2,a3－中至少有一个是偶数．证由巢原理：a2,至有两个奇偶性相同．则这３个数被２除的余数至少有个是相同的，不妨设为x;同b2,中２除的余数也至少有２个x．这样－b1,－a3－b3被除的余数至少有一个为０．例7设a2,…,是数字和２组成的序列,已从其任一数开始的顺序个数的和不超过16即ai+ai+1+…+≤161≤i。则存在和k，k>h使得ah+1+…+ak=39证令Sj=

j

i

，,2,。然i

S1<S2<，且(a1+(a11+…+a20)+…+(a91+根据假定有≤10×=作序列S1,S100,S1+39,…,S100+39.共200项其中最大项S100+39由鸽巢原理，必有两项相等．而且必是前段中某项与后段中某项相等．设Sk=，－Sh=39即ah+1+ah+2+…+ak=39例1)求于且的含正整数的个数求小于的的正整数的个数解1)小10000不含1的整数可看做4位,但0000.故有99××9－16560个含有－上方法不可直接套用来计含0数个数。0019含1但不”。不含的位数有个，2位数有个，3位有93个，4位有个不含小于的整数有9+92+93+94=(951)/(9－个含小于的整数有－7380=2619个多集Multiset)：素以复现集合如Ｍ={a,a,a,b,c,c,d,d,d,d，也简为M={3·abc,4·}元也重出无次如穷记为：·例1000到9999之间有多少个奇数，其各位数字互不相同？答：5××8×例用数，1，，3可构造多少个不同的5位数？如果用1，1，1，3呢？答：54=20(5,2)=10定：设r为整数，从n个不同的元素的集合S中取r个素按次序排一行，称为S的一个r-列。例S={a,b,c}则S有1-排列：b，c2-排列：ab，，bc，，3-排列：abc，，，，，素集的r-排列数记为()。若，则P)=0。

素集S的排列简称为S的列或n元素的排列（全排列）定n!=n(n-1)×…×20!=1故Pn,r)=n-r)!PnPn,n)=n!例将个英语字母按任意次排成一行，不允许、、i、、u五元音中任意两个相邻，有多少种排法？答：×例从{…,9}中任意取7不同的数字排成一行，不允许5和相邻，可以组成多少个不同的位数？答：×6×例个人围圆桌入座，其中两人希望不坐在一起，有多少种方案？答：9！-2！例对妇出席一宴会，围一圆桌坐下，试问有几种不同的方案？若要求每对夫妇相邻有多少种方案。答：9！×！=32×24=768例个不同颜色珠子串成一条项链，可以串成多少种不同的项链？答：19!/2设为一非负整数从具有n个同元素的集合中取个元素而不考虑其次序，称为S一个组合即的个r元子。例如：若，则S有0-组合：1-组合：{a}，{b}，{c}{d}2-组合：，，{a,d}，{b,c}，，{c,d}3-组合：{a,b,c},{a,b,d},{a,c,d},{b,c,d}4-组合：{a,b,c,d}例设共有15名同学选了数学课，但每次只名学到课，教室里有个座位，数学老师能看到学生们有多少种可能的座位坐法？答：C(15,12)×P(25,12)

544544例如果个单词可以3个或4个音母以重复使用个英文字母可以构造出多少个字母的单词？答：×5

3

×21

×

×21例求多于四位的三进制数的个数。解这个问题相当于多重{∞∞·2}的排列问题，由定理3.4.1所求的三进制数的个数N。例用面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？解所求标志数是多{红,3·黄旗}排数N由理例MISSISSIPPI这个单词里的所有字母可以组成多少不同的排？答：11!/(1!4!4!2!)定设S是重集，S的含有r个素的子多重集就叫做的r-组合。例如：S={2·a,1·b,3·c}，S的2-组合有，它们是{定设重={a∞a∞}则S的组数是Cr+-1,r。从k种素中取允许复的r组合的典型模型是r个同的球进k个同的盒里，而每个盒子中的球数不加限制，允许重复的组合数即其放法方案数。该数为C(r+kk-=C(r+r)从3种素中取元素的多重组合，相当于将个相同的球放人个同的盒中，每盒可多于一个球的方案。多重组合与球放入盒子的方案的对照：例从为众多的一角、二角币、五角币和一元币中选取六枚有多少种方法？解这里4种同的币,种币都可无限重因此本问题是多重集S={∞角∞·2角∞·5角∞元}组合，故从中选出枚的方法种数为：C(4+6-1,6)=C(9,6)=84

4444例试问x+y+z)展后有多少项？解这个问题相当于从3种素中取可重复4-合，或4个相同的球放进个同的盒子里，其组合数为：C(3+4-1,4)=C(6,4)=15即：x+y+z)共项。推设重集S={1·n2,…,nk}且一切i…,有ni≥，则的r组合数是C,r。推设重集={∞a…,∞ak}r≥k，则中个元素至少取一个的r-组数为Cr-k+k-1,k-Cr-1,k-1)。推r个同的球放到个标的盒子中，不允许有空盒，共有Crk种方案。例有一冰箱厂生产电冰箱，将其装入集装箱销往外地，每个集装箱可装18台冰箱，要求每个集装箱内各种电冰箱至少一台，问可能有多少种不同的集装箱装法？答：k=15,r=18N=C(18-1,15-1)=C(17,14)=680例设多集，要求每元素在组合中至少出现一次，求S的满足此条件的组的目。解方程x1+x2+x3+x4=10的整数解的个数即为所求。用变量代换y1=x1-1，，，y4=x4-1变换成求y1+y2+y3+y4=6的非负整数解的个数。该数目为C(6+4-1,6)=C(9,6)。例设方，满≥≥1,x3≥0,x45的数解的个数。解作变代换y1=x1-3，，y3=x3，y4=x4-5，方程的非负整数解的个