隨堂練習 : 一個房間的地面是由個正方形所組成, 如下圖今想要用長方形磁磚鋪滿地面, 已知每一塊長方形磁磚可以覆蓋兩個相鄰的正方形, 即或試問用 6 塊磁磚鋪滿房間地面的方法共有多少個? 例 : 周長為 0 而三邊長度均為整數的三角形共有多少個? 解 : 設三角形邊長為 abc 且滿足 a

Size: px

Start display at page:

Download "隨堂練習 : 一個房間的地面是由個正方形所組成, 如下圖今想要用長方形磁磚鋪滿地面, 已知每一塊長方形磁磚可以覆蓋兩個相鄰的正方形, 即或試問用 6 塊磁磚鋪滿房間地面的方法共有多少個? 例 : 周長為 0 而三邊長度均為整數的三角形共有多少個? 解 : 設三角形邊長為 abc 且滿足 a"

白匆皇甫
9 years ago
Views:

1 基本計數原理在殷商時代, 透過爻 ( 因ㄧㄠ ˊ, 即卦上的橫線 ) 與卦的排列和變化來解釋各種自然現象, 經後人整理成為中國最古老的典籍之一 - 周易若每次取個爻, 有 4種不同的排列, 稱為四象 ; 若每次取個爻可得 8種相異的排列, 稱為八卦, 在周易裡還把每次取個卦形成的 8 64 種排列稱為八卦, 宋代科學家沈括也討論過圍棋棋局總數的問題 : 因棋盤上共有格點, 因此共有種棋局而西元前 600 年左右, 印度人也討論過這樣的問題 : 酸甜苦辣鹹澀 6 種味道可調配出多少種不同的味道? 答案是 : 單味 6 種雙味 5 種三味 0 種四味 5 種五味 6 種六味種, 共 6 種味道計數原理常見的有窮舉法樹狀圖一一對應原理加法原理乘法原理排容原理以及遞迴關係式一窮舉法 : 在有限的集合裡, 一一列舉出所有可能的解 ( 即可行解 ), 並從中尋找最適合的解, 也是解決計數問題的一種方法例 : 在邊長的正三角形 ABC 中, 在每一邊的兩個三等分點中, 各選取一點而連成一個三角形, 問共可連成幾個三角形? 這些三角形中共有幾個銳三角形? 幾個直角三角形? 幾個鈍三角形? 解 : 設 AB BC CA 邊上的等分點依次為 D E F G H I 如下圖 : 所連成的三角形有 DFH DFI DGH DGI EFH EFI EGH EGI 共 8 個三角形而其中 DFH 及 EGI 是邊長的正三角形, 其餘 6 個是的直角三角形

2 隨堂練習 : 一個房間的地面是由個正方形所組成, 如下圖今想要用長方形磁磚鋪滿地面, 已知每一塊長方形磁磚可以覆蓋兩個相鄰的正方形, 即或試問用 6 塊磁磚鋪滿房間地面的方法共有多少個? 例 : 周長為 0 而三邊長度均為整數的三角形共有多少個? 解 : 設三角形邊長為 abc 且滿足 ab c 0 ab c 因三角形兩短邊長的合大於最長邊的長即 b c a, 所以 0 a b c a a a 0 a b c a a a a 即 0 a 5 列舉所有有的理解如下 : a

3 b c 隨堂練習 : 三邊長均為正整數且最長的邊長為的正三角形共有多少個? 二樹狀圖 : 例的 8 個三角形也可用樹狀圖表示樹狀圖在不具規則的問題中比較能表現出它的效力例有一長方體如右圖, 由頂點 A 沿著稜線走到對角線 ( AG ) 的另一頂點 G, 每一個頂點最多只能經過一次, 問共有多少種走法? 解 : 由 A 經 B 到 G 的所有走法, 以樹狀圖表示如下 : 同理由 A 經 C ( 或 D ) 到 G 也有相同的走法, 因此共有 6 8 種走法隨堂練習 : 有一四面體 ABCD 如右圖由頂點 A 沿著稜線走到頂點 B 每個頂點最多只能經過一次, 問共有多少種走法三一一對應原理設 A B 是兩個集合, 且函數 f 從 A 映到 B, 計為 f : A B, 若對於集合 A 中的任兩個元素 ( 當然不相等 ), 恆有 f f 的一對函數如 f x x, gx x 中的任一元素 b, 在 A 中有一元素 a, 使得, 則稱 f 是從 A 映到 B 都是從 R 應到 R 的一對一函數若對於 B f a 成函數 ( 或稱蓋射 ), 如 h x x 是從 R 映到 0 0, b, 則稱 f 是從 A 映到 B 的映 x x 的映成函數, 但不是從 R 映到 R 的映成函數, 而 x log x 是從 0 0, x x 映到?? 的一對一

4 x log 且映成的函數一對一且映成的函數會有 R 函數如是 gx x, 又如 px x 的反函數就是 g x x 例 4: 已知是自然對數的底數, 它是個無理數, 且 , 設 f x x x x x 試證 : f 是從 R 映到 (,) X X 數 x 的反映函數就的一對一且映成的函數, 並求其反函解 : f x 設, R x x x x, 將 f 且 f f x x 的分子分母同乘以, 得 f x x x, ( )( ) ( )( ) ( ) ( ) 因 f f 同義於 f = f = 所以 f 數再設 y f x, 即 x x y y x y y y, x 因 0, 所以 y 0 ( y )( y ) 0 y, y x 是一個一對一函 y 的範圍即為函數值 f x 的範圍, 將它寫成集合就成為值域 y y =(-,) y 底下, 證明 f : R (,) 是個映成函數設 y (,), 可找到 x log ( ) 使 y y y log ( ) x y y y 得 f x y x y log ( ) y y y

5 而反函數 y x f x log ( ) log ( ), x(,) y x 函數 f x x x 的略圖描繪如下, 其中 y, y 是兩條漸近線由例 4, 可知 f : A B 是個映成函數的充要條件是 : 值域等於對應域, 即 f A B 隨堂練習 : 設 f x x x, 試證 f 是從 R 映到 R 的一對一函數, 並作函數 y f x 的圖形隨堂練習中的 f x x x, 其實也是從 R 映到 R 的映成函數, 介紹卡丹 (Cardao) 公式的解法如下設 y x x, 令 x u v, 兩邊立方得 x u v uv( u v) x uvx u v 0 因此 uv u, v 為 t ( ) u v y u v y uv 7 4 y y yt 0 的兩根, 而 7 y y t y y y y 因 x x y 0, 洽有一實根, 所以 x u v 檢驗一下 y y y y y y y y x x ( )+( ) ( )( ) x x

6 4 y y y x x 4 7 y 設 y R 存在 y y y y x 使得 f x y, f 確是從 R 映到 R 的映成函數且 f x x x x ( x) 設 A B 是兩個有線集合, 且函數 f : A B ( 一 ) 若 f 是一個一對一函數, 設 A a a a, 因,,... f a f a f a 是集 ( ),..., 合 B 中兩兩相異的元素, 因此 A B, 其中 A 表示集合 A 的元素個數 ( 二 ) 若 f 是個一對一且應成的函數, 因 B f A f a a a B A 例 5: 設集合 S a a a,,..., 因此 ( ),,..., 試求 S 的所有子集合的個數解 : 設 S 的所有子集合所成集合為 S X X S, i,= 而 T x, x..., x x 或 0, i,,..., 函數 f : s T 當 A S 時, 令 f A x x x ( ),,..., 當 xi () 設 AB, S 且 A B A時, x, 否則 x 0, 其中 i,,..., 存在某個元素 ai i i S 但不同時屬於 A 與 B, 此 f( A ) 與 f( B ) 的第 i 個分量必不相等, 即 f ( A) f ( B), 故 f 是個一對一函數 x x x T, 當 xi 時, a i S, 當 xi 0 () 設,,..., 因此存在 A S, 使得 f ( A) x, x,..., x 時, a i S, i,,...,, 故 f 為映成函數因 ( x, x,..., x ) 中每一個 x i 不是就是 0, 所以集合 T 共有個元素又 f : s T 是個一對一

7 s 且映成的函數, 因此 T 隨堂練習 : 東山里舉辦桌球單打比賽, 每場比賽一定要分出勝負, 採單敗淘汰制 ( 即輸一場就淘汰 ), 現有 0 人參賽, 問總共要比賽幾場才能產生冠軍? 四加法原理 ( 分類 ) 若完成某件事情有類方法, 而每一類方法中分別有 m, m,..., m 種方法, 不論採用這些方法中的任何一種, 均能單獨完成這件事情, 那麼要完成這件事情共有 m m... m 種方法, 若使用集合的語法, 加法原理也可敘述如下設 A 是一個有限集合, 而 A, A,... A K 是 A 的一些兩兩互斥 ( 及 Ai Aj, 其中 i j, 且 i, j,,... ) 的子集合, 且 A A A... A, 那麼就有 A A A... A, 我們稱 A, A,... A K 為集合 A 的一個分割運用加法原理來計數的關鍵是如何適當的找到集合 A 的一個分割 A, A,... A K 例題 6: 設向量 a 的始點與終點均為正方體的頂點, 且 a 0, 問共有多少個相異的 a 向量? 解 : 正方體 ABCDEFGH 如右圖設正方體的一稜長為, 那麼向量 a 的長度有三類 : (): a, 有 AB AD AE 及相反向量, 共 6 個 (): a, 有 AC BD AF BE AH ED 及相反向量, 共個 (): a, 有 AG EC BH DF 及相反向量, 共 8 個這三類兩兩互斥, 由加法原理, 向量 a 共有 6++8=6( 個 ) 隨堂練習下圖是正五邊形與共對角線所構成的圖形, 問所有的三角形共有多少

8 個? 五乘法原理 ( 分段 ) 若完成某件事情必須經過個步驟, 而每一步驟分有 m, m,... m 種方法, 那麼完成這件事情共有 m m... m 種方法例 7: 關於正整數 540 正因數的問題 : () 540 有多少個正因數? () 540 正因數的總合為何? () 540 正因數的成績為合? 解 : 先做 540 的標準分解式 a b c () 540 的正因數是 5 的形式, 其中 a 0,or, b 0,, or, c 0or, 因此 abc,, 依次有,4, 種選擇, 即將求 540 正因數的個數這件事分成個步驟, 每一步驟分別有,4, 種方法, 所以完成這件事的方法為 4 4 ( 種 ), 即 540 的正因數有 4 個 () 將 () 中的正因數相加 : () 將 () 中的改為, 可得

9 a b c 隨堂練習 : 設正整數 p q r, 其中 pqr,, 為正質數, 而 abc,, 都是正整數, 試求解下列問題 () 有多少個正因數? () 的正因數總和等於多少? () 的正因數乘積等於多少? 關於函數惡樹的問題也可運用乘法原理來處理例 8 設 AB, 為兩個有限集合, 且 A, B, 函數 f : A B () 函數 f 共有多少個? () 若, 且 f 是一對一函數, 問函數 f 共有多少個? () 若, 且 f 是一對一又映成的函數, 問函數 f 共有多少個? 解 : () 集合 A 中的任一元素 a,( i,,..., ) 都可以唯一對應到 B 中的任一元素, 因 B i 有個元素, 由乘法原理, 共可定義... 個函數 () 集合 B 的個元素中洽有一個是 a 的函數值, 集合 B 中剩下的個元素洽有一個是 a 的函數值, 依此類推, 集合 B 中剩下的個元素中洽有一個是 a 的函數值, 由乘法原理可定義... 個一對一函數, 將此數計為 P, 稱為中取的排列數 () 由 () 得一對一且映成的函數共有 P =...! ( 個 ), 又

10 P!!! 當時, P 又 P!, 所以規定 0! 0! 運用函數的特性 ( 定義域 A 中的任一元素唯一的對應 B 中的某一元素 ), 可以處理下列問題隨堂練習 : 將三本不同的書全部分給甲乙丙丁戊五人求下列個小題的分法 () 任意分 () 每人至少一本 () 甲至少一本一筆畫的問題, 也可以利用乘法原理處理例 9 誠慧社區巷道如下, 垃圾車從 A 進入, 由 B 離去, 須走過每一條巷道, 但走過的巷道不再走, 問共有多少種走法?( 上述走法的一筆畫 ) 解 : 圖 ( 一 ) 圖 ( 二 ) 圖 ( 三 )

11 () 關於圖 ( 一 ) 的解, 繪出精密圖如右 : 由 A 到 P 有條路徑, 如走甲路線到 Q, 又有條路徑, 如走乙路線到 P, 最後走丙路線到 Q, 然後離去, 由乘法原理, 共有! 種走法 () 關於圖 ( 二 ) 的解, 再利用 () 重複兩次, 可得 (!) 6 種走法 () 關於圖 ( 三 ) 的解, 分成先走上一圈, 再走下一圈及先走上半圈下半圈, 再走完兩類, 每一類都各有 (!) 種走法, 由加法原理共有 (!) 7種走法隨堂練習 : ( 一 ) 下列圖形, 由 A 走到 B, 一筆畫的走法有多少種? () () ( 二 ) 試作一個無法以一筆畫走完的圖形如六排容原理在加法原理中, 必須先找到集合 A 的一個分割 A, A,..., A K 才會有 A Ai 的漂亮結果, 假若找不到 A 的一個分割, 只好使用排容原理來計數排容原理就是計算 A A... A 的方法在及時, 都可以使用文氏圖, 得到 : i

12 A A A + A A A A A A A + A A A A A A A A A A A 但 4 時即, 文氏圖不容易處理, 使用及分配律 A B C ( A B) A C 可推出, 再使用數學歸納法可以推出的一般情形 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A 而的排容原理是 A A... A A A A A A A... A A... A 其中 i j i j i i j i j i i j i j Ai Aj 是指兩兩交集的個數和共有 C 個, 同理 Ai Aj A 是參參交集的個數和, 共有 C 個, 組合! 是中取 ( 只取不排 ) 的方法數, 即 C! P, 亦即 C C 54 C 0! 5 5 P!, 如!!( )! 例 0: 設 A B 均為有限集合, 且 A, B, 函數 f : A B, 若, 且函數 f 是映成函數, 問函數 f 共有多少個? 解 : 設 A a, a,..., a, B b, b,..., b C 令在集合 B 中, b 不是函數值的函數, 所成的集合為 B b 不是函數值的函數, 所成的集合為 B

13 b 不是函數值的函數, 所成的集合為 B 那麼由 A 映到 B 的映成個數為 B B... B C C C C C C 將五件不同的玩具分給三位小朋友, 每人至少一件的分法數即是 5 對的映成函數 ( 蓋射 ) 個數, 也就是 : C C 隨堂練習 : 從到 9876 的正整數中, 數字中有 0 的數 ( 即個位數字 0 十位數字 0 或百位數字 0) 共有多少個?,,...,, 函數 f : A A, 而且是個一對一函數, 若 a 的函數值設集合 A a a a 不是 a, 若 a 的函數值不是 a,, 若 a 的函數值不是 a, 則稱 f 是個錯列函數, 這種錯列函數共有多少個? 設 w 表示 A A的錯列函數個數, 顯然 w 0, w, w, 但 w 4 就不顯然了, 運用排容原理是求解的方法之一, 先求 w, w 4 就成為特例了在集合 A 中設 a a的函數所成的集合為 A, a a 的函數所成的集合為 A,, a a 的函數所成的集合為 A, 那麼

14 w! A A... A! C! C!... C! C0!!! C!... C C!... ( ) ( )!! ( )! ( )! w 9, w 44, w 65, w 854 計算一下若取 7, A A的一對一函數中, 任取一函數其為錯列的機率為 w , 當 7! 5040 很大時 w!, 若取.78, 0.68 十遞迴關係式有些計數問題可使用數列的遞迴關係式處理, 具有簡潔俐落的特性例 : 將元和元的兩種郵票貼成一排, 若郵資是元, 問共有多少種貼法? 解 : ( 一 ) 窮舉法 : 設元郵票元郵票分別貼 xy, 張, 共貼元, 則有 xy, 其中 xy, 為非負整數其解為 : x 9 6 y 0 4 共有 5 種情況, 如 x6, y ( 及元郵票 6 張, 元郵票張 ), 8! 8 8,,,,,,,, 排列法共有 C6 C 8種, 所以共有 6!! C0 C C C C ( 種貼法 ) ( 二 ) 遞迴關係式法 : 設使用元和元郵票貼成一排, 共貼成源的方法有 a 種, 顯然 a, a, a, 又貼成元 ( 4, N ) 的方法可分成互斥兩類

15 () 第一張貼元, 剩下 (-) 元, 其貼法有 a 種 () 第一張貼元, 剩下 (-) 元, 其貼法有 a 種由加法原理, 可得遞迴關係式 : a ( 4) a a, 由 a, a, a 迭代可得 a a a, a a a 4, a a a 6, a a a a a a, a a a 9, a a a 8, a a a a a a 60 9 所以郵資元的貼法共有 60 種當很大時, 迭代十分複雜, 但借助電腦耐煩耐操的特性, 可以很快速求得 a 的值隨堂練習 : 阿毅登樓每步可走階, 也可走階若樓梯共有階, 那麼他有多少種上樓的方法再回到錯列函數的問題, A a a a,,...,, w 表示 A A的錯列函數的個數, 已知 w 0, w, w, 接著尋求 < w > 的遞迴關係首先, a 的函數值不是 a 時共有 ( ) 種方法, 而 a, a,..., a 錯列的情況可分成互斥的兩類 : () a 的函數值是 ai ( i ), 但是 ai ( i ) 的函數值不是 a, 剩下來的 a, a,..., a 錯列的方法數為 w () a 的函數值是 ai ( i ), 但是 ai ( i ) 的函數值是 a, 剩下的 w a, a,..., ai, ai,..., a 錯列的方法數為由加法乘法原理得 w ( )( w w ), 又已知 w 0, w, w, 可得知

16 w 9, w 44, w 65, w 854, 的確快速俐落! 最後, 看一個運用遞迴關係式處理機率問題的例子例 ( 全盤獲勝問題 ) 甲持有 m 元, 乙持有元, 兩人擲一公正硬幣, 若出現正面, 乙給甲元, 若出現反面, 甲給乙元, 求甲將乙的元全部贏過來的機率解 : 設 P 為持有 K 元的一方全贏的機率, 則 P0 0, Pm 若持有 K 元的一方擲硬幣 () 獲正面得元, 共有 (K+) 元, 以後全贏的機率為 P () 獲反面輸元, 共有 (K-) 元, 以後全贏的機率為 P 所以, P P P 即 P P P P 所以,< P > 為一等差數列, 0,,... m P P ( m ) 公差, 且 P0 0 又 m 0 因此, 公差 m 所以, P 0 ( ) 公差 m m 故甲全贏的機率為 Pm m 隨堂練習 : 在例中, 將公正硬幣改為出現正面機率為 a(0 a, a ) 的不公正硬幣, 求甲全贏的機率習題 :. 將正三角形 ABC 的各邊六等分, 過各分點在 ABC 內作各邊的平行線如下圖 () 試問共有多少個三角形? () 試問共有多少個平行四邊形?

17 .NBA 總冠軍是由東西區的冠軍隊採七戰四勝制比賽後的獲勝隊獲得的若現在已賽畢三場, 湖人隊以 : 領先, 試問往後有多少種結果來決定總冠軍?. 某鐵路沿線設有 0 個站, 試問鐵路局需準備幾種車票? 這票上的票款有多少種? 4. 試使用例 5, 求本章引起動機中印度 6 種味道 ( 酸甜苦辣鹹澀 ) 共可調配出多少種不同的味道? 5. 試使用數學歸納法證明排容原理 6.( 尤拉中函數 ) 設函數中 ( m ) 表示不大於正整數 m 且與 m 互質的正整數個數, 如 ( i), (), (), (4), (5) 4 () 設 p 為正質數, 為正整數, 求 ( P ) () 設 m ( P P... P ) 其中 P, P... P 為正質數,,,... 為正整數, 試證 : ( m) m( )( )...( ) p p p 7. 從到 000 的正整數中 () 不含有 7 的數字共有多少個? () 不能被 5,6,8 任一數整除的數有多少個? 8. 有紅黃藍白四種色球各 0 個, 現在從中取 5 個排成一列, 試問同色球不相鄰的排法有多少種? 9. 在下圖中, 由 A 到 B 一筆畫的走法有多少種?

18 0. 考慮正整數 m 寫成個正整數和的寫法, 其中 m= 如 5=++=++=++=++=++=++, 將 5 寫成個正整數和只有 6 種寫法, 在和式中, 項的位置次序不同, 就視為不同的寫法試問共有多少種不同的寫法? 參考答案 : ( 一 ) 隨堂練習 :. 種.6 個.5 種 5.9 場 6.5 個 7.()a b c () a b c p q r p q r () ( ) a b c 8.() 5 5 種 () P 5 60種 () 5 4 6種 9.( 一 )()! 5! 70 種 ()! 5! 60 種 ( 二 ) 如圖個. 種 a a a P P P P, P a a a. m m m ( 二 ) 習題.()78 個 ()0 個, 將平行四邊形的邊分成部平行 AB BC 與 CA 三類.0 種.()90 種 ()45 種票款種 6.() P ( P )

19 () 考慮排容原理 7.()79 個 8. ()600 個種 9. 0.!! 864 種 C m ( m )! ( )!( m )! 參考資料 : ( 一 ) 高中數學實驗教材第五冊 ( 二 ) 高中數學第四冊南一書局 ( 三 ) 高中數學第四冊教師手冊龍騰文化 ( 四 ) 路線的探針 - 賴敦生 ( 五 ) 高中數學競賽教程九章出版社

4

練習 9A ( 9. 特殊角的三角比 T ( 在本練習中, 不得使用計算機如有需要, 答案以根式或分數表示. 試完成下表三角比 θ 0 4 60 sin θ cos θ tan θ 求下列各數式的值 (. cos 60. sin 4 4. tan 4. cos0 4 tan 0 7. sin 4 cos 4 8. cos 60 tan 4 9. tan 60sin 0 0. sin 60 cos