不可重複之排列 - Non-repeatable straight-line permutations
The number of permutations of n distinct objects taken m at a time is n n! P = nPm = __________ = n * (n - 1) * (n - 2) * ... * (n - m + 1) m (n - m)! for m = 0, 1, 2, ..., n.
Example: A,B,C 任選兩個不重複之排列數
Solution:
A: AB AC B: BA BC C: CA CB
3! / (3 - 2)! = (3 * 2 * 1) / 1 = 6
Example: 4張紙牌 A,B,C,D 任意排列數
Solution:
答案: 4 * 3 * 2 * 1 = 4! = 24
Example: 你有4隻馴鹿, 名字分別是 Lancer, Cooper, Phoenix, 和 Ocean, 你需要馴鹿拉雪橇3次. 每一隻馴鹿只能拉一次雪橇 (也就是每次拉雪橇的馴鹿不可重複) . 有多少種安排馴鹿拉雪橇的方法?
Solution:
4 P = 24 3
The number of permutations of n disctict obectes taken all together is n P = n! n
Example: In how many ways can eight teaching assistants be assigned to eight sections of a course in algebra?
Solution:
8 P = 8! = 40320 ways 8
The number of permutations of n objects of which N1 are of one kind, N2 are
of a second kind, ... Nk are of a k-th kind, and N1 + N2 + ... + Nk = N, is
N!
_______________________
N1! * N2! * ... * Nk!
Example: In how many ways can two paintings by Monet, 3 paintings by Renoir, and two paintings by Degas be hung side by side on a museum wall, if we do not distinguish between the paintings by the same artists?
Solution:
Subsitiuting N = 7, N1 = 2, N2 = 3, and N3 = 2 into formula described above,
we get
7!
______________ = 210 ways
2! * 3! * 2!
可重複之排列 - Repeatable straight-line permutations
從 n 個相異物取出可重複的 m 個之排列數 nm
Example: 3張紙牌 A,B,C 任抽一張, 抽完放回, 連抽兩次之排列數.
Solution:
32 = 9
環形排列 - Circular permutations
n 個相異物之環形排列數 n! ____ = (n - 1)! n
The number of permutations of n distinct objects arranged in a circle is (n - 1)!
A,B,C 的直線排列有下列 6種:
ABC ...... ① ACB ...... ② BAC ...... ③ BCA ...... ④ CAB ...... ⑤ CBA ...... ⑥
考慮環狀排列 ABC, BCA, CAB 是同一環狀排列; ACB, BAC, CBA 也是同一環狀排列 . 因此, 如下圖 A,B,C 之環狀排列只有 3! / 3 = 2 種, 即 ABC 以及 ACB .
從 n 個相異物取出 m 個之環形排列數
nPm ______ m
Example: 五對夫婦圍圓桌而坐, 試問男女相間坐的方法數為何?
Solution:
先直線排列: 5! * 5! * 2
故環狀排列數為 5! * 5! * 2 _____________ = 2880 10
Example: 有8個不同顏色的珠子, 取6個串成一項鍊, 試問其方法數有多少種？
Solution:
8個珠子選 6個 8 C = 28 6
6 個環狀排列 6! / 6 = 5! = 120
6 個環狀排列, 珠子項鍊不分正反 120 / 2 = 60
故共 28 * 60 = 1680 種
從 n 個相異物中不重複地取出 m 個之組合數 - The number of non-repeatable combinations of m from n dissimilar objects
The number of combinations of n distinct objects taken m at a time is n n nPm n! C = nCm = ( ) = ____ = _______________ m m m! m! * (n - m)! for m = 0, 1, 2, ... , n.
Example: In how many ways can a person choose three books from a list of eight best-sellers?
Solution:
8 C = 56 3
Example: In how many different ways can a committee of four be selected from among the 64 staff members of a hospital?
Solution:
64 C = 635376 4
從 n 類相異物中任意取出 m 個可重複之組合數 - The number of non-repeatable combinations of m from n dissimilar objects
n n+m-1 (n + m - 1)! H = C = _______________ m m m! * (n - 1)!
Example: x + y + z + u = 12 的正偶數解有幾組?
Solution:
令 x = 2 * X + 2 ......(1) y = 2 * Y + 2 ......(2) z = 2 * Z + 2 ......(3) u = 2 * U + 2 ......(4) (1)+(2)+(3)+(4) => 12 = x + y + z + u = 2 * (X + Y + Z + U) + 8 => X + Y + Z + U = 2
(2, 0, 0, 0) ... 4 組 (1, 1, 0, 0) ... 4 C = 6 組 2 4 + 6 = 10 組
4 4+2-1 5 5! 5! H = C = C = _______________ = _________ = 10 組 2 2 2 2! * (5 - 2)! 2! * 3!
讀到這裡, 請區分以下 3者的差別:
I. 從 n 個相異物取出 m 個之排列數
II. 從 n 個相異物取出 m 個之環狀排列數
III. 從 n 個相異物取出 m 個之組合數
取捨原理 - Principles of selection and deselection
如上圖, 設 A, B, C 是 3個有限集合, 則
n(A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(B ∩ C) - n(C ∩ A) - n(A ∩ B) + n(A ∩ B ∩ C)
Example: If X is the event that unemployment will go up, Y is the event that stock prices will go up, and Z is the event that interest rates will go up, express in words what events are represented by the following regions of the Venn diagram.
(a) rigion 4;
(b) rigion 1 and 3 together;
(c) rigion 3, 5, 6, and 8 together;
Solution:
(a) Since this rigion is contained in X and Z but not Y, it represents the
event that unemployment anf interest rates will go up, but stock prices
will not go up.
(b) Since this is the rigion common to Y and Z, it represnets the event that
stock prices and interest rates will go up.
(c) Since this is the entite rigion outside X, it represents the event that
unemployment will not go up.
列舉法 - Counting
Example: 甲乙二人比賽桌球, 每局不得和局, 若規定連贏 2局或先贏 3局者贏得比賽, 則勝負的情形有幾種?
Solution:
5 * 2 = 10 種
Example: To meet a graduation requirement, each of 3 students must study a frorign language, including, among others, French, German, Spanish. In how many ways can they make their chiocs, if we are interested only in how many of them will study French, how many of them will study German, and how many of them will study Spanish?
Solution:
There are 20 disctict possibilities.
互斥事件之加法原理 - Principle of addition on mutual-exclusive events
如上圖, A 點走到 B 點:
經過 P: 3 種
經過 Q: 2 種
經過P 與 經過Q 為互斥事件
所以 A 點走到 B 點 = 3 + 2 = 5 種選擇
Example: 將 15 用三個自然數之和來表示, 不考慮順序, 方法有幾種？
Solution:
考慮上圖 15 個球, 可將它們分為 3 組, 左, 中, 右, 每組個 5個. 請考慮下述 3種情況:
左邊移至中間: 移動 0 個 移動 1 個 移動 2 個 移動 3 個 移動 4 個 (左邊不得空置, 最多移動 4個)
中間往左右移 (左右不考慮順序): (左, 右) (1, 1) (1, 2) (1, 3) (2, 2)
左右往中間移 (左右不考慮順序): (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)
5 + 4 + 10 = 19 種
乘法法則 - Multiplication of choices
If an operation consists of two steps, of which the first can be done in N1 ways and for each of these the second can be done in N2 ways, then the whole operation can be done in N1 * N2 ways.
Example: In a medical study, patients are classified according to whether they blood type A, B, AB, or O, and also according to whether their blood pressure is low, normal, or high. In how manydifferent ways can a patient thus be classfied?
Solution:
4 * 3 = 12
Example: In how many different ways can the director of a search laboratory choose two chemists from among seven applicants and three physicists from among nine applicants?
Solution:
7 9 C * C = 21 * 84 = 1764 ways 2 3
If an operation consists of k steps, of which the first can be done in N1 ways and for each of these the second can be done in N2 ways, for each of the first two the third step can be done in N3 ways, and so forth, then the whole operation can be done in (N1 * N2 * ... * Nk) ways.
Example: In how many different ways can one order soup, a sandwich, a dessert, and a drink for lunch, if there is a choice of four different soups, three kind of sandwiches, five desserts, aand four drinks?
Solution:
The total number of ways is 4 * 3 * 5 * 4 = 240
The Number of ways in which a set of N distinct objects can be partitioned
into k subjects with N1 objects in the first subject, N2 objects in the
second subset, ..., and Nk objects in the k-th subset is
N N!
( ) = _______________________
N1,N2,...,Nk N1! * N2! * ... * Nk!
Proof. Since N1 objects going into the first subset can be choosen in
N
C ways, the N2 objects going into the second subset can be choosen in
N1
N-N1
C ways, the N3 objects going into the third subset can be choosen in
N2
N-N1-N2
C ways, and so forth,
N3
the total number of partitions is
N N N-N1 N-N1-N2-...
( ) = C * C * ... * C
N1,N2,...,Nk N1 N2 Nk
N! (N - N1 )!
= ________________ * ______________________ * ... *
N! * (N - N1)! N2! * (N - N1 - N2)!
(N - N1 - N2 - ... - Nk-1)!
_____________________________
Nk! * 0!
N!
= _____________________
N1! * N2! * ... Nk!
Example: In how many ways can seven buinessmen attending a convension be assigned to one triple and two double hotel rooms?
Solution:
7 4 2 C * C * C = 210 ways 3 2 2
7! ______________ = 210 ways 3! * 2! * 2!
走捷徑問題 I
Example: 如上圖, A 走到 B 有幾種走法?
Solution:
4 種
數字問題 I
Example: ⑴ 21600 正因數的個數?
Solution:
5 3 2 21600 = 2 * 3 * 5 答案: (5 + 1) * (3 + 1) * (2 + 1) = 72 個
⑵ 承上題, 21600 正因數有多少是 30 的倍數?
Solution:
21600 = 30 * 24 * 32 * 51 答案: (4 + 1) * (2 + 1) * (1 + 1) = 30 個
有限制條件的排列
Example: 甲乙丙丁戊己 6人排成一列, 下列情況有幾種排列方法?
⑴ 甲須排在乙左邊,
Solution:
乙
↓ ↓ ↓ ↓ ↓
甲 X X X X = 5 * 4!
↓ ↓ ↓ ↓
X 甲 X X X = 4 * 4!
↓ ↓ ↓
X X 甲 X X = 3 * 4!
↓ ↓
X X X 甲 X = 2 * 4!
↓
X X X X 甲 = 1 * 4!
(5 + 4 + 3 + 2 + 1) * 4! = 360 種
或者 我們引入機率的概念 甲乙排列共 2! = 2種排法 Probability(甲須排在乙左邊/甲乙全部之排列) = 1 / 2 因此 甲須排在乙左邊的排列法 = 全部之排列 * (1 / 2) 即 6! * (1 / 2) = 360 種
⑵ 甲排在乙左邊, 且乙排在丙左邊,
Solution:
Probability(甲排在乙左邊且乙排在丙左邊/甲乙丙全部之排列) = 1 / 3! = 1 / 6 因此 甲須排在乙左邊, 且乙須排在丙左邊的排列法 = 全部之排列 * (1 / 6) 6! * (1 / 6) = 120 種
⑶ 甲排在乙丙左邊,
Solution:
乙丙順序可對調 Probability(甲排在乙丙左邊/甲乙丙全部之排列) = 2 / 3! = 2 / 6 = 1 / 3 因此 甲須排在乙丙左邊 = 全部之排列 * (1 / 3) 6! * (1 / 3) = 240 種
Example: 將三個不同的球, 放入五個不同的箱子中, 但每箱最多放一球, 則有多少種不同的放法?
Solution:
兩個空箱 5 5! C = ______________ = 10 2 (5 - 2)!* 2! 共有 10種組合
另外 3個不同的球有 3! = 6 種排法
10 * 6 = 60 種
走捷徑問題 II
Example: 如上圖由 A 走到 B:
⑴ 有幾種走法?
Solution:
10! / (6! * 4!) = 210 種走法
⑵ 必須經過 C
Solution:
A->C->B 2 * 8! / (5! * 3!) = 112 種
⑶ 經過 C 或經過 D
Solution:
(A->C->B) + (A->D->B) - (A->C->D->B) = 112 + (7! / (4! * 3!) ) * ( 3! / (2! * 1!) ) - 60 = 157 種走法
⑷ 不經過 C 且不經過 D
Solution:
210 - 157 = 53 種走法
有限制條件下的重複排列
Example: 有 6件不同的禮物分給甲乙丙 3人, 請問下列狀況有幾種分法?
⑴ 甲至少得 1件
Solution:
全部 - 甲完全沒有 (只分乙丙) 36 - 26 = 665 種
⑵ 甲乙丙均至少得 1件
Solution:
至少有一人沒分到禮物的分法: 甲沒分到禮物, 其他人任意分的分法 = 乙沒分到禮物, 其他人任意分的分法 = 丙沒分到禮物, 其他人任意分的分法 = 26 共 3 * 26 = 192 種 把上述 192 中重複扣的加回來: 至少有兩人沒分到禮物的分法: 甲, 乙沒分到禮物, 其他人任意分的分法 = 乙, 丙沒分到禮物, 其他人任意分的分法 = 甲, 丙沒分到禮物, 其他人任意分的分法 = 16 共 3 * 16 = 3 種
維恩圖
X = 甲沒分到禮物的分法 = 64 Y = 乙沒分到禮物的分法 = 64 Z = 丙沒分到禮物的分法 = 64 X' = 甲至少得 1件 = 665 Y' = 乙至少得 1件 = 665 Z' = 丙至少得 1件 = 665 (X ∩ Y) = 甲,乙沒分到禮物的分法 = 1 (Y ∩ Z) = 乙,丙沒分到禮物的分法 = 1 (Z ∩ X) = 甲,丙沒分到禮物的分法 = 1 (X ∩ Y ∩ Z) = 甲,乙,丙沒分到禮物的分法 = 0 所以 有顏色的部分是 = 甲乙丙均至少得 1件的分法 = 全部 - X - Y - Z + (X ∩ Y) + (Y ∩ Z) + (Z ∩ X) - (X ∩ Y ∩ Z) 729 - 64 - 64 - 64 + 1 + 1 + 1 - 0 = 540 種
36 - 3 * 26 + 3 * 16 - 1 * 06 = 540 種
選取特定人事物
Example: 甲乙丙丁戊己庚 7人選 4人, 這4人中, 甲乙丙至少選 1人, 請問有幾種選法?
Solution:
4 3 C * C = 12 種 3 1
成雙成對的排列組合
Example: 有 5對夫婦跳雙人舞, 男女要共舞, 以下情況各有幾種?
(a) 夫婦不能共舞,
Solution:
5 5 5 5 5 5! - C * 4! + C * 3! - C * 2! + C * 1! - C * 0! = 44 種 1 2 3 4 5
(b) 恰有 1對夫婦共舞,
Solution:
A B C D E (夫) x | 1 2 3 4 5 (婦) 5 * ( A不能在第1位 且 B不能在第2位 且 C不能在第3位 且 D不能在第4位 ) = 5 * ( 4! - (A在第1位 或 B在第2位 或 C在第3位 或 D在第4位) ) 注意: A在第1位 ......(1) B在第2位 ......(2) C在第3位 ......(3) D在第4位 ......(4) (1),(3),(3),(4) 這 4個集合是有交集的
ABCD ABDC ACBD ACDB ADBC ADCBBACDBADC ......(1)BCADBCDA ......(2) BDAC ......(3)BDCACABDCADB ......(4)CBAD CBDACDAB ......(4) CDBA ......(6) DABC ......(7)DACBDBAC DBCADCBA ......(8) DCAB ......(9)排除A在第1位排除B在第2位排除C在第3位排除D在第4位 5 * 9 = 45 種
5 4 4 4 4 C * ( 4! - C * 3! + C * 2! - C * 1! + C * 0! ) = 45 種 1 1 2 3 4
(c) 恰有 2對夫婦共舞,
Solution:
A B C D E x | | 1 2 3 4 5ABCACBBCA ......(1)BACCAB ......(2)CBA排除A在第1位 排除B在第2位 排除C在第3位 10 * 2 = 20 種
5 3 3 3 C * ( 3! - C * 2! + C * 1! - C * 0! ) = 20 種 2 1 2 3
(d) 恰有 3對夫婦共舞,
Solution:
A B C D E x | | | 1 2 3 4 5ABBA ......(1) 排除A在第1位 排除B在第2位 10 * (A不能在第1位 且 B不能在第2位) = 10 * 1 = 10 種
5 2 2 C * (2! - C * 1! + C * 0! ) = 10 種 3 1 0
(e) 至少 1對夫婦共舞.
Solution:
至少1對夫婦共舞 = 恰有1對夫婦共舞+恰有2對夫婦共舞+恰有3對夫婦共舞+恰有4對夫婦共舞+恰有5對夫婦共舞= 45 + 20 + 10 + 0 + 1 = 76 種
Example: 四對夫妻圍圓桌而坐, 下列各情況, 各有幾種坐法?
(1) 男女相間隔且夫妻相鄰,
Solution:
4! ____ * 2 = 12 種 4
(2) 每對夫妻相對,
Solution:
4! * 2 = 48 種
(3) 恰有三對夫妻相鄰,
Solution:
4 先選哪 3對夫妻相鄰 => C 3
3對夫妻環狀排列 => 2!
3對夫妻可任意互換 => (2 * 2 * 2)
3
(目前圓桌有6人) 最後讓第 4對夫妻 (2人) 任意取 3對夫妻之間隙 (3個) 填入 => C * 2!
2
4 3 故共有 C * 2! * (2 * 2 * 2) * C * 2! = 384 種 3 2
(4) 夫妻不相鄰且男女相間隔.
Solution:
4! - 12 = 12 種 男女相間 - 男女相間隔且夫妻相鄰
數字問題 II
Example: 從一副撲克牌中任選 5張, 恰巧選到 Two Pairs 的個數?
Solution:
13 4 4 11 4 C * C * C * C * C = 123552 2 2 2 1 1
二項式定理 - Binomial Theorem
n n n 0 n n-1 1 n 0 n
(x + y) = C * x * y + C * x * y + ... + C * x * y
0 1 n
n n n-r r
= ∑ C * x * y
r=0 r
Example: Try to prove the following formula.
k m n m+n ∑ C * C = C r = 0 r k-r k
Solution:
Proof.
m+n m n
(1 + y) = (1 + y) * (1 + y)
k m+n m+n
The coefficent of y in (1 + y) is C , and
k
k m n
The coefficent of y in (1 + y) * (1 + y) =
m m m m n n n n
( C + C * y + ... + C * y ) * ( C + C * x + ... + C * y )
0 1 m 0 1 n
is the sum of the products which we obtain by multipying the constant
k
term of the first factor by the coefficient of y in the second factor,
k m n
... , and the coefficient of y in (1 + y) * (1 + y) is
m n m n m n m n
C * C + C * C + C * C + C * C
0 k 1 k-1 2 k-2 k 0
k m n m+n
= ∑ C * C = C
r = 0 r k-r k
and this completes the proof.
3
Example:
What is the coefficient of X3 * Y * Z2 of (X + Y + Z)6 ?
Solution:
Substituting n = 6, r1 = 3, r2 = 1, and r3 = 2 into the formula above, we get
6!
______________ = 60
3! * 1! * 2!
二項式係數法則 - Rule for binomial coefficents
n n C = C for r = 0, 1, 2, ..., n r n-r
Example: Determin the value of
75 C 72
Solution:
75 75 75 * 74 * 73 C = C = ______________ = 67525 72 3 3!
Example:
求多項式 (1+x)1 + (1+x)2 + ... + (1+x)10 之展開式中 x2 之係數?
Solution:
(1 + x) * ((1 + x)10 - 1) (1 + x)11 - (1 + x) 原式 = ___________________________ = _____________________ 1 + x -1 x 11 C = 165 3
Example:
多項式 (x100 + 1) 除以 (x - 1)2 之餘式?
Solution:
100 100 100 100 99 100 2 100 100 0
原式 = ((x - 1) + 1) + 1 = C * (x - 1) + C * (x - 1) + ... + C * (x - 1) + C * (x - 1) + C * (x - 1) + 1
0 1 98 99 100
2
|________________ 可被 (x -1) 除 _________________________|
餘式 = 10 * (x - 1) + 1 + 1 = 10 * x - 8
Example:
n n 0 n 1 n 2 n n-1 n n (1 + x) = C * x + C * x + C * x + ... + C * x + C * x 0 1 2 n-1 n
Ⓐ 令 X = 1, => n n n n n C + C + C + ... + C = 2 0 1 2 n
Ⓑ 令 X = -1, => n n n n n C - C + C - ... + (-1) * C = 0 0 1 2 n
Ⓒ 將 ( Ⓐ+Ⓑ ) / 2 可得 n n n n-1 C + C + C + ... 偶次項係數和 2 0 2 4
Ⓓ 將 ( Ⓐ-Ⓑ ) / 2 可得 n n n n-1 C + C + C + ... 奇次項係數和 2 1 3 5
Example:
10 10 10 10 試求 C + 3 * C + 5 * C + ... + 21 * C 之值? 0 1 2 10
Solution:
10 10 10 10
S = C + 3 * C + 5 * C + ... + 21 * C
0 1 2 10
10 10 10 10
S = 21 * C + 19 * C + 17 * C + ... + C
0 1 2 10
10 10 10 10
因 C = C , C = C , ...
10 0 9 1
10 10 10 10
2 * S = 22 * ( C + C + ... + C ) = 22 * 2
1 2 10
=>
10
S = 11 * 2 = 11264
巴斯卡定理 - Pascal's Triangle
當 1 <= k <= (n - 1) 時, n-1 n-1 n C + C = C k-1 k k
Example:
2 3 10 試求 C + C + ... + C 2 2 2
Solution:
2 3 10
C + C + ... + C
2 2 2
3 3 4 5 10
= (C + C ) + C + C + ... + C
3 2 2 2 2
4
|_______| = C
3
4 4 5 6 10
= (C + C ) + C + C + ... + C
3 2 2 2 2
= ...
10 10
= C + C
3 2
11
= C = 11! / (3! * (11-3)! ) = 11! / (3! * 8!) = 165
3
Example: (1) 求 11 的 4 次方.
Solution:
14641
(2) 11 的 6 次方
Solution:
1771561
Email: jasonc@mail2000.com.tw . 請尊重原創, 使用圖文時載明出處. 謝謝.
-
(Finished)
留言列表
{{ article.title }}
