组合数学题目及标准答案.doc

膆组合数学蚃例1:将8个“车”放在8×8的国际象棋棋盘上,如果它们两两均不能互吃,那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态?肀解:8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。衿用一个排列a1,a2,…,a8,对应于一个安全状态,使ai表示第i行的ai列上放置一个“车”。这种对应显然是一对一的。因此,安全状态的总数等于这8个数的全排列总数8!=40320。芄肂例4:n位客人在晚会上每人与他人握手d次,d是奇数。证明n偶数。螀证:由于每一次握手均使握手的两人各增加一次与他人握手的次数,因此n位客人与他人握手次数的总和nd是偶数—握手次数的2倍。根据奇偶性质,已知d是奇数,那么n必定是偶数。蚆蚇例4从1到2n的正整数中任取n+1个,则这n+1个数中,至少有一对数,其中一个是另一个的倍数。薁证设n+1个数是a1,a2,···,an+1。每个数去掉一切2的因子,直至剩下一个奇数为止。组成序列r1,r2,,···,rn+1。这n+1个数仍在[1,2n]中,且都是奇数。而[1,2n]中只有n个奇数,故必有ri=rj=r,则ai=2αir,aj=2αjr。若ai>aj,则ai是aj的倍数。薀螈例5设a1,a2,···,am是正整数,则至少存在一对k和l,0≤k<l≤m,使得和ak+1+ak+2+···+al是m的倍数。螅芅证设Sh=,Sh≡rhmodm,0≤rh≤m-1,芁蝿h=1,2,···,,Sl≡,1≤rh≤m-=1,2,···,,故存在rk=rl,即Sk≡Slmodm,不妨设l>-Sk=ak+1+ak+2+…+al≡0modm肁薆例6设a1,a2,a3是任意三个整数,b1b2b3为a1,a2,a3的任一排列,则a1-b1,a2-b2,a3-:a1,a2,,不妨设为x;同样b1,b2,-b1,a2-b2,a3-,a2,…,a100是由数字1和2组成的序列,+ai+1+…+ai+9≤16,1≤i≤91。蒃则存在h和k,k>h,使得蒂ah+1+…+ak=39虿螇证令Sj=,j=1,2,…,100。显然羂节S1<S2<…<S100,且S100=(a1+…+a10)+(a11+…+a20)+…+(a91+…+a100)蒇根据假定有S100≤10×16=160袅作序列S1,S2,…,S100,S1+39,…,S100++39≤160+39蝿由鸽巢原理,=Sh+39,k>hÞSk-Sh=39即螁ah+1+ah+2+…+ak=39葿蕿例:1)求小于10000且的含1的正整数的个数莆2)求小于10000的含0的正整数的个数蒅艿解:1)小于10000的不含1的正整数可看做4位数,×9×9×9-1=:9999-6560=3439个羀蒈2)上述方法不可直接套用来计算“含0”数的个数。螇0019“含1”但“不含0”。莃不含0的1位数有9个,2位数有92个,3位数有93个,4位数有94个蚀不含0小于10000的正整数有蕿9+92+93+94=(95-1)/(9-1)=7380个羅螃含0小于10000的正整数有蒁9999-7380=2619个莇芇多重集(Multiset):元素可以重复出现的集合。如:膂M={a,a,a,b,c,c,d,d,d,d},膁也可简记为:M={3·a,1·b,2·c,4·d}莈元素也可重复出现无穷次,如无穷个a记为:∞·a莆蚁例1000到9999之间有多少个奇数,其各位数字互不相同?羁答案:5×8×8×7=2240蒀例用数字1,1,1,3,8可以构造多少个不同的5位数?如果用1,1,1,3,3呢?薄答案:5×4=20(5,2)=10莅蚂定义:设r为正整数,从n个不同的元素的集合S中,取r个元素按次序排成一行,称为S的一个r-排列。芇例S={a,b,c},则S有袆3个1-排列:a,b,c螄6个2-排列:ab,ac,ba,bc,ca,cb蒂6个3-排列:abc,acb,bac,bca,cab,cba芈n元素集的r-排列数记为P(n,r)。若r>n,则P(n,r)=0。羅n元素集S的n-排列简称为S的排列或n个元素的排列(全排列)膄袈定义n!=n×(n-1)×…×2×1莀0!=1莇故P(n,r)=n!/(n-r)!薃P(n,0)=1虿P(n,n)=n