《课堂练习2》参考答案 孙贺 、填空题(20分,毎格5分,注意:请在空格内填入计算结果,填写组合表达式不得分。) 设方程为x1+x2+r3=14,则所有变量均不超过8的正整数解的组数总共有 解答:排列总数为C(14-1,2-1)-3·C(6-1,3-1)=78-3×10=48 2.将ab,c,d,e,f,g排成一行,使得beg和cad都不出现,则排列总数有 解答:排列总数为 3.确定多重集S={3·a,4·b,2·q}的排列数,使得在这些排列中同类字母的全体不能相邻。 排列总数 解答:多重集合S的排列总数为==1260;若a连续出现,则s的排列总数为=105 若b连续出现;则s的排列总数为是;若c连续出现,则S排列总数为;若a和bbb连续出 现,则排列总数为=12依此类推 所以排列总数为 1260-105-60-280+20+12+30-6=871 4.十进制中,没有重复数字的4位数个数为 解答:没有重复数字的4位数个数为 9×9×8×7 、计算题(共3小题,每题10分,总共30分) 1.设函数f:A→B,|=n,|B|=m。确定从4到B的满射函数个数。 解答:分情况讨论:(1)若nm的情况。因为从A到B存在m个函数,从定义域A的n元集合到B的m个集合 有C(m,1)·(m-1)个函数恰好缺少m个元素中的1个元素,C(m,2)·(m-2)个函数恰好缺少m个 元素中的2个元素,……,有C(m,m-1)·1个元素恰好缺少m个元素中的m-1个元素,故由容斥原
5,öS26ëY å !WK£20©§z5©§5¿µ3SW\O(J§W|ÜLªØ©"¤ 1©§x1 + x2 + x3 = 14 §K¤kCþþØL8ê)|êok " )µüoêC(14 − 1, 2 − 1) − 3 · C(6 − 1, 3 − 1) = 78 − 3 × 10 = 48" ✐ 2©òa,b,c,d,e,f,gü¤1§¦begÚcadÑØÑy§Küoêk " )µüoê 7! − 5! − 5! + 3! = 4806 ✐ 3©(½õ8S = {3 · a, 4 · b, 2 · c} üꧦ3ù ü¥Óai1 NØU" üoêµ " )µõ8ÜSüoê= 9! 3!4!2! = 1260¶eaaaëYÑy§KSüoê 7! 4!2! = 105¶ ebbbbëYÑy¶KSüoê 6! 3!2!¶eccëYÑy§KSüoê 8! 3!4!¶eaaaÚbbbbëYÑ y§Küoê4! 2! = 12,daí,· · · · · · ¤±üoê 1260 − 105 − 60 − 280 + 20 + 12 + 30 − 6 = 871 ✐ 4©?¥§vkEêi4 êê " )µvkEêi4 êê 9 × 9 × 8 × 7 = 4536 ✐ !OK£3K§zK10©§o30©¤ 1©¼êf : A 7→ B, |A| = n, |B| = m "(½lAB÷¼êê" )µ©¹?ص(1) en m¹"ÏlAB3mn¼ê§l½ÂAn8ÜBm8Ü kC(m, 1) · (m − 1)n¼êTÐ"m¥1§C(m, 2) · (m − 2)n¼êTÐ"m ¥2§· · ·§kC(m, m − 1)· 1 nTÐ"m¥m − 1§dN½ 1
理得满射个数为 m2-C(m,1)·(m-1)n+C(m,2)·(m-2)m-…+(-1)-C(m,m-1)·1n 2.求1000的末尾的零的个数 解答:此问题等价于求把1000分解成素数时,2和5的幂是多少?1000的尾数零的个数等于2和5的 幂中较小的一个。显然,5的幂的个数远小于2的幂的个数。 在1至1000共1000个数中,5的倍数的数有200个,52=25的倍数的有40个,其中53=125的倍数 的有8个,54=625的倍数的有1个 所以100质因数分解时,5的幂应为200+40+8+1=249。故100末尾有249个零。「 3.John去参加一展览会,展览会的门票为50元。在售票处,John发现了一个奇怪的现象:在排 队购票的2n个人中,总有n个人拿的是面值为100元的钞票,而另外的n个人拿的是面值为50元的钞 票。假设售票处原来没有零钱。那么共有多少种排队方式,使得售票处不至出现找不开钱的局面。 解答:构造组合模型如下:我们用1表示有一个手拿$50的人,用0表示手拿$100的人,那么我们 所求解的问题可以转化为:n个1和n个0组成一个2n位的二进制数,要求从左到右扫描,1的累计数 不小于0的累计数,求满足这个条件的二进制的数的个数 在2n位上填入n个1的方案数为C(2n,n)不填1的其余n位自动填入0。从C(2n,n)中减去不符合 要求的方案数就是问题的解。不符合要求的是指从左到右扫描,出现0的累计数超过出现1的累计 不符合要求的数的特征是从左到右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0和m个1 而后的2(-m)-1位上有n-m个1,n-m-1个0。如果把后面这部分2(n-m)-1位的0与1互 换,使之成为n-m个0,n-m-1个1,结果得到一个由n+1个0和n-1个1组成的2n位数。即一个 不符合要求的数对应一个由n+1个0和n-1个1组成的一个排列。 反之,任何一个由n+1个0和n-1个1组成的2n位数,由于0的个数多于2个,2n是偶数,所以 定在某一个奇数位上出现0的累计数超过1的累计数。同样在后面的部分,令0和1互换,使之成为 一个由n个0和n个1组成的2n位数。即n+1个0和n-1个1组成的2n位数,一定对应一个不符合要求 的数。所以不符合要求的数的总数为C(2n,n+1) 所以我们所求的结果便可表示为C(2n,n)-C2n,n+1)=mC(n,n) 证明题(共5题,每题10分,总共50分) 动员是25天内的冠军,该选手每天至少比赛一场,但是总共比赛次数不超过41场。证 明:存在着连续的若干天使得该选手恰好进行了8场比赛
n÷ê mn − C(m, 1) · (m − 1)n + C(m, 2) · (m − 2)m − · · · + (−1)n−1C(m, m − 1) · 1 n ✐ 2©¦1000!""ê" )µd¯K du¦r1000!©)¤ê§2Ú5´õº1000!ê"ê u2Ú5 ¥"w,§5êu2ê" 3110001000ꥧ5êêk200§5 2 = 25êk40§Ù¥5 3 = 125ê k8§5 4 = 625êk1" ¤±1000!Ïê©)§5A200 + 40 + 8 + 1 = 249"1000!"k249"" ✐ 3©Johnë\ÐA¬§ÐA¬¦50"3Ȧ?§Johnuy Û%yµ3ü è ¦2n<¥§okn<<´¡100¦§ , n<<´¡50 ¦"bȦ?5vk"a"@okõ«ü誧¦È¦?ØÑyéØmaÛ¡" )µE|Ü .Xeµ·^1L«kÃ<$50<§^0L«Ã<$100<§@o· ¤¦)¯K±=zµn1 Ún0|¤2n ?ꧦlm×£§1\Oê Øu0\Oꧦ÷vù^?êê" 32n þW\n1YêC(2n, n) ØW1Ù{n gÄW\0"lC(2n, n)¥~ØÎÜ ¦YêÒ´¯K)"ØÎܦ´lm×£§Ñy0\OêLÑy1\O ê" ØÎܦêA´lm×£§7,3,Ûê 2m+1 þÄkÑym+10Úm1¶ 2(n − m) − 1 þkn − m 1§n − m − 10"XJr¡ùÜ©2(n − m) − 1 01p §¦¤n − m0§n − m − 11§(Jdn + 10Ún − 11|¤2n ê"= ØÎܦêéAdn + 10Ún − 11|¤ü" §?Ûdn + 10Ún − 11|¤2n ê§du0êõu2§2n´óꧤ± ½3,Ûê þÑy0\OêL1\Oê"Ó3¡Ü©§-0Ú1p§¦¤ dn0Ún1|¤2n ê"=n + 10Ún − 11|¤2n ꧽéAØÎܦ ê"¤±ØÎܦêoêC(2n, n + 1) ¤±·¤¦(JBL«C(2n, n) − C(2n, n + 1) = 1 n+1C(2n, n) ✐ n!y²K£5K§zK10©§o50©¤ 1©$Ä ´25US)§TÀÃzU'm|§´o'mgêØL41|"y ²µ3XëYeZU¦TÀÃTÐ?1 8|'m" 2
解答:令工为该运动员从第1天到第天比赛的总次数,1≤i≤25,Vx;:x;∈{1,…,41 因此对所有的x成立x2+8≤49。由于x1,x2,…,x25,x1+8,x2+8,…,x25+8共50个元素,且 每个元素均在集合{1,…,49}中,所以必存在两个元素相等 由于该运动员每天至少比赛一场,所以对于所有的1≤i<j≤25,成立r<x。所以存在i,j 使得x1+8=xj。即该运动员在从第天到第j天间恰好进行了8场比赛 2.在边长为1的正三角形内任意放入n2+1个点,证明:一定存在两点,其距离不超过1/,其 解答:对三角形的三边进行n等分,并连接相应的等分点。当n=3时三角形的划分情况如图1所 示。因此,一个边长为1的正三角形被分成了n2个小三角形,且每个三角形的边长为1/。所以若 将n2+1个点放入大三角形中,由抽屉原则,至少有两个点A、B在同一个小三角形中。因为小三角 形的边长为1/m,所以A、B间的距离不超过1/m 3.证明 解答:在二项式系数中,令y=1,则得 (x+1)=∑C(n,k)x=1+∑C(m,k)x k=1 对上式两边求导,得 n(x+1)-1=∑AC(n,4)x-1 k=1 令x=1,则 kC(n, k)
)µ-xiT$Ä l11U1iU'mogê§1 ≤ i ≤ 25, ∀xi : xi ∈ {1, · · · , 41}" Ïdé¤kxi¤áxi + 8 ≤ 49"dux1, x2, · · · , x25, x1 + 8, x2 + 8, · · · , x25 + 850§ zþ38Ü{1, · · · , 49}¥§¤±73ü " duT$Ä zU'm|§¤±éu¤k1 ≤ i 1n/S?¿\n 2 + 1 :§y²µ½3ü:§ÙålØL1/n§Ù ¥n ∈ N" )µén/n>?1n ©§¿ëA ©:"n = 3n/y©¹Xã1¤ «" Ïd§>1n/©¤ n 2n/§ zn/>1/n"¤±e òn 2 + 1:\n/¥§dÄTK§kü:A!B3Ón/¥"Ïn />1/n§¤±A!BmålØL1/n" ✐ 3©y²µ Xn k=1 kC(n, k) = n2 n−1 )µ3ªXꥧ-y = 1§Kµ (x + 1)n = Xn k=0 C(n, k)x k = 1 +Xn k=1 C(n, k)x k éþªü>¦§µ n(x + 1)n−1 = Xn k=1 kC(n, k)x k−1 -x = 1§Kµ n2 n−1 = Xn k=1 kC(n, k) 3
C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1) 解答: 右边=(m+ m m! (n-1 n(m+n).+ mn!(m+n) m(m +n) m!n! (m+n) (m+n)! min =左边 5.证明 C(m,0)C(m,n)+C(m,1)C(m-1,n-1)+…+C(m,n)C(m-n,0)=2"C(m,n 解答:利用组合意义对此恒等式进行证明:假设有m个球,现要求取出其中的n个球并放入A,B两 个有区别的袋子中,求放置方法的总数。 恒等式左边的意义:可从m个球中先取出个球放入A袋中,并在剩余的m-i个球中取出n-i个 球放入B袋中,其中0≤i≤n。所以方法总数为C(m,0)C(m,n)+C(m,1)C(m-1,n-1)+…+ C(m, n)C(m-n, O 恒等式右边的意义:可从m个球中首先取出n个球。对于取出n个球中的每个球,都可将该球放 入A袋或不放入A袋(放入B袋)共两种可能性,所以方法总数为2C(m,n) 综上所述,恒等式成立
✐ 4©y²µ C(m + n, m) = C(m + n − 1, m) + C(m + n − 1, m − 1) )µ m> = (m + n − 1)! m!(n − 1)! + (m + n − 1)! (m − 1)!n! = n(m + n)! m!n!(m + n) + m(m + n)! m!n!(m + n) = (m + n)! m!n! = > (1) ✐ 5©y²µ C(m, 0)C(m, n) + C(m, 1)C(m − 1, n − 1) + · · · + C(m, n)C(m − n, 0) = 2nC(m, n) )µ|^|Ü¿Âédð ª?1y²µbkm¥§y¦ÑÙ¥n¥¿\A§Bü k«Of¥§¦{oê" ð ª>¿Âµlm¥¥kÑi¥\A¥§¿3{m−i¥¥Ñn−i ¥\B¥§Ù¥0 ≤ i ≤ n"¤±{oêC(m, 0)C(m, n) + C(m, 1)C(m − 1, n − 1) + · · · + C(m, n)C(m − n, 0) ð ªm>¿Âµlm¥¥ÄkÑn¥"éuÑn¥¥z¥§ÑòT¥ \A½Ø\A£\B¤ü«U5§¤±{oê2 nC(m, n)" nþ¤ã§ð ª¤á" ✐ 4