組合數(shù)學(xué)作業(yè)

1、11） 在邊長(zhǎng)為1的等邊三角形內(nèi)任意放10個(gè)點(diǎn)，證明一定存在 兩個(gè)點(diǎn)，其距離不大于1/3。證：如圖所示：在三角形的邊上加兩個(gè)點(diǎn)等分每條邊，把大三角形分別9個(gè)邊長(zhǎng)為1/3的小三角形。由鴿巣原理：10個(gè)點(diǎn)中一定存在兩個(gè)點(diǎn)落于同一個(gè)小三角形，其距離不大于1/3。2）在邊長(zhǎng)為1的三角形內(nèi)放個(gè)點(diǎn)，則把三角形分割成n-1個(gè)小三角形。由鴿巣原理可知：個(gè)點(diǎn)必有兩點(diǎn)落于同一個(gè)小三角形內(nèi)，則其距離不大于1/n.2證： m個(gè)數(shù)，i=1,2.m.設(shè) 0m-1當(dāng)=0時(shí)，存在一個(gè)整數(shù)可以被m整除。當(dāng)從1.m-1這m-1個(gè)中取值，那么m個(gè)中只有m-1種可能，則鴿巣原理可知：必存在j和k，使得,jk,即有3.證：有理數(shù)可由整

2、數(shù)和分?jǐn)?shù)組成。當(dāng)為整數(shù)時(shí)，存在以0為循環(huán)的循環(huán)小數(shù)。當(dāng)為分?jǐn)?shù)時(shí)，若分?jǐn)?shù)是有限的循環(huán)小數(shù)，則存在以0為循環(huán)的循環(huán)小數(shù)。若分?jǐn)?shù)是無限循環(huán)的循環(huán)小數(shù)，則肯定存在某一位后以某一位為循環(huán)的循環(huán)小數(shù)。4證：設(shè)全部由7組成的N+1個(gè)數(shù)，7，77，777，,7777。77（N+1個(gè)7）存在整數(shù)N，由7組成的數(shù)除以N，以代表N+1中的數(shù)。即=Nq+ 0 N-1則存在0.N-1這n個(gè)數(shù)，則鴿巣原理可知：必定存在兩個(gè)數(shù)使得 是N 的倍數(shù) 組合數(shù)學(xué)第2次作業(yè)25 證明在任意選取的n+1個(gè)正整數(shù)中存在著兩個(gè)正整數(shù)，其差能被n整除。解：設(shè)任意n+1正整數(shù)，任意取兩個(gè)整數(shù)的差為=,ij.差除以n的余數(shù)為。 0n-1 如果存

3、在i，使得=0.則可以被n整除，對(duì)所有i，i=1,2 。n都有0則這n個(gè)i中只能取1,2.。n-1。這n-1種情況。由鴿巢原理可知，必存在i和j使得，ij，則有= 可以被n整除。證明在任意選取的n+2個(gè)正整數(shù)中存在著兩個(gè)正整數(shù)，其差能被2n整除或者其和能被2n整除。解：設(shè)任意n+2正整數(shù)，任意取兩個(gè)整數(shù)的差為=,ij. 差除以2n的余數(shù)為。 02n-1 如果存在i，使得=0.則可以被n整除，對(duì)所有i，i=1,2 。2n都有0則這2n個(gè)i中只能取1,2.。n-1。這2n-1種情況。由鴿巢原理可知，必存在i和j使得，ij，則有= 可以被2n整除。2.6某學(xué)生有37天的時(shí)間準(zhǔn)備時(shí)間考試，根據(jù)她過去的

4、經(jīng)驗(yàn)至多需要復(fù)習(xí)60個(gè)小時(shí)，但每天至少要復(fù)習(xí)1小時(shí)。證明無論怎樣安排都存在連續(xù)的若干天，使得她在這些天里恰好復(fù)習(xí)了13小時(shí)。 設(shè)是從第1天到第i天復(fù)習(xí)的總小時(shí)，i=1,2，。37.至多復(fù)習(xí)60個(gè)小時(shí)。1。60。做序列： 這個(gè)序列也是嚴(yán)格單調(diào)上升的，且有+1360+13?？疾煜旅娴男蛄校?該序列有84個(gè)數(shù)，每個(gè)數(shù)都是小于等于73的正整數(shù)，由鴿巢原理可知，必存在i和j使得 (ij）.令n=i-j,該學(xué)生在第j+1,j+2,.j+n=i 的連續(xù)n 天中復(fù)習(xí)了13個(gè)小時(shí)。(P34)3.7把q個(gè)負(fù)號(hào)和p個(gè)正號(hào)排在一條直線上，使得沒有兩個(gè)負(fù)號(hào)相鄰，證明不同的排法有C（p+1，q）種。證：先把p個(gè)正號(hào)排在一

5、條直線上，那么就有p+1個(gè)間隔，那就可以把q個(gè)負(fù)號(hào)插進(jìn)這p+1個(gè)位置，則就知道其不同的排法有C（p+1，q）種。3.8（1）從整數(shù)1,2，、，100中選出兩個(gè)數(shù)，使得他們的差正好是7，有多少種不同的選法。解：從整數(shù)1,2，、，100中選出兩個(gè)數(shù)，使得他們的差正好是7的兩個(gè)數(shù)有1和8, 2和9, 3和10, 4和11，、93和100，則一共有93種選法。 （2）如果選出的兩個(gè)數(shù)之差小于等于7，又有多少種選法？解：如果選一個(gè)數(shù)為1的話，那另一個(gè)數(shù)就可以是2,3,4,5,6,7,8有7種如果選一個(gè)數(shù)為2的話，那另一個(gè)數(shù)就可以是3,4,5,6,7,8,9有7種、如果選一個(gè)數(shù)是93的話，有94,95,9

6、6,97,98,99,100，也是7種選94，那就有95,96,97,98,99,100 6種選95，那就有96,97,98,99,100 5種選96，那就有97,98,99,100 4種選97，那就有98,99,100 3種選98，那就有99,100 2種選99，那就有100 1種那把上面所有的選法加起來得：937+6+5+4+3+2+1=672則從整數(shù)1,2，、，100中選出的兩個(gè)數(shù)之差小于等于7有672種選法。3.20從整數(shù)1,2、，1000中選取三個(gè)數(shù)使得它們的和正好被4整除，問有多少種選法。解：將1,2、1000都除以4，A、余數(shù)為0的有4,8,12,16，、1000， 250個(gè)B、

7、余數(shù)為1的有1，5,9,13，、997， 250個(gè)C、余數(shù)為2的有2,6,10,14，、998， 250個(gè)D、余數(shù)為3的有3,7,11,15，、9999， 250個(gè)然后再?gòu)腁,B,C,D中選取三個(gè)數(shù)可被4整除：在A中取三個(gè)數(shù)，則有C（250，3）在A,B,D中各取一個(gè)數(shù)，則有【C（250,1）】3在A中取一個(gè)，在C中取兩個(gè)；在B中取兩個(gè)和在C中取一個(gè)；在C中取一個(gè)，再在D中取兩個(gè),則有3C(250，2)C(250，1)所以總選法是C（250,3）+【C（250,1）】3+3C（250,2）C（250,1）3.32設(shè)S=n1a1，n2a2，nkak，問S的大小不同的各種組合的總數(shù)是多少？解：當(dāng)K

8、=1時(shí)，S1=n1a1，S1的組合為，a1，2a1，n1a1，有n1+1個(gè). 當(dāng)k=2時(shí)，S2=n1a1，n2a2，顯然S1的組合都是S2的組合，如果對(duì)S1的組合加入a2，就可以構(gòu)成S2的含a2的組合。S1的組合有n1+1個(gè)，對(duì)其中的每一個(gè)組合加入a2的方法有n2種，由乘法法則，S2中含a2的組合有（n1+1）n2個(gè)。所以S2的組合有（n1+1）+（n1+1）n2=（n1+1）（n2+1）個(gè)。 由歸納法不難證明S=n1a1，n2a2，nkak的各種組合的總數(shù)是 （n1+1）（n2+1）（nk+1）.P624.3解：（1）、 要取的系數(shù)，則k=13. 的系數(shù)為： （2）要取的系數(shù)，且 則只能取k

9、=10,取的系數(shù)為：4.4 解：由二項(xiàng)式定理得： （1）、 （2）、對(duì)任意的實(shí)數(shù)r求和解：用任意的實(shí)數(shù)r求和 實(shí)數(shù)r的和=4.7方法一： = = 又 =0方法二：= = 由兩邊同時(shí)微分得：令x=1時(shí)：左邊=0，右邊=而又=0 可證！4.16由二項(xiàng)式定理得： =兩邊同時(shí)積分得：= 令x=-1時(shí)：左邊= ， 右邊= = 可證！4.22 用多項(xiàng)式定理展開 解：= ， 的取法有：004的3種，112的3種，220的3種和130的6種。當(dāng)為004時(shí)：有=當(dāng)為112時(shí)：有 +=經(jīng)計(jì)算得： =+6+45.1在1和10000之間不能被4，5，6整除的數(shù)有多少個(gè)？解：令P1, P2, P3, 分別表示一個(gè)整數(shù)能

10、被4,5,6整除的性質(zhì). 設(shè) S=x|x是整數(shù)1x10000 Ai =x|xSx具有性質(zhì)Pi , i=1,2,3. 則：|A1|=【10000 / 4】=2500 |A2|=【10000 / 5】=2000 |A3|=【10000 / 6】=1666 |A1A2|=【10000 / （4，5）】=【10000 / 20】=500 |A1A3|=【10000 / （4，6）】=【10000 / 12】=833 |A2A3|=【10000 / （5，6）】=【10000 / 30】=333 |A1A2A3|=【10000 / （4，5，6）】=【10000 / 60】=166 由定理得： |123

11、| =10000 -（2500+2000+1666）+（500+833+333）-166 =53345.4確定S= a, 3 b, 5 c, 7 d 的10 - 組合數(shù).解：令T= a, b, c, d ，T的所有10- 組合構(gòu)成集合W.則由定理3.7得 |W|=286 任取T的一個(gè)10- 組合， 如果其中b多于3個(gè)則稱它具有性質(zhì)P1， 如果其中c多于5個(gè)則稱它具有性質(zhì)P2， 如果其中d多于7個(gè)則稱它具有性質(zhì)P3.不難看出所求的10- 組合數(shù)就是W中不具性質(zhì)P1，P2，P3的元素個(gè)數(shù).令A(yù)i=x|xWx具有性質(zhì)Pi ，i=1,2,3. |A1|=84 |A2|=35 |A3|=10 |A1A2

12、|=1 |A1A3|=0 |A2A3|=0 |AbAcAd|=0 由定理得： |123|=286-(84+35+10)=158 5.5 1)確定方程X1+X2+X3=14的不超過8的非負(fù)整數(shù)解的個(gè)數(shù). 解： 方程不超過8的非負(fù)整數(shù)解，則0x18, 0x28, 0x38. |S|=120 |A1|=21 |A2|=21 |A3|=21 |A1A2|=0 |A1A3|=0 |A2A3|=0 |A1A2A3|=0 由定理得： |123|=120 -21*3=572) 確定方程X1+X2+X3=14的不超過8的正整數(shù)解的個(gè)數(shù). 解： 方程不超過8的正整數(shù)解，則1x18, 1x28, 1x38. 相當(dāng)于

13、取值為0x17, 0x27, 0x37， x1+x2+x3=11 |S|=78 |A1|=10 |A2|=10 |A3|=10 |A1A2|=0 |A1A3|=0 |A2A3|=0 |A1A2A3|=0 由定理得： |bcd|=78-10*3=48P865.7求集合1,2，n的排列數(shù)，使得在排列中正好有k個(gè)整數(shù)在它們的自然位置上（所謂自然位置就是整數(shù)i排在第i位上）解：由題意可知，從n個(gè)數(shù)中取n-k個(gè)數(shù)后，再將n-k個(gè)數(shù)錯(cuò)位排列，則所求的排列數(shù)是：=5.8定義=1，用組合分析的方法證明n！=證：n！是對(duì)1,2.，n進(jìn)行全排列，是對(duì)1,2.n進(jìn)行分類：當(dāng)1,2,n中有0個(gè)數(shù)錯(cuò)位排列，則排法為當(dāng)1

14、,2,n中有1個(gè)數(shù)錯(cuò)位排列，則排法為當(dāng)1,2,n中有2個(gè)數(shù)錯(cuò)位排列，則排法為.當(dāng)1,2,n中有n個(gè)數(shù)錯(cuò)位排列，則排法為由于加法法則1,2n的排法總數(shù)為所以：5.9證明為偶數(shù)當(dāng)且僅當(dāng)n為奇數(shù).證：（反證法）“”設(shè)n為偶數(shù)，則n為偶數(shù)，為奇數(shù)，即為奇數(shù)，與題設(shè)為偶數(shù)矛盾，所以假設(shè)不成立。即n為奇數(shù)?！啊币阎猲為奇數(shù)，則n-1是偶數(shù)，為偶數(shù)。綜合上所述，為偶數(shù)當(dāng)且僅當(dāng)n為奇數(shù)可證。5.1在1和10000之間不能被4，5，6整除的數(shù)有多少個(gè)？解：令P1, P2, P3, 分別表示一個(gè)整數(shù)能被4,5,6整除的性質(zhì). 設(shè) S=x|x是整數(shù)1x10000 Ai =x|xSx具有性質(zhì)Pi , i=1,2,3.

15、 則：|A1|=【10000 / 4】=2500 |A2|=【10000 / 5】=2000 |A3|=【10000 / 6】=1666 |A1A2|=【10000 / （4，5）】=【10000 / 20】=500 |A1A3|=【10000 / （4，6）】=【10000 / 12】=833 |A2A3|=【10000 / （5，6）】=【10000 / 30】=333 |A1A2A3|=【10000 / （4，5，6）】=【10000 / 60】=166 由定理得： |123| =10000 -（2500+2000+1666）+（500+833+333）-166 =53346.1 計(jì)算

16、f (0)f(1)f(2) f(n)當(dāng)n為偶數(shù)時(shí)：f (0)f(1)f(2) f(n)= f (0)f(0)+f(2) f(n2) 由性質(zhì)2得：=1+ f(n2+1)= f(n1)+1當(dāng)n為奇數(shù)時(shí)：f (0)f(1)f(2) f(n)= f (0)f(1)f(2) f(n-1)f(n)+ f(n+1)f(n+1)= f (0)f(0)+f(2) f(n1)f(n+1) 由性質(zhì)2得：=1+ f(n1+1)f(n+1)=1+ f(n)f(n+1)= f(n1)+16.2 證明下面的等式f(2n)+ = = = =由性質(zhì)6得：= f(2n)方法二：直接由性質(zhì)6得：令2n=(n-1)+(n+1) f(n-1)+(n+1)=f(n+1-1)f(n-1+1)+f(n+1-2)f(n-1)2 =f(2n) (由第一小題已證出) f(3n+2)=f(2n+1)f(n+