組合數(shù)學課后答案

1、文檔供參考，可復制、編制，期待您的好評與關注！ 作業(yè)習題答案習題二2.1證明：在一個至少有2人的小組中，總存在兩個人，他們在組內(nèi)所認識的人數(shù)相同。證明：假設沒有人誰都不認識：那么每個人認識的人數(shù)都為1,n-1，由鴿巢原理知，n個人認識的人數(shù)有n-1種，那么至少有2個人認識的人數(shù)相同。假設有1人誰都不認識：那么其他n-1人認識的人數(shù)都為1,n-2，由鴿巢原理知，n-1個人認識的人數(shù)有n-2種，那么至少有2個人認識的人數(shù)相同。2.3證明：平面上任取5個坐標為整數(shù)的點，則其中至少有兩個點，由它們所連線段的中點的坐標也是整數(shù)。證明：方法一：有5個坐標，每個坐標只有4種可能的情況：（奇數(shù)，偶數(shù)）；（奇數(shù)

2、，奇數(shù)）；（偶數(shù)，偶數(shù)）；（偶數(shù)，奇數(shù)）。由鴿巢原理知，至少有2個坐標的情況相同。又要想使中點的坐標也是整數(shù)，則其兩點連線的坐標之和為偶數(shù)。因為 奇數(shù)+奇數(shù) = 偶數(shù) ； 偶數(shù)+偶數(shù)=偶數(shù)。因此只需找以上2個情況相同的點。而已證明：存在至少2個坐標的情況相同。證明成立。方法二：對于平面上的任意整數(shù)坐標的點而言，其坐標值對2取模后的可能取值只有4種情況，即：(0,0) ,(0,1) ,(1,0), (1,1)，根據(jù)鴿巢原理5個點中必有2個點的坐標對2取模后是相同類型的，那么這兩點的連線中點也必為整數(shù)。2.4一次選秀活動，每個人表演后可能得到的結果分別為“通過”、“淘汰”和“待定”，至少有多少人參

3、加才能保證必有100個人得到相同的結果？證明： 根據(jù)推論2.2.1，若將3*（100-1）+1=298個人得到3種結果，必有100人得到相同結果。2.9將一個矩形分成(m+1)行列的網(wǎng)格每個格子涂1種顏色，有m種顏色可以選擇，證明：無論怎么涂色，其中必有一個由格子構成的矩形的4個角上的格子被涂上同一種顏色。證明： （1）對每一列而言，有（m+1）行，m種顏色，有鴿巢原理，則必有兩個單元格顏色相同。 （2）每列中兩個單元格的不同位置組合有種，這樣一列中兩個同色單元格的位置組合共有 種情況 （3）現(xiàn)在有列，根據(jù)鴿巢原理，必有兩列相同。證明結論成立。2.11證明：從S=1,3,5,599這300個奇

4、數(shù)中任意選取101個數(shù)，在所選出的數(shù)中一定存在2個數(shù)，它們之間最多差4。證明： 將S劃分為1,3,5，7,9,11, 595,597,599共100組，由鴿巢原理知任意選取101個數(shù)中必存在2個數(shù)來自同一組，即其差最多為4.2.12證明：從1200中任意選取70個數(shù)，總有兩個數(shù)的差是4，5或9。設從1200中任意選取的70個數(shù)構成一組，即第一組： ；第二組： ；第三組：；顯然，這三組數(shù)均在1209之間，且共有3*70=210個數(shù)，根據(jù)鴿巢原理一定有兩個數(shù)相等，又因為任取的這70個數(shù)均不相同，所以這2個相等的數(shù)一定來自不同組，根據(jù)不同組的分布討論如下：1） 如果這兩個數(shù)分別來自第一組和第二組，則

5、有；2） 如果這兩個數(shù)分別來自第一組和第三組，則有；3） 如果這兩個數(shù)分別來自第二組和第三組，則有；得證。習題三3.8 確定多重集的11-排列數(shù)？3.9 求方程，滿足的整數(shù)解的個數(shù)。3.10 架上有20卷百科全書，從中選出4卷使得任意兩本的卷號都不相鄰的選法有多少種？解：n=20，r=4，3.17 一局乒乓球比賽中，運動員甲以11:7戰(zhàn)勝運動員乙，若在比賽過程中甲從來沒有落后過，求有多少種可能的比分記錄？解：根據(jù)題意，相當于求從點(0,0)到點(11,7)且從下方不穿過y=x的非降路徑數(shù)，即為：3.21 1)會議室中有2n+1個座位，現(xiàn)擺成3排，要求任意兩排的座位都占大多數(shù)，求有多少種擺法？解

6、：(1)方法1：如果沒有附加限制則相當于把2n+1個相同的小球放到3個不同的盒子里，有種方案，而不符合題意的擺法是有一排至少有n+1個座位。這相當于將n+1個座位先放到3排中的某一排，再將剩下的2n+1-(n+1)=n個座位任意分到3排中，這樣的擺法共有種方案，所以符合題意的擺法有：方法2：設第一排座位有x1個，第二排座位有x2個，第三排座位有x3個。x1+x2+x3=2n+1，且x1+x2(2n+1)/2，x1+x3(2n+1)/2，x2+x3(2n+1)/2，即x1+x2n+1，x1+x3n+1，x2+x3n+1，令y1= x1+x2-n-1，y2= x1+x3-n-1，y3= x2+x3

7、-n-1，可知y1+y2+y3=2(2n+1)-3(n+1)=n-1且yi0，1i3。顯然，x方程滿足要求的解與y方程非負整數(shù)解一一對應，有種。方法3：要求每行非空如果沒有附加限制則相當于把2n+1個相同的小球放到3個不同的盒子里，不允許為空，有種方案，而不符合題意的擺法是有一排至少有n+1個座位。這相當于將n個座位先放到3排中的某一排，再將剩下的2n+1-n=n+1個座位任意分到3排中，每排不允許為空，這樣的擺法共有種方案，所以符合題意的擺法有：(2)會議室中有2n個座位，現(xiàn)擺成3排，要求任意兩排的座位都占大多數(shù)，求有多少種擺法？解：(2)方法1：如果沒有附加限制則相當于把2n個相同的小球放

8、到3個不同的盒子里，有種方案，而不符合題意的擺法是有一排至少有n個座位。這相當于將n個座位先放到3排中的某一排，再將剩下的2n-n=n個座位任意分到3排中，這樣的擺法共有種方案。需要注意的是，三排中如果任意兩排都是n個座位共有3種情況，這3種情況在中被重復計算了2次，因此需要將重復減去的3次加上。所以符合題意的擺法有：方法2：設第一排座位有x1個，第二排座位有x2個，第三排座位有x3個。x1+x2+x3=2n，且x1+x2n+1，x1+x3n+1，x2+x3n+1，令y1=x1+x2-n-1，y2=x1+x3-n-1，y3=x2+x3-n-1，可知y1+y2+y3=2(2n)-3n-3=n-3

9、且yi0，1i3。顯然，x方程滿足要求的解與y方程非負整數(shù)解一一對應，有種。方法3：要求每行非空如果沒有附加限制則相當于把2n個相同的小球放到3個不同的盒子里，不允許為空，有種方案，而不符合題意的擺法是有一排至少有n個座位。這相當于將n-1個座位先放到3排中的某一排，再將剩下的2n-(n-1)=n+1個座位任意分到3排中，每排不允許為空，這樣的擺法共有種方案，所以符合題意的擺法有：3.24 n(n2)個不同的球分給甲、乙、丙3人，使得甲至少分得兩個球，有多少種不同的分法？解：3.25 24個相同的球分堆，使得每堆的球不少于5，有多少種不同的分堆方法？方法1： 每堆去掉4個球，剩余球分堆的方法數(shù)

10、其中習題四4.3 一項對于A,B,C三個頻道的收視調(diào)查表明，有20%的用戶收看A，16%的用戶收看B，14%的用戶收看C，8%的用戶收看A和B，5%的用戶收看A和C，4%的用戶收看B和C，2%的用戶都看。求不收看A,B,C任何頻道的用戶百分比？解：設性質(zhì)P1是收看A頻道的用戶百分比；P2是收看B頻道的用戶百分比；P3是收看C頻道的用戶百分比；Ai=x|xSx具有性質(zhì)Pi，i=1,2,3。S是受調(diào)查的所有用戶的集合。；根據(jù)定理4.1.1，有ACB2327696654.4 某雜志對100名大學新生的愛好進行調(diào)查，結果發(fā)現(xiàn)他們喜歡看球賽和電影、戲劇。其中58人喜歡看球賽，38人喜歡看戲劇，52人喜歡

11、看電影，既喜歡看球賽又喜歡看戲劇的有18人，既喜歡看電影又喜歡看戲劇的有16人，三種都喜歡看的有12人，求有多少人只喜歡看電影？解：方法1：設性質(zhì)P1喜歡看球賽；P2喜歡看戲?。籔3喜歡看電影。Ai=x|xSx具有性質(zhì)Pi，i=1,2,3。S是100名大學新生的集合。由題意可得，這100名大學生中每人至少有三種興趣中的一種，所以可得既喜歡看球賽有喜歡看電影的人有 因此只喜歡看電影的人有=52-(26+16)+12=22人方法2：方法3：設只喜歡看球賽的人數(shù)為x；設只喜歡看電影的人數(shù)為y；喜歡看球賽和電影但不喜歡看戲劇的人數(shù)為z，則解得y=22，所以22人只喜歡看電影。球賽戲劇電影1264161

12、426224.5 某人有六位朋友，他跟這些朋友每一個都一起吃過晚餐12次，跟他們中任二位一起吃過6次晚餐，和任意三位一起吃過4次晚餐，和任意四位一起吃過3次晚餐，任意五位一起吃過2次晚餐，跟六位朋友全部一起吃過一次晚餐，另外，他自己在外吃過8次晚餐而沒碰見任何一位朋友，問他共在外面吃過幾次晚餐?解：設n為在外面共吃過晚餐的次數(shù)，性質(zhì)Pi(1£i£6)表示他和第i位朋友吃過晚餐，Ai(1£i£6)表示他和第i位朋友吃過晚餐的次數(shù)。顯然滿足對稱篩公式，其中由題可得方程：解得吃飯次數(shù)為4.13計算棋盤多項式R()。解：R() = x*R()+R() =x*(1

13、+3x+x2)+(1+x)*R( ) = x3+3x2+x+(1+x)xR()+R() = x3+3x2+x+(1+x)x(1+x)+(1+4x+2x2) = 5x3+12x2+7x+14.14 A,B,C,D,E五種型號的轎車，用紅、白、藍、綠、黑五種顏色進行涂裝。要求A型車不能涂成黑色；B型車不能涂成紅色和白色；C型車不能涂成白色和綠色；D型車不能涂綠色和藍色；E型號車不能涂成藍色，求有多少種涂裝方案？解：ABCDE紅白藍綠黑ABCDE藍綠白紅黑ABCDE紅白綠藍黑1.若未規(guī)定不同車型必須涂不同顏色，則：涂裝方案2.若不同車型必須涂不同顏色，則：禁區(qū)的棋盤多項式為：R()=R()R()=(

14、1+x)(xR()+R()=(1+x)(xR()R()+R()R()=(1+x)(x(1+2x) 2+(1+3x+x2)2)=1+8x+22x2+25x3+11x4+x5 所以： N =5!-r1×4!+r2×3!r3×2!+r4×1!- r5×0! =5！-8*4！+22*3！-25*2！+11*1！-1=20習題五5.1 求如下數(shù)列的生成函數(shù)。（1）；（2）；（3）； （4）；（5）； （6）；解：5.3 已知數(shù)列的生成函數(shù)是，求.5.15 知數(shù)列的指數(shù)生成函數(shù)是，求。6.5 平面上有n條直線，它們兩兩相交且沿有三線交于一點，設這n條直線把

15、平面分成個區(qū)域，求的遞推關系并求解.解：設n-1條直線把平面分成個區(qū)域，則第n條直線與前n-1條直線都有一個交點，即在第n條直線上有n-1個交點，并將其分成n段，這n段又把其所在的區(qū)域一分為二。6.6 一個的方格圖形用紅、藍兩色涂色每個方格，如果每個方格只能涂一種顏色，且不允許兩個紅格相鄰，設有種涂色方案，求的遞推關系并求解.解：設f(n)為的方格圖形的涂色方案。當n=1時，f(1)=2，即一個方格有紅、藍兩種涂色方案。當n=2時，f(2)=3，即兩個方格有（紅、藍），（藍、紅）、（藍、藍）三種涂色方案。由于不允許兩個紅格相鄰，所以不存在（紅、紅）的情況。當n>2時，如果第一個格子涂為藍

16、色，則剩余n-1個格子的涂色方案數(shù)為f(n-1)；如果第一個格子涂為紅色，由于不允許兩個紅格相鄰，所以第二個格子必為藍色，則剩余n-2個格子的涂色方案數(shù)為f(n-2)。于是，當n>2時涂色方案數(shù)為f(n)= f(n-1)+ f(n-2)。先求解這個遞推關系的通解，它的特征方程為解這個方程，得所以，通解為代入初值來確定和，得 求解這個方程組，得 所以，原遞推關系的解為 （）.6.7 核反應堆中有和兩種粒子，每秒鐘內(nèi)1個粒子可反應產(chǎn)生出3個粒子，而1個粒子又可反應產(chǎn)生出1個粒子和2個粒子.若在t=0s時刻反應堆中只有1個粒子，求t=100s時刻反應堆里將有多少個粒子和粒子.解：設t時刻反應堆

17、中粒子數(shù)為，粒子數(shù)為在t-1時刻在t時刻 6.8 求下列n階行列式的值解：當n=1時，當n=2時，當n>2時，先求解這個遞推關系的通解，它的特征方程為解這個方程，得所以，通解為代入初值來確定和，得 求解這個方程組，得 所以，原遞推關系的解為 （）.6.9設h(n)表示n+2條邊的凸多邊形為它的對角線劃分所得的區(qū)域數(shù)，其中假定沒有二條對角線在凸多邊形內(nèi)有一公共點。定義h(0)=0，對n=l，2，證明證明： 如圖所示，在凸n+2邊形中，劃出以任意兩相鄰邊為邊的三角形，例如ABC。則余下的是n+1個頂點的凸多邊形，它的對角線劃分所得的區(qū)域數(shù)為h(n-1)。由A點引出的對角線共有n-1條，分ABC為n塊。下面我們計算一下由A點引出的對角線對n+1條邊的凸