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

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

2、巢原理知，起碼有2個(gè)坐標(biāo)的狀況同樣。又要想使中點(diǎn)的坐標(biāo)也是整數(shù)，則其兩點(diǎn)連線的坐標(biāo)之和為偶數(shù)。因?yàn)槠鏀?shù)+奇數(shù)=偶數(shù)；偶數(shù)+偶數(shù)=偶數(shù)。所以只要找以上2個(gè)狀況同樣的點(diǎn)。而已證明：存在起碼2個(gè)坐標(biāo)的狀況同樣。證明建立。方法二：關(guān)于平面上的隨意整數(shù)坐標(biāo)的點(diǎn)而言，其坐標(biāo)值對(duì)2取模后的可能取值只有4種狀況，即：(0,0),(0,1),(1,0),(1,1)，依據(jù)鴿巢原理5個(gè)點(diǎn)中必有2個(gè)點(diǎn)的坐標(biāo)對(duì)2取模后是同樣種類的，那么這兩點(diǎn)的連線中點(diǎn)也必為整數(shù)。2.4一次選秀活動(dòng)，每一個(gè)人表演后可能獲得的結(jié)果分別為“經(jīng)過(guò)”、“裁減”和“待定”，起碼有多少人參加才能保證必有100個(gè)人獲得同樣的結(jié)果？證明：依據(jù)推論，若將

3、3*（100-1）+1=298個(gè)人獲得3種結(jié)果，必有100人獲得同樣結(jié)果。m12.9將一個(gè)矩形分紅(m+1)行m1列的網(wǎng)格每個(gè)格子涂1種顏色，有m種顏色能夠選擇，證明：不論2怎么涂色，此中必有一個(gè)由格子組成的矩形的4個(gè)角上的格子被涂上同一種顏色。證明：（1）對(duì)每一列而言，有（m+1）行，m種顏色，有鴿巢原理，則必有兩個(gè)單元格顏色同樣。（2m1）每列中兩個(gè)單元格的不一樣地點(diǎn)組合有種，這樣一列中兩個(gè)同色單元格的地點(diǎn)組合共有2m1m種狀況213）此刻有m1列，依據(jù)鴿巢原理，必有兩列同樣。證明結(jié)論建立。22.11證明：從S=1,3,5,599這300個(gè)奇數(shù)中隨意選用101個(gè)數(shù)，在所選出的數(shù)中必定存在2

4、個(gè)數(shù)，它們之間最多差證明：4。將S區(qū)分為1,3,5，7,9,11同一組，即其差最多為4.,595,597,599共100組，由鴿巢原理知隨意選用101個(gè)數(shù)中必存在2個(gè)數(shù)來(lái)自2.12證明：從1200中隨意選用70個(gè)數(shù)，總有兩個(gè)數(shù)的差是4，5或9。設(shè)從1200中隨意選用的70個(gè)數(shù)組成一組，即第一組：a1,a2,a70；第二組：a14,a24,a704；第三組：a19,a29,a709；明顯，這三組數(shù)均在1209之間，且共有3*70=210個(gè)數(shù)，依據(jù)鴿巢原理必定有兩個(gè)數(shù)相等，又因?yàn)槿稳〉倪@70個(gè)數(shù)均不同樣，所以這2個(gè)相等的數(shù)必定來(lái)自不一樣組，依據(jù)不一樣組的散布議論以下：1）假如這兩個(gè)數(shù)分別來(lái)自第一組

5、和第二組，則有ajai4；2）假如這兩個(gè)數(shù)分別來(lái)自第一組和第三組，則有ajai9；3）假如這兩個(gè)數(shù)分別來(lái)自第二組和第三組，則有ajai5；得證。習(xí)題三3.8確立多重集M3a,4b,5c的11-擺列數(shù)？3.9求方程x1x2x3x420，知足x12,x20,x35,x41的整數(shù)解的個(gè)數(shù)。3.10架上有20卷百科全書，從中選出4卷使得隨意兩本的卷號(hào)都不相鄰的選法有多少種？nr12041172380解：n=20，r=4，r443.17一局乒乓球競(jìng)賽中，運(yùn)動(dòng)員甲以11:7戰(zhàn)勝運(yùn)動(dòng)員乙，若在比勝過(guò)程中甲素來(lái)沒有落伍過(guò)，求有多少種可能的比分記錄？解：依據(jù)題意，相當(dāng)于求從點(diǎn)(0,0)到點(diǎn)(11,7)且從下方不

6、穿過(guò)y=x的非降路徑數(shù)，即為：3.211)會(huì)議室中有2n+1個(gè)座位，現(xiàn)擺成3排，要求隨意兩排的座位都占大部分，求有多少種擺法？解：(1)方法1：假如沒有附帶限制則相當(dāng)于把2n+1個(gè)同樣的小球放到3個(gè)不一樣的盒子里，有2n1312n3n+1個(gè)座位。這相當(dāng)于將n+1個(gè)座3-12種方案，而不切合題意的擺法是有一排起碼有位先放到3排中的某一排，再將剩下的2n+1-(n+1)=n個(gè)座位隨意分到3排中，這樣的擺法共有32n1(n1)31n223種方案，所以切合題意的擺法有：2方法2：設(shè)第一排座位有x1個(gè)，第二排座位有x2個(gè)，第三排座位有x3個(gè)。x1+x2+x3=2n+1，且x1+x2(2n+1)/2，x1

7、+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)-3(n+1)=n-1且yi0，1i3。明顯，x方程知足要求的解與y方程非負(fù)整數(shù)解一一對(duì)應(yīng)，有n131n1種。312方法3：要求每行非空假如沒有附帶限制則相當(dāng)于把2n+1個(gè)同樣的小球放到3個(gè)不一樣的盒子里，不一樣意為空，有2n112nn+1個(gè)座位。這相當(dāng)于將n個(gè)座位先放到3-1種方案，而不切合題意的擺法是有一排起碼有23排中的某一排，再將剩下的2n+1-n=n+1個(gè)座位隨意

8、分到3排中，每排不一樣意為空，這樣的擺法共有32n1n1n3種方案，所以切合題意的擺法有：22(2)會(huì)議室中有2n個(gè)座位，現(xiàn)擺成3排，要求隨意兩排的座位都占大部分，求有多少種擺法？解：(2)方法1：假如沒有附帶限制則相當(dāng)于把2n個(gè)同樣的小球放到3個(gè)不一樣的盒子里，有2n312n2n個(gè)座位。這相當(dāng)于將n個(gè)座位先放2種方案，而不切合題意的擺法是有一排起碼有2到3排中的某一排，再將剩下的2n-n=n個(gè)座位隨意分到3排中，這樣的擺法共有32nn31n2n3種情232種方案。需要注意的是，三排中假如隨意兩排都是個(gè)座位共有n22次，所以需要將重復(fù)減去的3次加上。所以切合題意的擺法況，這3種狀況在3中被重復(fù)

9、計(jì)算了2有：方法2：設(shè)第一排座位有x1個(gè)，第二排座位有x個(gè)，第三排座位有x個(gè)。x123，且12n，+x3n+1，x23n+1，令y1+x+x=2nx1+x12-n-1，213-n-1，323-n-1123=2(2n)-3n-3=n-3且x+x=x+xy=x+xy=x+xy+y+yyi0，1i3。明顯，x方程知足要求的解與y方程非負(fù)整數(shù)解一一對(duì)應(yīng)，有n331n1312種。方法3：要求每行非空假如沒有附帶限制則相當(dāng)于把2n個(gè)同樣的小球放到3個(gè)不一樣的盒子里，不一樣意為空，有2n12n1n個(gè)座位。這相當(dāng)于將n-1個(gè)座位先放到322種方案，而不切合題意的擺法是有一排起碼有排中的某一排，再將剩下的2n-

10、(n-1)=n+1個(gè)座位隨意分到3排中，每排不一樣意為空，這樣的擺法共有32n(n1)1n23種方案，所以切合題意的擺法有：23.24n(n2)個(gè)不一樣的球分給甲、乙、丙3人，使得甲起碼分得兩個(gè)球，有多少種不一樣的分法？n解：3n2nn2n1i22nii3.2524個(gè)同樣的球分堆，使得每堆的球許多于5，有多少種不一樣的分堆方法？方法1：每堆去掉4個(gè)球，節(jié)余球分堆的方法數(shù)此中習(xí)題四4.3一項(xiàng)關(guān)于A,B,C三個(gè)頻道的收視檢查表示，有C，8%的用戶收看A和B，5%的用戶收看20%的用戶收看A，16%的用戶收看B，14%的用戶收看A和C，4%的用戶收看B和C，2%的用戶都看。求不收看A,B,C任何頻道

11、的用戶百分比？解：設(shè)性質(zhì)P1是收看A頻道的用戶百分比；P2是收看B頻道的用戶百分比；P3是收看C頻道的用戶百分比；Ai=x|xSx擁有性質(zhì)Pi，i=1,2,3。S是受檢查的所實(shí)用戶的會(huì)合。|S|1；依據(jù)定理，有65A9632627BC4.4某雜志對(duì)100名大學(xué)重生的喜好進(jìn)行檢查，結(jié)果發(fā)現(xiàn)他們喜愛看球賽和電影、戲劇。此中58人喜愛看球賽，38人喜愛看戲劇，52人喜愛看電影，既喜愛看球賽又喜愛看戲劇的有18人，既喜愛看電影又喜愛看戲劇的有16人，三種都喜愛看的有12人，求有多少人只喜愛看電影？解：方法1：設(shè)性質(zhì)P1喜愛看球賽；P2喜愛看戲劇；P3喜愛看電影。Ai=x|xSx擁有性質(zhì)Pi，i=1,2

12、,3。S是100名大學(xué)重生的會(huì)合。由題意可得，這100名大學(xué)生中每人起碼有三種興趣中的一種，所以可得既喜愛看球賽有喜愛看電影的人有所以只喜愛看電影的人有=52-(26+16)+12=22人方法2：方法3：設(shè)只喜愛看球賽的人數(shù)為x；設(shè)只喜愛看電影的人數(shù)為y；喜愛看球賽和電影但不喜愛看戲劇的人數(shù)為z，則解得y=22，所以22人只喜愛看電影。球賽261461222416電影戲劇4.5某人有六位朋友，他跟這些朋友每一個(gè)都一同吃過(guò)晚飯意三位一同吃過(guò)4次晚飯，和隨意四位一同吃過(guò)12次，跟他們中任二位一同吃過(guò)6次晚飯，和任3次晚飯，隨意五位一同吃過(guò)2次晚飯，跟六位朋友所有一同吃過(guò)一次晚飯，此外，他自己在外吃

13、過(guò)餐?8次晚飯而沒遇見任何一位朋友，問他共在外面吃過(guò)幾次晚解：設(shè)n為在外面共吃過(guò)晚飯的次數(shù)，性質(zhì)Pi(1i6)表示他和第i位朋友吃過(guò)晚飯，Ai(1i6)表示他和第i位朋友吃過(guò)晚飯的次數(shù)。明顯知足對(duì)稱篩公式，此中由題可得方程：|A1A2A3A4A5A6|nC6112C626C634C643C652C6618解得吃飯次數(shù)為C6112C626C634C643C652C6618364.13計(jì)算棋盤多項(xiàng)式R()。解：R()=x*R()+R()=x*(1+3x+x2)+(1+x)*R()=x3+3x2+x+(1+x)xR()+R()322324.14A,B,C,D,E五種型號(hào)的轎車，用紅、白、藍(lán)、綠、黑五

14、種顏色進(jìn)行涂裝。要求車不可以涂成紅色和白色；C型車不可以涂成白色和綠色；D型車不可以涂綠色和藍(lán)色；A型車不可以涂成黑色；B型E型號(hào)車不可以涂成藍(lán)色，求有多少種涂裝方案？解：ABCDE紅白藍(lán)綠黑ABCDE藍(lán)綠白紅黑ABCDE紅白綠藍(lán)黑1.若未規(guī)定不一樣車型一定涂不一樣顏色，則：涂裝方案433344322.若不一樣車型一定涂不一樣顏色，則：禁區(qū)的棋盤多項(xiàng)式為：R()=R()R()=(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!-r14!+r23!r32!+r41

15、!-r50!=5！-8*4！+22*3！-25*2！+11*1！-1=20習(xí)題五5.1求以下數(shù)列的生成函數(shù)。（1）ak(1)k(k1)；（2）ak(1)kk2k；（3）akk6；（4）akk(k2)；（5）aknk（6）akkk；3；解：5.3已知數(shù)列ak的生成函數(shù)是A(x)23x9x2，求ak.13x5.15知數(shù)列ak的指數(shù)生成函數(shù)是Gx(x)x25ex，求ak。6.5平面上有n條直線，它們兩兩訂交且沿有三線交于一點(diǎn)，設(shè)這n條直線把平面分紅f(n)個(gè)地區(qū)，求f(n)的遞推關(guān)系并求解.解：設(shè)n-1條直線把平面分紅f(n-1)個(gè)地區(qū)，則第n條直線與前n-1條直線都有一個(gè)交點(diǎn)，即在第n條直線上有n

16、-1個(gè)交點(diǎn)，并將其分紅n段，這n段又把其所在的地區(qū)一分為二。6.6一個(gè)1n的方格圖形用紅、藍(lán)兩色涂色每個(gè)方格，假如每個(gè)方格只好涂一種顏色，且不一樣意兩個(gè)紅格相鄰，設(shè)f(n)有種涂色方案，求f(n)的遞推關(guān)系并求解.解：設(shè)f(n)為1n的方格圖形的涂色方案。當(dāng)n=1時(shí)，f(1)=2，即一個(gè)方格有紅、藍(lán)兩種涂色方案。當(dāng)n=2時(shí)，f(2)=3，即兩個(gè)方格有（紅、藍(lán)），（藍(lán)、紅）、（藍(lán)、藍(lán)）三種涂色方案。因?yàn)椴灰粯右鈨蓚€(gè)紅格相鄰，所以不存在（紅、紅）的狀況。當(dāng)n2時(shí)，假如第一個(gè)格子涂為藍(lán)色，則節(jié)余n-1個(gè)格子的涂色方案數(shù)為f(n-1)；假如第一個(gè)格子涂為紅色，因?yàn)椴灰粯右鈨蓚€(gè)紅格相鄰，所以第二個(gè)格子必

17、為藍(lán)色，則節(jié)余n-2個(gè)格子的涂色方案數(shù)為f(n-2)。于是，當(dāng)n2時(shí)涂色方案數(shù)為f(n)=f(n-1)+f(n-2)。先求解這個(gè)遞推關(guān)系的通解，它的特點(diǎn)方程為解這個(gè)方程，得所以，通解為代入初值來(lái)確立c1和c2，得求解這個(gè)方程組，得所以，原遞推關(guān)系的解為（n0,1,2,）.6.7核反響堆中有和兩種粒子，每秒鐘內(nèi)1個(gè)粒子可反響產(chǎn)生出3個(gè)粒子，而1個(gè)粒子又可反響產(chǎn)生出1個(gè)粒子和2個(gè)粒子.若在t=0s時(shí)刻反響堆中只有1個(gè)粒子，求t=100s時(shí)刻反響堆里將有多少個(gè)粒子和粒子.解：設(shè)t時(shí)刻反響堆中粒子數(shù)為f(t)，粒子數(shù)為g(t)在t-1時(shí)刻在t時(shí)刻6.8求以下n階隊(duì)列式的值dn解：當(dāng)n=1時(shí)，d122當(dāng)n=2時(shí)，d221132當(dāng)n2時(shí)，dn2dn-1dn-2先求解這個(gè)遞推關(guān)系的通解，它的特點(diǎn)方程為解這個(gè)方程，得所以，通解為代入初值來(lái)確立c1和c2，得求解這個(gè)方程組，得所以，原遞推關(guān)系的解為f(n)n1（n0,1,2,）.6.9設(shè)h(n)表示n+2條邊的凸多邊形為它的對(duì)角線區(qū)分所得的地區(qū)數(shù)，此中假定沒有二條對(duì)角線在凸多邊形內(nèi)有一公共點(diǎn)。定義h(0)=0，對(duì)n=l，2，證明證明：以下圖，在凸n+2邊形中，劃出以隨意兩相鄰邊為邊的三角形，比如ABC。則余下的是n+1的凸多邊形，它的對(duì)角線區(qū)分所得的地區(qū)數(shù)為h(n-1)。由A點(diǎn)引出的對(duì)角線共有n-1條，分ABC為下邊我們計(jì)算一下由