文章目錄
-
- 一、計數模型
- 二、常見的組合計數
一、計數模型
目前涉及到的計數模型 :
1 . 選取問題 :
n
n
n 元集
S
S
S , 從
S
S
S 集合中選取
r
r
r 個元素 ;
根據 元素是否允許重複 , 選取過程是否有序 , 将選取問題分為四個子類型 :
| 元素不重複 | 元素可以重複 | |
| 有序選取 | 集合排列 P ( n , r ) P(n,r) P(n,r) | 多重集排列 |
| 無序選取 | 集合組合 C ( n , r ) C(n,r) C(n,r) | 多重集組合 |
選取問題中 :
-
-
不可重複的元素 , 有序的選取 , 對應 集合的排列 ;
P
(
n
,
r
)
=
n
!
(
n
−
r
)
!
P(n,r) = \dfrac{n!}{(n-r)!}
P(n,r)=(n−r)!n!
-
不可重複的元素 , 無序的選取 , 對應 集合的組合 ;
C
(
n
,
r
)
=
P
(
n
,
r
)
r
!
=
n
!
r
!
(
n
−
r
)
!
C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}
C(n,r)=r!P(n,r)=r!(n−r)!n!
-
可重複的元素 , 有序的選取 , 對應 多重集的排列 ;
全
排
列
=
n
!
n
1
!
n
2
!
⋯
n
k
!
全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!}
全排列=n1!n2!⋯nk!n! , 非全排列
k
r
,
r
≤
n
i
k^r , \ \ r\leq n_i
kr, r≤ni
-
可重複的元素 , 無序的選取 , 對應 多重集的組合 ;
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
N=C(k+r−1,r)
2 . 不定方程非負整數解個數 :
x
1
+
x
2
+
⋯
+
x
k
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r
非負整數解個數為 :
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
N=C(k+r−1,r)
同時也是多重集的組合數 ;
3 . 非降路徑問題 :
基本模型 : 從
(
,
)
(0,0)
(0,0) 到
(
m
,
n
)
(m, n)
(m,n) 的非降路徑條數
(
m
+
n
m
)
\dbinom{m + n}{m}
(mm+n) ;
拓展模型 1 : 從
(
a
,
b
)
(a,b)
(a,b) 到
(
m
,
n
)
(m, n)
(m,n) 的非降路徑條數
(
m
−
a
+
n
−
b
m
−
a
)
\dbinom{m-a + n-b}{m-a}
(m−am−a+n−b) ;
拓展模型 2 : 從
(
a
,
b
)
(a,b)
(a,b) 經過
(
c
,
d
)
(c, d)
(c,d) 到
(
m
,
n
)
(m, n)
(m,n) 的非降路徑條數
(
c
−
a
+
c
−
b
c
−
a
)
(
m
−
c
+
n
−
d
m
−
c
)
\dbinom{c-a + c-b}{c-a}\dbinom{m-c + n-d}{m-c}
(c−ac−a+c−b)(m−cm−c+n−d)
限制條件的非降路徑數 : 從
(
,
)
(0,0)
(0,0) 到
(
n
,
n
)
(n,n)
(n,n) 除端點外 , 不接觸對角線的非降路徑數
參考 : 【組合數學】非降路徑問題 ( 限制條件的非降路徑數 )
二、常見的組合計數
常見的組合計數 :
I . 二項式系數
(
x
+
y
)
n
=
∑
k
=
n
(
n
k
)
x
k
y
n
−
k
(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}
(x+y)n=k=0∑n(kn)xkyn−k
(
n
k
)
\dbinom{n}{k}
(kn) 是二項式系數 ;
二項式系數相關組合恒等式 :
1 . 組合恒等式 ( 遞推式 ) :
( 1 ) 遞推式 1 :
(
n
k
)
=
(
n
n
−
k
)
\dbinom{n}{k} = \dbinom{n}{n-k}
(kn)=(n−kn) ①
( 2 ) 遞推式 2 :
(
n
k
)
=
n
k
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}
(kn)=kn(k−1n−1) ②
( 3 ) 遞推式 3 ( 帕斯卡 / 楊輝三角公式 ) :
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn)=(kn−1)+(k−1n−1) ③
2 . 回顧四個變下項求和的組合恒等式 : 之前介紹的組合恒等式 中的組合數
(
n
k
)
\dbinom{n}{k}
(kn) , 是下項
k
k
k 一直在累加改變 , 具有
∑
k
=
n
\sum\limits_{k=0}^{n}
k=0∑n 累加性質 , 上項
n
n
n 是不變的 ;
( 1 ) 簡單和 :
∑
k
=
n
(
n
k
)
=
2
n
\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n ④
( 2 ) 交錯和 :
∑
k
=
n
(
−
1
)
k
(
n
k
)
=
\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0
k=0∑n(−1)k(kn)=0 ⑤
( 3 ) 變下項求和 3 :
∑
k
=
n
k
(
n
k
)
=
n
2
n
−
1
\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}
k=0∑nk(kn)=n2n−1 ⑥
( 4 ) 變下項求和 4 :
∑
k
=
n
k
2
(
n
k
)
=
n
(
n
+
1
)
2
n
−
2
\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}
∑k=0nk2(kn)=n(n+1)2n−2 ⑦
3 . 變上項求和 :
∑
l
=
n
(
l
k
)
=
(
n
+
1
k
+
1
)
\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}
l=0∑n(kl)=(k+1n+1) ⑧
4 . 積 :
∑
l
=
n
(
l
k
)
=
(
n
+
1
k
+
1
)
\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}
l=0∑n(kl)=(k+1n+1) ⑨
5 . 積之和 :
( 1 ) 組合恒等式 ( 積之和 ) 1 :
∑
k
=
r
(
m
k
)
(
n
r
−
k
)
=
(
m
+
n
r
)
,
r
=
min
{
m
,
n
}
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}
k=0∑r(km)(r−kn)=(rm+n), r=min{m,n} ⑩
( 2 ) 組合恒等式 ( 積之和 ) 2 :
∑
k
=
r
(
m
k
)
(
n
k
)
=
(
m
+
n
m
)
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}
k=0∑r(km)(kn)=(mm+n) ⑪
II . 多項式系數
(
x
1
+
x
2
+
⋯
+
x
t
)
n
\ \ \ \ (x_1 + x_2 + \cdots + x_t)^n
(x1+x2+⋯+xt)n
=
∑
滿
足
n
1
+
n
2
+
⋯
+
n
t
=
n
非
負
整
數
解
個
數
(
n
n
1
n
2
⋯
n
t
)
x
1
n
1
x
2
n
2
⋯
x
t
n
t
= \sum\limits_{滿足 n_1 + n_2 + \cdots + n_t = n 非負整數解個數}\dbinom{n}{n_1 n_2 \cdots n_t}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}
=滿足n1+n2+⋯+nt=n非負整數解個數∑(n1n2⋯ntn)x1n1x2n2⋯xtnt
(
n
n
1
n
2
⋯
n
t
)
\dbinom{n}{n_1 n_2 \cdots n_t}
(n1n2⋯ntn) 是多項式系數
多項式系數相關組合恒等式 :
1 . 多項式定理推論 3 :
∑
(
n
n
1
n
2
⋯
n
t
)
=
t
n
\sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n
∑(n1n2⋯ntn)=tn
2 . 多重集全排列 :
(
n
n
1
n
2
⋯
n
t
)
=
n
!
n
1
!
n
2
!
⋯
n
k
!
\dbinom{n}{n_1 n_2 \cdots n_t} = \cfrac{n!}{n_1! n_2! \cdots n_k!}
(n1n2⋯ntn)=n1!n2!⋯nk!n!
3 . 遞推式 :
![1025.除數博弈[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)