￭排列與組合 - Permutations and Combinations－Lexra Pixnet

不可重複之排列 - 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 個之排列數

n^m

Example: 3張紙牌 A,B,C 任抽一張, 抽完放回, 連抽兩次之排列數.

Solution:

3²  = 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;

Veen Diagram

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 * 2⁴ * 3² * 5¹

答案: (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:

全部 - 甲完全沒有 (只分乙丙)

3⁶    -  2⁶                    = 665 種

⑵ 甲乙丙均至少得 1件

Solution:

至少有一人沒分到禮物的分法: 

甲沒分到禮物, 其他人任意分的分法 =
乙沒分到禮物, 其他人任意分的分法 =
丙沒分到禮物, 其他人任意分的分法 
= 2⁶
共 3 * 2⁶  = 192 種

把上述 192 中重複扣的加回來:

至少有兩人沒分到禮物的分法:

甲, 乙沒分到禮物, 其他人任意分的分法 = 
乙, 丙沒分到禮物, 其他人任意分的分法 =
甲, 丙沒分到禮物, 其他人任意分的分法
= 1⁶
共 3 * 1⁶   = 3 種

維恩圖

Veen Diagram

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  種

3⁶ - 3 * 2⁶  + 3 * 1⁶  - 1 * 0⁶ = 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
ADCB
BACD
BADC ......(1)
BCAD
BCDA ......(2)
BDAC ......(3)
BDCA
CABD
CADB ......(4)
CBAD
CBDA
CDAB ......(4)
CDBA ......(6)
DABC ......(7)
DACB
DBAC
DBCA
DCBA ......(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

Solution:

A B C D E
  x   | | 
1 2 3 4 5

ABC
ACB
BCA ......(1)
BAC
CAB ......(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 5

AB
BA ......(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.

Example:

What is the coefficient of X³  * Y * Z²  of (X + Y + Z)⁶  ?

Solution:

Substituting n = 6, r₁ = 3, r₂ = 1, and r₃ = 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+x)² + ... + (1+x)¹⁰   之展開式中 x² 之係數?

Solution:

        (1 + x) * ((1 + x)¹⁰ - 1)    (1 + x)¹¹  - (1 + x)
原式 = ___________________________ = _____________________ 
            1 + x -1                      x
 11
C   = 165
 3

Example:

多項式 (x¹⁰⁰    + 1) 除以 (x - 1)²  之餘式?

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: