【组合数学】计数模型、常见组合数与组合恒等式 ★★
一、计数模型
当前涉及到的计数模型 :
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)
文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。
原文链接：hanshuliang.blog.csdn.net/article/details/109206929
- 点赞
- 收藏
- 关注作者
评论（0）