第一章排列與組合 1.(a)應用關倸式C(n,r)-C(n-1,r)+C(n-1,r-1)薄明 等式C(n+1,m)=C(",m)+C(n一1,m-1)+C(n-2, m-2)+……+C(n-m,0),其中m≤n (b)以粗合式討論證明此等式。 【證明】 a)C(n+1,m)=C(n,m)+C(n,m-1) C(n,m-1)=C(n-1,m-1)+C(n-1,m-2) C(n-1,m-2)=C(n-2,m-2)+C(n-2,m-3) C(n-m+2,1)=C(n-m+1,1)+C(n-m+1,0) +)C(m-m+1,0)=C(n-m,0) C(n+1,m)=C(,m)+C(n-1,m-1)+C(n-2, m-2)+……+C(n-m,0) ()假設(磐+1)個物體中有m個物體被標號鳥S;S2,S,,… 則自(n+1)個物體中取出加個的方式有以下這麽多棰 (不包含S)+(包含S1但不包含S2)+(包含S,,S2; 但不包含S)+…+(包含S1,Sn,……S,;但不包含S,+
2粗合數擊問题詳解 )+…+(包舍S1,S2,S 意即 C(丌+1,m)=C(n,m)+C(r-1,m-1) C(n-2,m-2) C 2.(a)證明等式 I×1!+2×2!+3×3!+…+"×n!=(n+1)!-1立 b)鼠討論此等式的粗合式意義。 (c)證明對於任意整數m均可唯一地以下列形式(階乘表示法)表 示 m=a1×I!+axX2!+a3×3!+……+atxi!+ 其中0≤a;≤i,=I,2,3 【詮明】 a)(n+1)!=×n!+n! r-1)×(#-1)!+(n-1)! (n-1)!=(n-2)X(n-2)!+(n-2)! +) 2! ×】!+1! n+1)!=m×n!+(n-1)×〔n-1)!+……+2×2! 1x1!+1 故(n+1)!-1=1×1!+2×2!+3×3!+……+n×n! (b)將(n+1)個不同物體S1,S2,……,Sn+放入(n+1)個 不同格子C1,C2,……,C-+1闪的方式有以下道麼多種 (S1不在C1内)+(S1在C1內;但S2不在C2内)
第一章排列粗合 (S,S2分别在C1,C2内;但Ss不在Cs内)+…… (S, S S,分别在C3,C C内,但S;+1不 在C+1內)+……+(S1,S2,……,S。,S+1,分别在C1, C2,………,C,,C+1内) 意即 (n+1)!二#Xn!+(n-1)×(n一1)!+………+3×3! +2×2!+1×1!+1 故1×】!+2×2!+3×3! f n x (n+1)!-1 (c任意整數n均可表示成以下的形式 K1·2+ K1=K2·3+a 0≤a4≤ Kz=R3·4 3 由於K1,Kz,K。,……爲嚴格遞减序列,因此一定會有一個 K,=0,則燥代秸果可得 1!+a2×2 3! 十a×1 接著,證明此表示法的唯一性。假設整數n有兩種不同表示法 n=a:×1!+a2×2!+as×3!+…a:×i!+…以及 ×1!+a2×2 3! ×i 則0=(a1-a}’)×1!+(a2-a2)×2!+( )×3!+ +(;- 其中-1<( 應用(a所得之秸果可推得
粗合學雨題詳解 故表尔法唯 3.吲地P(n,n)-P(n,n-1)而P(n,n)+P(n,n 试用租合式討論說明以上.二個關係式。 【解】: 涸下问物中取出一個作上特别記號,則有尸(n,n 式將猁餘的〔n-1)個物體放及n偃不网的子。在钶種卢 此特昶物體已無選擇而必須放人唯一的笮格子内.所以 )=P( 若現在考將(n-2)個不间物體放入n惘八同格子的方式玎 P(η,n-2)種,而剩餘2個物體擺入2格子的大式有唾 所以 )-2×(n,n-2)+P( 4.試用租合式討論證明 C(n,0)+C(n,1)+C(n,2 C( 【證明】 自n個不间物體中取出幾個(也叮能是0個或n個)的方:支 有∑C(n,i)種。 相冏地,以乘法原理觀察的話,每個物饅均有取與不取
第一章排列與粗合5 擇,n個物體的取法方式即為2·。故 ∑C(n,i)=2 5.(a)試證n·C〔n-1,〃)=(r+1)·C(n,y+1)成立。 這等式代表什麼租台意義呢? (b)試證等式 C(n,1)+2×C(n,2)+3×C(n,3)+……… n×C(n,n)=n×2 【證明】: (a)n·C(n-1,r) !((n-1)-y)! (r+1) (r+1)!(磐-(r+1))! (r+1)·C(η,r+1) 假設有n個不同物體,考以下二種選取過程 ①選出二堆,其中一堆僅包含一物體,另一堆包含r物髓,則 先選一個,再選出r個,其選取方式有 C(n-1,r)種 自n物艭中選取(r+1)個,再由(y+1)物體中選出-個 ,其方式有 C( 1)·(r+1)種 事寞上,①丶二過科瞄速的是一件事所以 n·C(n-1,r)=C(n,r+1)·(r+1)
6粗合数學同題詳解 (b)∑r·C(n,r)=∑(r+1).C(n,r+1) rE O ∑n·C(n n∑C(n-1,r) =n·21(得自題4) 6.耠定一個n個,試證在 才、n-1n+1 若n是奇數 R 若磐是偶數 時,C(n,K)有極大值。 【證明】 F(K)= C(n, k+]) n-K C(#,K)K+1 因鳥R(K)震K的單調遞减函數,其中0≤K≤n1,且 R(0)=n,R(n-1)=-,所以 當r是奇黧,R 2 n-1 ∴.R K 2 時C()有砸大恤 當n是偶數,R 21)=”#2且R()n2 K=亏時,C(n,K)有極大值
7.(a)利用組合式尉論證明(2n)!及「3/ 章排列虫租合了 均是整數 (n2)! (b)試證 (n!)+是整數 【證明】: (a)有2n個物體包含n類,每類2個,則 (2n)! 2·即表示此2n個 物體可能的不同排列的個數。 (3n)! 2*·3 的討論力式同上 (b)n個物慢包含n類,每類n個,則這些物體的不同排列方 式有 種 (n!) 接蓍對這些排列方式加以分類,方式如下:若二種排列方式僅 是物體命名上的不同而不同即急一類。 =2為例,1221及2112的排列方式屬於同一類,如此一來 ,每類之内有n!個排列,即共有 n!)*+類,這必定是一個整數。 8.自整數1,2,3,4,………,1000選出三個整數,則使選出整數 的和可被3整除的選法有幾種。 【解】 如同例1-12,可得 2×C(333,3)+C〔334,3)+334(333)2
8粗合數學問題詳解 9.a)在2n個物體中有n個是相同的,求自此2n個物體中選取n個 的方式有種。 (b)在(3n+1)倡物體中有n個是相同的,求自此(3n+1) 物體中選取n個的方式有幾種。 【解】 (a)若選出的物懵中有k個不相同的,則其餘的(n-k)個是相爵 的,所以糖共的理取方式有 ∑(k) =2·種 b)同上的討論 2n+1122/2n+11 ∑ 22m+1=2 10.自n個整數中谬取二粗整數,分别包含k1及k2個整數,其中1 及k2固定且k1十k2<丌,則有幾種選取方式叮使得第一租内的 最小整數比第二組內的最大整數還大。 【解】 任意自n個整數中選取(k1+k2)個整數後,將它們分成台於活 目要求的方式僅有一種,所以共有 方式 1!.假設在凸n邊形中,任意三倏對角粽不在內部共點。試求由n每 形的逊展對角成的三角形有幾個。 【解】 依據禱成三角形的對角線交點及n蠱形頂點的偶敷對:三趙开
第一章排列典合9 分類。 ⑩3個頂點,沒有對角粽交點 任3個頂點可泱定一三角形 (3)個此類三角形 ⑧2個頂點,1個對角線交點 任4個頂點泱定4個三角形 4(4個此類三角形 ③1個頂點,2個對角線交點 任5個頂點可決定5個三角形 5(5)個此類三角形 ④沒有頂點,3個對角線交點 由於沒有3條對角褓共點,所以6個頂 個頂點(3惭對角線)泱定一三角形 有(6)個此類三角形 由①~④可知共有 3)4n (3)+4(4)+5(5)+(6)個三角形
10粗合數粤問题詳解 12.考慮一個由長度焉n的字(word)所成的集合,而每催宇都是由 字母{0,1,2}組成。 a)武證:0出現偶数的字共有 b)證明等式 2 其中若n為倜數,則q=丌;若〃恁奇數,則q=n-1。 【證明】: (a)包含一個0以上或一個1以上的字共有3·-1個(即不包括 222…2)由例19可知這些字的一牛篇包含著偶數個0,再算 人包含客個0而不被算入的222……22 3"+1 ∴包含偶數個0的字有 1 個 (b)包含K個0的字有 2*個 K 将自0到的偶數K對應的(K)2加起來即a)之精果,故 3+1 K K是偶數 13.藉由一通訊管線輸逸含有m個字母的字,於下列冬絛件下,求n 個字母的字能傳多小不同訊息( m essage)? a)字母在同一訊息中可重複出現