第一章排列與組合 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)