IDEA激活码
文章目录
- 一、计数模型
- 二、常见的组合计数
一、计数模型
当前涉及到的计数模型 :
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)
(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)
(0,0) 到
(
n
,
n
)
(n,n)
(n,n) 除端点外 , 不接触对角线的非降路径数
参考 : 【组合数学】非降路径问题 ( 限制条件的非降路径数 )
二、常见的组合计数
常见的组合计数 :
I . 二项式系数
(
x
+
y
)
n
=
∑
k
=
0
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
=
0
n
\sum\limits_{k=0}^{n}
k=0∑n 累加性质 , 上项
n
n
n 是不变的 ;
( 1 ) 简单和 :
∑
k
=
0
n
(
n
k
)
=
2
n
\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n ④
( 2 ) 交错和 :
∑
k
=
0
n
(
−
1
)
k
(
n
k
)
=
0
\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0
k=0∑n(−1)k(kn)=0 ⑤
( 3 ) 变下项求和 3 :
∑
k
=
0
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
=
0
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
=
0
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
=
0
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
=
0
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
=
0
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 . 递推式 :
(
n
n
1
n
2
⋯
n
t
)
=
(
n
−
1
(
n
1
−
1
)
n
2
⋯
n
t
)
+
(
n
−
1
n
1
(
n
2
−
1
)
⋯
n
t
)
+
(
n
−
1
n
1
n
2
⋯
(
n
t
−
1
)
)
\dbinom{n}{n_1 n_2 \cdots n_t} = \dbinom{n-1}{(n_1-1) n_2 \cdots n_t} + \dbinom{n-1}{n_1 (n_2 - 1) \cdots n_t}+ \dbinom{n-1}{n_1 n_2 \cdots (n_t -1)}
(n1n2⋯ntn)=((n1−1)n2⋯ntn−1)+(n1(n2−1)⋯ntn−1)+(n1n2⋯(nt−1)n−1)
