文章目錄
- 一、兩個計數原則、集合排列示例
- 二、集合排列、圓排列示例
排列組合參考部落格 :
- 【組合數學】基本計數原則 ( 加法原則 | 乘法原則 )
- 【組合數學】集合的排列組合問題示例 ( 排列 | 組合 | 圓排列 | 二項式定理 )
- 【組合數學】排列組合 ( 排列組合内容概要 | 選取問題 | 集合排列 | 集合組合 )
- 【組合數學】排列組合 ( 排列組合示例 )
- 【組合數學】排列組合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重複度大于排列數 | 多重集非全排列 某些元素重複度小于排列數 )
- 【組合數學】排列組合 ( 多重集組合數 | 所有元素重複度大于組合數 | 多重集組合數 推導 1 分割線推導 | 多重集組合數 推導 2 不定方程非負整數解個數推導 )
- 【組合數學】排列組合 ( 多重集組合數示例 | 三個計數模型 | 選取問題 | 多重集組合問題 | 不定方程非負整數解問題 )
一、兩個計數原則、集合排列示例
排列
26
26
26 個字母 , 使得
a
,
b
a,b
a,b 之間有
7
7
7 個字母 , 求排列方法數 ;
需要使用 分類計數原理 ( 加法原則 ) , 分步計數原理 ( 乘法原則 ) ;
-
分類計數 ( 加法原則 ) : 有
3
3
3 類方案 , 第一類有
2
2
2 個方案 , 第二類有
4
4
4 個方案 , 第三類有
1
1
1 個方案 , 總共有
2
+
4
+
1
=
7
2 + 4 + 1 = 7
2+4+1=7 個方案 ;
-
分步計數原理 ( 乘法原則 ) : 有
3
3
3 類方案 , 第一步有
2
2
2 個方案 , 第二步有
4
4
4 個方案 , 第三步有
1
1
1 個方案 , 總共有
2
×
4
×
1
=
8
2 \times 4 \times 1 = 8
2×4×1=8 個方案 ;
1. 首先使用分步計數原理 ,
-
第一步 : 先構造出以
a
,
b
a,b
a,b 為邊界 , 中間含有
7
7
7 個字母的子結構 ;
-
第二步 : 将
a
,
b
a,b
a,b 子結構作為元素 , 與其它
26
−
9
=
17
26-9 = 17
26−9=17 個子元素一起 , 總共
18
18
18 個元素進行全排列 ;
分步計數原理對應乘法法則 , 最終結果是 第一步的方案個數 乘以 第二步的方案個數 ;
2. 第一步計算 : 先構造出以
a
,
b
a,b
a,b 為邊界 , 中間含有
7
7
7 個字母的子結構 ;
該子結構中的
7
7
7 個字母 , 相當于從除
a
,
b
a,b
a,b 之外的其它
24
24
24 個字母中選取
7
7
7 個字母進行排列 ,
一一對應 : 相當于元素不重複的集合中 , 進行有序選取 , 對應着集合的排列問題 , 使用集合排列公式進行計算 ;
24
24
24 個字母中選取
7
7
7 個字母進行排列 , 選取方法有
P
(
24
,
7
)
P(24, 7)
P(24,7) 種 ;
這裡涉及到分類計數原理 ,
-
第一類是
a
a
a 在前 ,
b
b
b 在後的情況 , 選取方法有
P
(
24
,
7
)
P(24, 7)
P(24,7) 種 ;
-
第二類是
b
b
b 在前 ,
a
a
a 在後的情況 , 選取方法有
P
(
24
,
7
)
P(24, 7)
P(24,7) 種 ;
分類計數原理對應加法法則 , 總的方法數是 第一類 與 第二類 相加之和 , 選取方法有
2
P
(
24
,
7
)
2\ P(24, 7)
2 P(24,7) 種 ;
3. 第二步計算 : 将
a
,
b
a,b
a,b 子結構作為元素 , 與其它
26
−
9
=
17
26-9 = 17
26−9=17 個子元素一起 , 總共
18
18
18 個元素進行全排列 ;
18
18
18 個元素進行全排列 , 結果是
18
!
18!
18! ;
4. 第一步方案 乘以 第二步方案 ( 分步計算原理 加法法則 ) :
第一步的方案個數 乘以 第二步的方案個數 ;
N
=
2
P
(
24
,
7
)
18
!
N = 2\ P(24, 7) \ 18!
N=2 P(24,7) 18!
二、集合排列、圓排列示例
10
10
10 個男生 ,
5
5
5 個女生, 站成一排 , 如果沒有女生相鄰 , 有多少種方法 ? 如果站成一圈 , 有多少種方法 ?
需要使用 分類計數原理 ( 加法原則 ) , 分步計數原理 ( 乘法原則 ) ;
-
分類計數 ( 加法原則 ) : 有
3
3
3 類方案 , 第一類有
2
2
2 個方案 , 第二類有
4
4
4 個方案 , 第三類有
1
1
1 個方案 , 總共有
2
+
4
+
1
=
7
2 + 4 + 1 = 7
2+4+1=7 個方案 ;
-
分步計數原理 ( 乘法原則 ) : 有
3
3
3 類方案 , 第一步有
2
2
2 個方案 , 第二步有
4
4
4 個方案 , 第三步有
1
1
1 個方案 , 總共有
2
×
4
×
1
=
8
2 \times 4 \times 1 = 8
2×4×1=8 個方案 ;
1.
10
10
10 個男生 ,
5
5
5 個女生, 站成一排 , 如果沒有女生相鄰 , 有多少種方法 :
需要使用分步處理 : 先把男生放好 , 然後将女生插空放進去 ;
① 第一步 : 先把男生放好 , 男生
10
10
10 個 , 站好以後有
11
11
11 個格子 ;
10
10
10 個男生的放置位置 , 元素不重複的有序選取 , 這是集合排列問題 , 排列方案有
P
(
10
,
10
)
=
10
!
P(10,10) = 10!
P(10,10)=10! 個方案 ;
② 第二步 : 然後将女生插空放進去 ,
5
5
5 個女生隻能放在這
11
11
11 個格子中 ;
11
11
11 個格子中放
5
5
5 個女生 , 元素不重複的有序選取 , 這是集合的排列問題 , 排列方案有
P
(
11
,
5
)
P(11, 5)
P(11,5)
③ 分步計數原理 ( 乘法原則 ) : 将 第一步方案數 與 第二步方案數 相乘 , 方案個數是 :
P
(
10
,
10
)
P
(
11
,
5
)
P(10,10) \ P(11, 5)
P(10,10) P(11,5)
2.
10
10
10 個男生 ,
5
5
5 個女生, 站成一圈 , 如果沒有女生相鄰 , 有多少種方法 :
需要使用分步處理 : 先把男生放好 , 然後将女生插空放進去 ;
① 第一步 : 先把男生放好排成一圈 , 男生
10
10
10 個 , 因為是排成一圈 , 是以站好以後隻有
10
10
10 個格子 ;
10
10
10 個男生的放置位置 , 元素不重複的有序選取 , 這是集合圓排列問題 , 需要使用圓排列公式 , 排列方案有
P
(
10
,
10
)
10
\cfrac{P(10,10)}{10}
10P(10,10) 個方案 ;
參考 : 【組合數學】排列組合 ( 排列組合内容概要 | 選取問題 | 集合排列 | 集合組合 ) 四、環排列
n
n
n 元集
S
S
S , 從
S
S
S 集合中 有序 , 不重複 選取
r
r
r 個元素 ,
S
S
S 集合的
r
−
r-
r− 環排列數
=
P
(
n
,
r
)
r
= \dfrac{P(n,r)}{r}
=rP(n,r)
r
r
r 個不同的線性排列 , 相當于同一個環排列 ;
一個環排列 , 從任意位置剪開 , 可以構成
r
r
r 種不同的線性排列 ;
② 第二步 : 然後将女生插空放進去 ,
5
5
5 個女生隻能放在這
10
10
10 個格子中 ;
![動态規劃與排列組合二項式的關系[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)