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

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

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

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

4、個數(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。設(shè)從1200中任意選取的70個數(shù)構(gòu)成一組，即第一組： ；第二組： ；第三組：；顯然，這三組數(shù)均在1209之間，且共有3*70=210個數(shù)，根據(jù)鴿巢原理一定有兩個數(shù)相等，又因為任取的這70個數(shù)均不相同，所以這2個相等的數(shù)一定來自不同組，根據(jù)不同組的分布討論如下：1） 如果這兩個數(shù)分別來自第一組和第二組，則有；2） 如果這兩個數(shù)分別來自第一組和第三組，則

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

6、1個相同的小球放到3個不同的盒子里，有種方案，而不符合題意的擺法是有一排至少有n+1個座位。這相當(dāng)于將n+1個座位先放到3排中的某一排，再將剩下的2n+1-(n+1)=n個座位任意分到3排中，這樣的擺法共有種方案，所以符合題意的擺法有：方法2：設(shè)第一排座位有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-n-1，可知y1+y2+y3=2(2n+1)-

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

8、是有一排至少有n個座位。這相當(dāng)于將n個座位先放到3排中的某一排，再將剩下的2n-n=n個座位任意分到3排中，這樣的擺法共有種方案。需要注意的是，三排中如果任意兩排都是n個座位共有3種情況，這3種情況在中被重復(fù)計算了2次，因此需要將重復(fù)減去的3次加上。所以符合題意的擺法有：方法2：設(shè)第一排座位有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且yi0，1i3。顯然，x方程滿足要求的解與y方

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

10、視調(diào)查表明，有20%的用戶收看A，16%的用戶收看B，14%的用戶收看C，8%的用戶收看A和B，5%的用戶收看A和C，4%的用戶收看B和C，2%的用戶都看。求不收看A,B,C任何頻道的用戶百分比？解：設(shè)性質(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名大學(xué)新生的愛好進(jìn)行調(diào)查，結(jié)果發(fā)現(xiàn)他們喜歡看球賽和電影、戲劇。其中58人喜歡看球賽，38人喜歡看戲劇，52人喜歡看電影，既喜歡看球賽又喜歡看戲劇的有18人，既喜

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

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

13、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五種型號的轎車，用紅、白、藍(lán)、綠、黑五種顏色進(jìn)行涂裝。要求A型車不能涂成黑色；B型車不能涂成紅色和白色；C型車不能涂成白色和綠色；D型車不能涂綠色和藍(lán)色；E型號車不能涂成藍(lán)色，求有多少種涂裝方案？解：ABCDE紅白藍(lán)綠黑ABCDE藍(lán)綠白紅黑ABCDE紅白綠藍(lán)黑1.若未規(guī)定不同車型必須涂不同顏色，則：涂裝方案2.若不同車型必須涂不同顏色，則：禁區(qū)的棋盤多項式為：R()=R()R()=(1+x)(xR()+R()=(1+x)(xR()

14、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習(xí)題五5.1 求如下數(shù)列的生成函數(shù)。（1）；（2）；（3）； （4）；（5）； （6）；解：5.3 已知數(shù)列的生成函數(shù)是，求.5.15 知數(shù)列的指數(shù)生成函數(shù)是，求。6.5 平面上有n條直線，它們兩兩相交且沿有三線交于一點，設(shè)這n條直線把平面分成個區(qū)域，求的遞推關(guān)系并求解.解：設(shè)n-1

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

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

17、 求下列n階行列式的值解：當(dāng)n=1時，當(dāng)n=2時，當(dāng)n>2時，先求解這個遞推關(guān)系的通解，它的特征方程為解這個方程，得所以，通解為代入初值來確定和，得 求解這個方程組，得 所以，原遞推關(guān)系的解為 （）.6.9設(shè)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