排列與組合

四個基本計數原理

( 1 ) (1) (1) 加法原理: 設集合 S S S 被劃分成兩兩不相交的部分 S 1 S_1 S1?, S 2 S_2 S2? … S m S_m Sm?, 則 S S S的物件數目可以通過確定它的每一個部分的物件數目并如此相加而得到 :
∣ S ∣ = ∣ S 1 ∣ + ∣ S 2 ∣ + . . . + ∣ S m ∣ {\vert S \vert} = {\vert S_1 \vert} + {\vert S_2 \vert} +...+ {\vert S_m \vert} ∣S∣=∣S1?∣+∣S2?∣+...+∣Sm?∣
例如: 從河北到四川可以坐火車或者坐飛機, 坐飛機有 3 3 3 種方法, 坐火車有 4 4 4 種

方法, 則從河北到四川的方法有 3 + 4 = 7 3+4=7 3+4=7 種方法

( 2 ) (2) (2) 乘法原理 : 加法原理的推論

例如: 從河北到四川第一程需要坐飛機,第二程需要坐火車, 坐飛機有 3 3 3 種方法, 坐火車有 4 4 4 種

方法, 則從河北到四川的方法有 3 ? 4 = 12 3*4=12 3?4=12 種方法

( 3 ) (3) (3) 減法原理: 令 A A A 是一個集合, 而 U U U 是包含 A A A 的更大集合, 設

A ? \overset{-}{A} A?是 A A A 在 U U U 中的補,那么 A A A 中的物件數目 ∣ A ∣ {\vert A \vert} ∣A∣由以下法則給出 ∣ A ∣ = ∣ U ∣ ? ∣ A ? ∣ {\vert A \vert} = {\vert U \vert} - {\vert \overset{-}{A} \vert} ∣A∣=∣U∣?∣A?∣

例如: 計算 1..600 1..600 1..600 中不能被 6 6 6 整除的數字個數

∣ U ∣ = 600 {\vert U \vert} = 600 ∣U∣=600

∣ A ? ∣ = 600 6 = 100 {\vert\overset{-}{A} \vert} = \frac{600}{6}=100 ∣A?∣=6600?=100

∣ A ∣ = ∣ U ∣ ? ∣ A ? ∣ = 600 ? 100 = 500 {\vert A \vert} = {\vert U \vert} - {\vert \overset{-}{A} \vert} = 600 -100 =500 ∣A∣=∣U∣?∣A?∣=600?100=500

( 4 ) (4) (4) 除法原理:令 S S S是一個有限集合, 把它劃分成 k k k 個部分使得每一部分包含的物件數目相等, 于是, 此劃分中的部分數目由下述公式給出:

k = ∣ S ∣ 在 一 個 部 分 中 的 對 象 數 目 k = \frac{{\vert S \vert}}{在一個部分中的物件數目} k=在一個部分中的對象數目∣S∣?

例如: 在一排鴿巢中有 740 740 740 只鴿子,如果每個鴿巢含有 5 5 5 只鴿子, 那么鴿巢的數目為 740 5 = 148 \frac{{740}}{5}=148 5740?=148

兩道例題:

( 1 ) (1) (1) : 在 0 0 0 和 10000 10000 10000 中有多少個整數恰好有一位數字是 5 5 5

解法: 通過添加前導 0 0 0 (如 6 6 6 看作 0006 0006 0006 , 25 25 25 看作 0025 0025 0025 , 325 325 325 看作 0325 0325 0325), 可以把 S S S 中的每一個數都當作 4 4 4 位數, 現在我們根據數字 5 5 5 是位于第 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4位從而把集合分成 4 4 4 個集合, 這 4 4 4 個集合中的每一個都含有 9 × 9 × 9 = 729 9\times9\times9 = 729 9×9×9=729個整數,從而 S S S 所含有的整數個數等于 4 × 729 = 2916 4\times729 = 2916 4×729=2916

(根據這個我出了一道題,可以試著練習一下題目鏈接)

( 2 ) (2) (2): 由數字 1 , 1 , 1 , 3 , 8 1,1,1,3,8 1,1,1,3,8 可以構造出多少個不同的 5 5 5 位數?

解法: 實際上我們只有兩種選擇, 3 3 3 要放置在哪里(有 5 5 5 種選擇), 8 8 8 要放置在哪里(有 4 4 4 種選擇),剩下的位置自動由 1 1 1 占位,所以根據乘法原理,答案是
5 × 4 = 20 5\times4=20 5×4=20

集合的排列

定理 1 1 1: 對于正整數 n n n 和 r r r , r ≤ n r\leq n r≤n, 有
P ( n , r ) = n × ( n ? 1 ) × ? × ( n ? r + 1 ) P(n,r) = n \times (n-1) \times \cdots \times (n-r+1) P(n,r)=n×(n?1)×?×(n?r+1)
并規定 0 ! = 1 0! = 1 0!=1

于是可以寫成 P ( n , r ) = n ! ( n ? r ) ! P(n,r) = \frac{n!}{(n-r)!} P(n,r)=(n?r)!n!?

例題: 將 26 26 26 個字母排序, 使得元音字母 a , e , i , o , u a,e,i,o,u a,e,i,o,u任意兩個都不能連續出現,這種排序方法的總數是多少?

解法: 首先排序 21 21 21 個輔音字母, 總共有 21 ! 21! 21! 種方法, 然后將 5 5 5 個元音字母插空到 22 22 22 個位置種,所以答案是

P ( 22 , 5 ) × 21 ! = 22 ! 17 ! × 21 ! P(22,5) \times 21!= \frac{22!}{17!} \times 21! P(22,5)×21!=17!22!?×21!

剛剛例題的排列叫做線性排列, 除了線性排列以外, 還有圓排列

考慮以下問題

6個孩子沿著圓圈行進,他們能以多少種不同的方式形成一個圓?

解法:
因為孩子們在行進中, 因此重要的是他們彼此間的相對位置, 因此只要其中一個排列可以通過旋轉與另外一個重合,即通過一個圓周位移而得到另一個, 所以每一個回圈排列對應 6 6 6 個線性排列

例如下面的回圈排列:

來自于下面的線性排列中的每一個:

123456 123456 123456
234561 234561 234561
345612 345612 345612
456123 456123 456123
561234 561234 561234
612345 612345 612345

把上面每一個排列的最后一位移到第一位之前就形成前面的回圈排列,于是, 6 6 6個孩子的線性排列與回圈排列的對應是 6 6 6 比 1 1 1 ,因此為了求回圈排列數目, 我們把線性排列個數除以 6 6 6 ,因此 6 6 6 個孩子的回圈排列數目是
6 ! 6 = 5 ! \frac{6!}{6} = 5! 66!?=5!

定理 2 2 2: n n n 元素集合的回圈 r r r 排列的數目是

P ( n , r ) r = n ! r × ( n ? r ) ! \frac{P(n,r)}{r}= \frac{n!}{r\times(n-r)!} rP(n,r)?=r×(n?r)!n!?
特別地, n n n 元素集合的回圈排列的數目是 ( n ? 1 ) ! (n-1)! (n?1)!

例題1: 10 10 10 個人要圍坐一個圓桌,其中有兩個人不愿意挨著坐, 共有多少圓形座位設定方法?

解法1: 運用減法原理, 將 p 1 p_1 p1? p 2 p_2 p2? 兩個人看作一個整體 X X X , 于是考慮 9 9 9 個人按照圓桌座位,是 2 × 9 ! 9 = 2 × 8 ! 2 \times\frac{9!}{9} =2\times 8! 2×99!?=2×8!, 十個人按照圓桌座位方法總數是 9 ! 9! 9! ,所以答案是
9 ! ? 2 × 8 ! 9!-2\times 8! 9!?2×8!

解法2: p 1 p_1 p1? 左右兩邊的座位方法有 8 × 7 8 \times 7 8×7 種可能, 將這三個人看作一個整體, 于是考慮 8 8 8 個人按照圓桌座位,是 2 × 8 ! 8 = 2 × 7 ! 2 \times\frac{8!}{8} =2\times 7! 2×88!?=2×7!,所以答案是
8 × 7 × 7 ! 8\times 7 \times 7! 8×7×7!

例題2: 用 20 20 20 種顏色的念珠串成項鏈,有多少種不同的項鏈?

解法:

首先很明顯是回圈排列, 所以項鏈最多數目是 20 ! 20 = 19 ! \frac{20!}{20} =19! 2020!?=19!,然后考慮項鏈可以翻轉過來而不改變排列,所以答案是 19 ! / 2 19!/2 19!/2

關于這部分的理解,例如是 3 3 3 個人按照圓桌座位排序是這兩種

其中每個人的相對位置改變了, 所以是兩種方法

但對于項鏈來說,可以翻轉,所以本質上是一種項鏈

(不知道我說清楚了沒, 實在不理解可以想圍著圓桌坐沒法翻轉過去倒立著坐)

集合的組合

定理1: 對于 0 ≤ r ≤ n 0 \leq r \leq n 0≤r≤n , 有

P ( n , r ) = r ! ( n r ) P(n,r)=r! \begin{pmatrix} n \\ r \\ \end{pmatrix} P(n,r)=r!(nr?)

因此 ( n r ) = n ! r ! ( n ? r ) ! \begin{pmatrix} n \\ r \\ \end{pmatrix}=\frac{n!}{r!(n-r)!} (nr?)=r!(n?r)!n!?

例如: 在平面上給出 25 25 25 個點使得沒有 3 3 3 個點共線, 這些點確定多少個三角形?

解法:

( 25 3 ) = 25 ! 3 ! 22 ! \begin{pmatrix} 25 \\ 3 \\ \end{pmatrix}=\frac{25!}{3!22!} (253?)=3!22!25!?

定理2: (帕斯卡公式) 對于所有滿足 1 ≤ k ≤ n ? 1 1 \leq k \leq n-1 1≤k≤n?1 的整數 n n n 和 k k k , 有

( n k ) = ( n ? 1 k ) + ( n ? 1 k ? 1 ) \begin{pmatrix} n \\ k \\ \end{pmatrix}=\begin{pmatrix} n-1 \\ k \\ \end{pmatrix}+\begin{pmatrix} n-1 \\ k-1 \\ \end{pmatrix} (nk?)=(n?1k?)+(n?1k?1?)

可以從以下角度理解:

在 n n n 個蘋果中選出 k k k 個蘋果, 對于第 1 1 1 個蘋果,有兩種選擇,可以選也可以不選

如果選擇了, 則是從剩下 n ? 1 n-1 n?1 個蘋果中選出 k ? 1 k-1 k?1 個蘋果,即 ( n ? 1 k ? 1 ) \begin{pmatrix} n-1 \\ k-1 \\ \end{pmatrix} (n?1k?1?)

如果不選 ,則是從剩下 n ? 1 n-1 n?1 個蘋果中選出 k k k 個蘋果,即 ( n ? 1 k ) \begin{pmatrix} n-1 \\ k \\ \end{pmatrix} (n?1k?)

定理3: 對于 n ≥ 0 n \geq 0 n≥0, 有

( n 0 ) + ( n 1 ) + ( n 2 ) + ? + ( n n ) = 2 n \begin{pmatrix} n \\ 0 \\ \end{pmatrix} +\begin{pmatrix} n \\ 1 \\ \end{pmatrix}+\begin{pmatrix} n \\ 2 \\ \end{pmatrix}+ \cdots + \begin{pmatrix} n \\ n \\ \end{pmatrix} = 2^n (n0?)+(n1?)+(n2?)+?+(nn?)=2n

多重集合的排列

定理1:

設 S S S 是有 k k k 種不同型別物件的多重集合, 每一個元素都有無線重復數,那么 S S S 的 r r r 排列是 k r k^r kr

例如: 由 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4 可以構成多少個四位數,答案顯然是 4 4 4^4 44

定理2: 設 S S S 是多重集合, 它有 k k k 種不同型別的物件, 且每一種型別的有限重復數分別是 n 1 , n 2 , ? ? , n k n_1, n_2, \cdots ,n_k n1?,n2?,?,nk?,且 S S S 的大小為 n = n 1 + n 2 + ? + n k n=n_1+n_2+ \cdots +n_k n=n1?+n2?+?+nk?, 則 S S S 的排列數目是

n ! n 1 ! n 2 ! ? n k ! \frac{n!}{n_1!n_2! \cdots n_k!} n1?!n2?!?nk?!n!?

例題: 詞MISSISSIPPI中字母的排列數是

11 ! 1 ! 4 ! 4 ! 2 ! \frac{11!}{1!4!4!2!} 1!4!4!2!11!?

因為這個數字等于多重集合 { 1 ? M , 4 ? I , 4 ? S , 2 ? P } \lbrace 1 \cdot M, 4 \cdot I,4 \cdot S,2 \cdot P \rbrace {1?M,4?I,4?S,2?P} 的排列數

對于定理 2 2 2 還有另外一種理解方式:

把一個物件集合劃分成指定大小的各個部分, 其中這些部分都有指定給他們的標簽, 為了方便理解,給出以下例子

例子: 考慮有 4 4 4 個物件的集合 { a , b , c , d } \lbrace a,b,c,d \rbrace {a,b,c,d}, 把它劃分成兩個子集, 每一個大小為 2 2 2

如果沒有標簽, 那么有三種劃分方式:
{ a , b } \lbrace a,b \rbrace {a,b}; { c , d } \lbrace c,d \rbrace {c,d}
{ a , c } \lbrace a,c \rbrace {a,c}; { b , d } \lbrace b,d \rbrace {b,d}
{ a , d } \lbrace a,d \rbrace {a,d}; { b , c } \lbrace b,c \rbrace {b,c}

現在假設給這些部分做上不同的標簽, (例如, 紅色和藍色), 則有 6 6 6 種劃分,例如對于 { a , b } \lbrace a,b \rbrace {a,b} , { c , d } \lbrace c,d \rbrace {c,d}有

紅色 { a , b } \lbrace a,b \rbrace {a,b} 藍色 { c , d } \lbrace c,d \rbrace {c,d}
藍色 { a , b } \lbrace a,b \rbrace {a,b} 紅色 { c , d } \lbrace c,d \rbrace {c,d}

在一般情況下, 我們可以用 B 1 , B 2 , ? ? , B k B_1, B_2,\cdots, B_k B1?,B2?,?,Bk? 標記這些部分,并且把這些部分想象成一些盒子,此時,以下定理成立

定理3: 設 n n n 是正整數, 并設 n 1 , n 2 , ? ? , n k n_1, n_2, \cdots, n_k n1?,n2?,?,nk? 且 n = n 1 + n 2 + ? + n k n=n_1+n_2+\cdots + n_k n=n1?+n2?+?+nk?, 把 n n n 物件集合劃分成 k k k 個標有標簽的盒子, 且第 1 1 1 個盒子有 n 1 n_1 n1? 個物件, 第 2 2 2 個盒子有 n 2 n_2 n2? 個物件, ? \cdots ? , 第 k k k 個盒子有 k k k 個物件,這樣的劃分方法數有

n ! n 1 ! n 2 ! ? n k ! \frac{n!}{n_1!n_2! \cdots n_k!} n1?!n2?!?nk?!n!?

如果這些盒子沒有標簽,且 n 1 = n 2 = ? = n k n_1=n_2=\cdots = n_k n1?=n2?=?=nk?,那么劃分為

n ! k ! n 1 ! n 2 ! ? n k ! \frac{n!}{k!n_1!n_2! \cdots n_k!} k!n1?!n2?!?nk?!n!?

這是因為, 對于把這些物件分配到 k k k 個沒有標簽的盒子的每一種方法, 都有 k ! k! k! 種方法給這些盒子標上標簽,因此使用除法原理, 沒有標簽的盒子的劃分是

n ! k ! n 1 ! n 2 ! ? n k ! \frac{n!}{k!n_1!n_2! \cdots n_k!} k!n1?!n2?!?nk?!n!?

如果不好理解, 可以從以下方面考慮

對于定理 2 2 2 是有 k k k 種元素,每一種有 n 1 , ? ? , n k n_1,\cdots, n_k n1?,?,nk? 個,則每一種元素要占位 n 1 , ? ? , n k n_1,\cdots, n_k n1?,?,nk?個

而定理 3 3 3 是 將 n = n 1 , ? ? , n k n=n_1,\cdots, n_k n=n1?,?,nk?個元素, 裝在 k k k 個不同的盒子里 (染成 k k k 種顏色), 每一個盒子分別要裝 n 1 , ? ? , n k n_1,\cdots, n_k n1?,?,nk? 個元素, 也可以看作是有 k k k 種元素,每一種有 n 1 , ? ? , n k n_1,\cdots, n_k n1?,?,nk? 個

如果還不是很清楚的話,我們可以回看這個例子:

考慮有 4 4 4 個物件的集合 { a , b , c , d } \lbrace a,b,c,d \rbrace {a,b,c,d}, 把它劃分成兩個子集, 每一個大小為 2 2 2, 且標記為兩種顏色 (紅色和藍色)

也可以看作是 4 4 4 個元素分成 2 2 2 種 , 每一種都有 2 2 2 個

可以細細體會一下

例子: 有多少種方法在 8 × 8 8 \times 8 8×8 的棋盤上放置 8 8 8 個非攻擊型車? (兩個車能相互攻擊當且僅當它們位于棋盤的同一行或同一列)

解法: 因為兩輛車不同位于同一行和同一列 , 所以我們可以一列一列的擺放車, 第 1 1 1 列的車有 8 8 8 行可以放置 , 第 2 2 2 列的車不能和上一列的車擺在同一行 , 有 7 7 7 行可以放置 , 之后同理, 所以很明顯有 8 ! 8! 8! 種方法

在上面討論中, 我們默認每輛車之間沒有區別, 現在我們考慮有 8 8 8 輛不同顏色的車, 在決定哪 8 8 8 個方格要被這些車占據后 ( 8 ! 8! 8! 種可能), 我們現在還要決定在每個占據的方格上的車是什么顏色的, 很明顯也有 8 ! 8! 8! 種可能,于是,在 8 × 8 8 \times 8 8×8 棋盤上具有 8 8 8 種不同顏色的 8 8 8 個非攻擊型的車的放置方法數為 8 ! × 8 ! 8! \times 8! 8!×8!

現在假設不是有 8 8 8 個不同顏色的車, 而是有 1 1 1 個紅車 ( R R R) , 3 3 3 個藍車 ( B B B) 和 4 4 4 個黃車 ( Y Y Y), 同時還假設同顏色的車之間沒有區別, 現在, 我們看到一個多重集合 { 1 ? R , 3 ? B , 4 ? Y } \lbrace 1 \cdot R, 3 \cdot B,4 \cdot Y \rbrace {1?R,3?B,4?Y}

根據定理 2 2 2 這個多重集合的排列個數等于
8 ! 1 ! 3 ! 4 ! \frac{8!}{1!3!4!} 1!3!4!8!?

因此,在 8 × 8 8 \times 8 8×8 棋盤上放置 1 1 1 個紅車 , 3 3 3 個藍車和 4 4 4 個黃車并使它們互相之間不能攻擊的方法數為

8 ! 8 ! 1 ! 3 ! 4 ! 8!\frac{8!}{1!3!4!} 8!1!3!4!8!?

多重集合的組合