組合數(shù)學(xué)課件第一章排列組合習(xí)題.ppt

第一章習(xí)題,1.證任一正整數(shù)n可唯一地表成如下形式： n=aii!,0aii,i1,2,。 解 2.證 nC(n-1,r) = (r+1)C(n,r+1).并給出組合意義。解 3.證kC(n,k)=n2 。解 4.有n個(gè)不同的整數(shù)，從中取出兩組來， 要求第一組數(shù)里的最小數(shù)大于第二組的最大數(shù)。問有多少種方案？解,i1,i1,k,n-1,5.六個(gè)引擎分列兩排，要求引擎的點(diǎn)火的次序兩排交錯(cuò)開來，試求從一特定引擎開始點(diǎn)火有多少種方案。解 6.試求從1到1000000的整數(shù)中，0出現(xiàn)了多少次？解 7.n個(gè)男n個(gè)女排成一男女相間的隊(duì)伍，試問有多少種不同的方案？若圍成一圓桌坐下，又有多少種不同的方案？解 8.n個(gè)完全一樣的球，放到r個(gè)有標(biāo)志的盒子,nr,要求無一空盒，試證其方案數(shù)為( ).解,n-1 r-1,9.設(shè) n=p1 p2 pl ,p1、p2、pl是l個(gè)不同的素?cái)?shù)，試求能整除盡數(shù)n的正整數(shù)數(shù)目.解 10.試求n個(gè)完全一樣的骰子擲出多少種不同的方案？解 11.凸10邊形的任意三個(gè)對(duì)角線不共點(diǎn)，試求這凸10邊形的對(duì)角線交于多少個(gè)點(diǎn)？又把所有對(duì)角線分割成多少段？解 12.試證一整數(shù)是另一個(gè)整數(shù)的平方的必要條件是除盡它的數(shù)目為奇數(shù)。解,a1 a2 al,13.統(tǒng)計(jì)力學(xué)需要計(jì)算r個(gè)質(zhì)點(diǎn)放到n個(gè)盒子里去,并服從下列假定之一，問有多少種不同的圖象。假設(shè)盒子始終是不同的。(a)Maxwell-Boltzmann假定：r個(gè)質(zhì)點(diǎn)是不同的，任何盒子可以放任意數(shù)個(gè). (b)Bose-Einstein假定：r個(gè)質(zhì)點(diǎn)完全相同，每一個(gè)盒子可以放任意數(shù)個(gè). (c)Fermi-Dirac假定：r個(gè)質(zhì)點(diǎn)都完全相同，每盒不超過一個(gè).解,14.從26個(gè)英文字母中取出6個(gè)字母組成一字，若其中有2或3個(gè)母音，問分別可構(gòu)成多少個(gè)字(不允許重復(fù))？解 15.給出( )( )+( )( )+( )( )+ ( )( )= ( )的組合意義。解 16.給出( )+( )+( )+( )=( )的組合意義。解,n m,r 0,n-1 m-1,n-2 m-2,n-m 0,n+r+1 m,r+1 1,r+2 2,r+m m,r r,r+1 r,r+2 r,n r,n+1 r+1,17.證明：解( )( )+( )( )+( )( )+( )( )=2 ( ) 18.從n個(gè)人中選r個(gè)圍成一圓圈，問有多少種不同的方案？解 19.分別寫出按照字典序由給定排列計(jì)算其對(duì)應(yīng)序號(hào)的算法及由給定序號(hào)計(jì)算其對(duì)應(yīng)排列的算法。(解略) 20.(a)按照第19題的要求，寫出鄰位對(duì)換法(排列的生成算法之二)的相應(yīng)算法。 (b)寫出按照鄰位對(duì)換法由給定排列生成其下一個(gè)排列的算法。(解略),m 0,m n,m 1,m 2,m n,m n,m-1 n-1,m-2 n-2,m-n 0,n,21.對(duì)于給定的正整數(shù)n,證明當(dāng) 22.(a)用組合方法證明 和 都是整數(shù). (b)證明 是整數(shù). 解 23.(a)在2n個(gè)球中,有n個(gè)相同,求從這2n個(gè) 球中選取n個(gè)的方案數(shù)。 (b)在3n+1個(gè)球中，有n個(gè)相同，求從這3n+1個(gè)球中選取n個(gè)的方案數(shù)。解,k=,n-1 2,n 2,n+1 2,時(shí)，C(n,k)是最大值。解,若n是奇數(shù) 若n是偶數(shù),(2n)! (3n)! 2 2 3,n n n,(n )! (n!),n+1,2,24.證明在由字母表0,1,2生成的長(zhǎng)度為n的字符串中. (a)0出現(xiàn)偶數(shù)次的字符串有個(gè)； (b) ( )2 +( )2 +( )2 = ， 其中q=2 . 解 25. 5臺(tái)教學(xué)機(jī)器m個(gè)學(xué)生使用，使用第1臺(tái)和第2臺(tái)的人數(shù)相等，有多少種分配方案？解,n 0,n 2,n q,3 +1 2,3 +1 2,n,n-1,n-q,n,n,n 2,26.在由n個(gè)0及n個(gè)1構(gòu)成的字符串中，任意前k個(gè)字符中，0的個(gè)數(shù)不少于1的個(gè)數(shù)的字符串有多少？解 27.在1到n的自然數(shù)中選取不同且互不相鄰的k個(gè)數(shù)，有多少種選取方案？解 28.(a)在5個(gè)0，4個(gè)1組成的字符串中，出現(xiàn)01或10的總次數(shù)為4的，有多少個(gè)？ (b)在m個(gè)0，n個(gè)1組成的字符串中,出現(xiàn)01或10的總次數(shù)為k的，有多少個(gè)？解,習(xí)題解答,1.證：對(duì)n用歸納法。題,先證可表示性： 當(dāng)n=0,1時(shí)，命題成立。 假設(shè)對(duì)小于n的非負(fù)整數(shù)，命題成立。 對(duì)于n,設(shè)k!n(k+1)!,即0n-k!kk! 由假設(shè)對(duì)n-k!,命題成立， 設(shè)n-k!=aii!，其中akk-1, n=aii!+k!，命題成立。,i=1,k,i=1,k,再證表示的唯一性： 設(shè)n=aii!=bii!, 不妨設(shè)ajbj,令j=maxi|aibi ajj!+aj-1(j-1)!+a11! =bjj!+bj-1(j-1)!+b11!, (aj-bj)j!=(bi-ai)i!j!ii! |bi-ai|i!(bi-ai)i! 另一種證法：令j=mini|aibi aii!=bii!, 兩邊被(j+1)!除,得余數(shù)ajj!=bjj!,矛盾.,i=1,k,i=1,k,i=1,j-1,i=1,j-1,i=1,j-1,i=1,j-1,ij,ij,2.證：題 組合意義： 等式左邊：n個(gè)不同的球，先任取出1個(gè)，再?gòu)挠嘞碌膎-1個(gè)中取r個(gè)； 等式右邊：n個(gè)不同球中任意取出r+1個(gè)，并指定其中任意一個(gè)為第一個(gè)。 顯然兩種方案數(shù)相同。,nC(n-1,r) = n = ,(n-1)! (r+1)n! r!(n-r-1)! (r+1)r!(n-r-1)!,= = (r+1)C(n,r+1).,(r+1)n! (r+1)!(n-r-1)!,3.證： 題 設(shè)有n個(gè)不同的小球，A、B兩個(gè)盒子,A盒中恰好放1個(gè)球,B盒中可放任意個(gè)球。有兩種方法放球： 先從n個(gè)球中取k個(gè)球(k1),再?gòu)闹刑粢粋€(gè)放入A盒,方案數(shù)共為kC(n,k),其余球放入B盒。 先從n個(gè)球中任取一球放入A盒，剩下n-1個(gè)球每個(gè)有兩種可能，要么放入B盒，要么不放，故方案數(shù)為n2 . 顯然兩種方法方案數(shù)應(yīng)該一樣。,k=1,n,n-1,4.解：設(shè)取的第一組數(shù)有a個(gè),第二組有b個(gè),而要求第一組數(shù)中最小數(shù)大于第二組中最大的，即只要取出一組m個(gè)數(shù)(設(shè)m=a+b),從大到小取a個(gè)作為第一組,剩余的為第二組。此時(shí)方案數(shù)為 C(n,m)。從m個(gè)數(shù)中取第一組數(shù)共有m-1中取法?？偟姆桨笖?shù)為(m-1)C(n,m)=n2 +1. 題 5.解：第1步從特定引擎對(duì)面的3個(gè)中取1個(gè)有C(3,1)種取法，第2步從特定引擎一邊的2個(gè)中取1個(gè)有C(2,1)種取法，第3步從特定引擎對(duì)面的2個(gè)中取1個(gè)有C(2,1)中取法，剩下的每邊1個(gè)取法固定。 題 所以共有C(3,1)C(2,1)C(2,1)=12種方案。,m=2,n,n-1,6.解：首先所有數(shù)都用6位表示，從000000到999999中在每位上0出現(xiàn)了10 次,所以0共出現(xiàn)了610 次,0出現(xiàn)在最前面的次數(shù)應(yīng)該從中去掉，000000到999999中最左1位的0出現(xiàn)了10 次，000000到099999中左數(shù)第2位的0出現(xiàn)了10 次，000000到009999左數(shù)第3位的0出現(xiàn)了10 次, 000000到000999左數(shù)第4位的0出現(xiàn)了10 次, 000000到000099左數(shù)第5位的0出現(xiàn)了10 次, 000000到000009左數(shù)第6位的0出現(xiàn)了10 次。 另外1000000的6個(gè)0應(yīng)該被加上。 所以0共出現(xiàn)了 610 10 10 10 10 10 10 +6 = 488895次。,5,5,5,4,3,2,1,0,5,5,4,3,2,1,0,題,7.解：把n個(gè)男、n個(gè)女分別進(jìn)行全排列，然后按乘法法則放到一起，而男女分別在前面,應(yīng)該再乘2,即方案數(shù)為2(n!) 個(gè). 圍成一個(gè)圓桌坐下，根據(jù)圓排列法則，方案數(shù)為2 (n!) /(2n)個(gè).題 8.證：每個(gè)盒子不空，即每個(gè)盒子里至少放一個(gè)球，因?yàn)榍蛲耆粯?，問題轉(zhuǎn)化為將n-r個(gè)小球放入r個(gè)不同的盒子，每個(gè)盒子可以放任意個(gè)球，可以有空盒，根據(jù)可重組合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)中方案。 根據(jù)C(n,r)=C(n,n-r),可得 C(n-1,n-r)=C(n-1,n-1-(n-r)=C(n-1,r-1)個(gè)方案。證畢。題,2,2,9.解：每個(gè)能整除盡數(shù)n的正整數(shù)都可以選取每個(gè)素?cái)?shù)pi從0到ai次，即每個(gè)素?cái)?shù)有ai+1種選擇，所以能整除n的正整數(shù)數(shù)目為(a1+1)(a2+1)(al+1)個(gè)。題 10.解：相當(dāng)于把n個(gè)小球放入6個(gè)不同的盒子里，為可重組合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。題 11.解：根據(jù)題意,每4個(gè)點(diǎn)可得到兩條對(duì)角線,1個(gè)對(duì)角線交點(diǎn),從10個(gè)頂點(diǎn)任取4個(gè)的方案有C(10,4)中,即交于210個(gè)點(diǎn)。,11.(續(xù)前頁)根據(jù)圖論知識(shí)，每個(gè)對(duì)角線交點(diǎn)有4個(gè)度，每個(gè)頂點(diǎn)去掉與相鄰兩個(gè)頂點(diǎn)的連線還有7個(gè)度，可以得到 210 4 + 10 7 2 12.證：根據(jù)第9題的結(jié)論， n= p1 p2 pl , 能被(a1+1)(a2+1)(al+1)個(gè)數(shù)整除，而n = p1 p2 pl ,能被(2a1+1)(2a2+1)(2al+1)個(gè)數(shù)整除，2ai+1為奇數(shù)(0il) ，所以乘積為奇數(shù)。 證畢。題, = 455條邊 題,a1 a2 al,2,2a1 2a2 2al,13.解： 題 (a) 每個(gè)質(zhì)點(diǎn)放入盒子都有n種選擇，r個(gè)質(zhì)點(diǎn)共有r 種不同的圖案。 (b) 可重組合，共有C(n+r-1,r)種圖案。 (c) 一般組合問題，共有C(n,r)種圖案。 14.解：題 其中有2個(gè)母音可構(gòu)成C(21,4)C(5,2)6!個(gè)字。 其中有2個(gè)母音可構(gòu)成C(21,3)C(5,3)6!個(gè)字。,n,15.解：題 如圖：,-r-1 -1 0 m-n x,y,m,A(-1,m),B(m-n,m),可看作是格路問題：左邊第i項(xiàng)為從點(diǎn)C 到點(diǎn)(-1,i)直接經(jīng)過(0,i)的路徑,再到點(diǎn)B 的所有路徑數(shù)。左邊所有項(xiàng)的和就是從 點(diǎn)C到B的所有路徑數(shù)即為右邊的意義。,C(-r-1,0),16.解：C(n+1,r+1)是指從n+1個(gè)元素a1, a2,an+1中任取r+1個(gè)進(jìn)行組合的方案數(shù)。左邊：若一定要選an+1,則方案數(shù)為C(n,r).若不選an+1,一定要選an,則方案數(shù)為C(n-1,r).若不選an+1,an,ar+2,則方案數(shù)為C(r,r).題 所有這些可能性相加就得到了總方案數(shù)。 17.證：組合意義,右邊：m個(gè)球,從中取n個(gè),放入兩個(gè)盒子,n個(gè)球中每個(gè)球都有兩種放法,得到可能的方案數(shù)。左邊：第i項(xiàng)的意義是一個(gè)盒子中放i個(gè),另一個(gè)盒子放n-i個(gè),所有的方案數(shù)相加應(yīng)該等于右邊。,17.(續(xù)前頁)數(shù)學(xué)證明： 左邊=C(m,k)C(m-k,n-k) = = =C(m,n) =2 C(m,n)=右邊 證畢。題,k=0,n,m! (m-k)! k!(m-k)! (n-k)!(m-n)!,k=0,n,k=0,n,m! n! k!n! (n-k)!(m-n)!,n! k!(n-k)!,k=0,n,n,18.解：圓排列:共有P(n,r)/r種不同的方案。 19.(略) 18題 20.(略) 21.證：取C(n,k)和C(n,k-1)進(jìn)行比較。C(n,k)/C(n,k-1)=(n-k+1)/k。 當(dāng)kn/2時(shí),(n-k+1)/k1,即C(n,k)C(n,k-1)得到當(dāng)k為最接近n/2的數(shù)時(shí)，C(n,k)取到最大值。題,22.證：(a)設(shè)有2n個(gè)不同球放入n個(gè)不同的盒子里，每盒兩個(gè)，這個(gè)方案數(shù)應(yīng)該是整數(shù)。對(duì)2n個(gè)球進(jìn)行排列得到方案數(shù)為(2n)!。而把2個(gè)球放入同一個(gè)盒子里不計(jì)順序，應(yīng)該把全排列數(shù)除掉這些重復(fù)計(jì)算的次數(shù)，n個(gè)盒子內(nèi)部的排列共重復(fù)計(jì)算了2 次。得到2n個(gè)不同球放入n個(gè)不同的盒子里，每盒兩個(gè)的方案數(shù)(2n)!/2 若有3n個(gè)不同的球,放入n個(gè)不同盒子,故同理得(3n)!/(3!) 是整數(shù)。,n,n,n,22.(接上頁) (b)有n 個(gè)不同的球，放入n個(gè)相同的盒子里，每盒n個(gè)，求方案數(shù)，方案數(shù)應(yīng)該是一個(gè)整數(shù)。按前面(a)的方法，應(yīng)該得到(n )!/(n!) 是整數(shù)。另外由于n個(gè)盒子相同，放入不同的盒子是沒有區(qū)別的，應(yīng)該把n個(gè)盒子的排列數(shù)n!除去。 因此得到(n )!/(n!) 是整數(shù)。題,2,n,2,n+1,23.解： 題 (a) 相當(dāng)于從n個(gè)不同的小球中分別取出m個(gè)小球(0mn)，再?gòu)膎個(gè)相同的小球中取出n-m個(gè)小球。共有方案： C(n,0)+C(n,1)+C(n,n)=2 種。 (b)相當(dāng)于從2n+1個(gè)不同的小球中分別取出m個(gè)小球(0mn)，再?gòu)膎個(gè)相同的小球中取出n-m個(gè)小球。共有方案： C(2n+1,0)+C(2n+1,1)+C(2n+1,n)種。,n,24.證：(a)歸納法：題 當(dāng)n=1時(shí),0出現(xiàn)偶數(shù)次的字符串有(3 +1)/2 =2個(gè)(即1,2),成立。假設(shè)當(dāng)n=k時(shí),0出現(xiàn)偶數(shù)次的字符串有(3 +1)/2 種?？偟淖址? 種。0出現(xiàn)奇數(shù)次的字符串有(3 -1)/2 種。當(dāng)n=k+1時(shí)，0出現(xiàn)偶數(shù)次的字符串包括兩部分：n=k時(shí),0出現(xiàn)偶數(shù)次再增加一位不是0的，共有2(3 +1)/2種，0出現(xiàn)奇數(shù)次再增加一位0,共有(3 1)/2種。所以共有2(3 +1)/2+(3 1)/2=(3 +1)/2種，證畢。(b) 等式左邊第m項(xiàng)是0出現(xiàn)m次的字符串?dāng)?shù)，總和就是0出現(xiàn)偶數(shù)次的字符串?dāng)?shù)，右邊由(a)得是0出現(xiàn)偶數(shù)次的字符串?dāng)?shù)，兩邊顯然相等。,1,k,k,k,k,k,k,k,k+1,25.解：當(dāng)使用第1臺(tái)機(jī)器的學(xué)生為n個(gè)時(shí)，使用第2臺(tái)機(jī)器的學(xué)生也為n,從m個(gè)學(xué)生中選出2n個(gè)使用這兩臺(tái)機(jī)器，剩余的學(xué)生可以任意使用剩下的機(jī)器的組合數(shù)為C(m,2n)C(2n,n)(m-2n)。所以總的