【组合数学】计数模型、常见组合数与组合恒等式 ★★

韩曙亮

发布于 2023-03-28 18:27:31

6420

发布于 2023-03-28 18:27:31

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、计数模型

当前涉及到的计数模型 :

1 . 选取问题 :

n

元集

S

, 从

S

集合中选取

r

个元素 ;

根据元素是否允许重复 , 选取过程是否有序 , 将选取问题分为四个子类型 :

	元素不重复	元素可以重复
有序选取	集合排列 P ( n , r ) P(n,r) P(n,r)	多重集排列
无序选取	集合组合 C ( n , r ) C(n,r) C(n,r)	多重集组合

P(n,r)

多重集排列无序选取集合组合

C(n,r)

多重集组合

选取问题中 :

不可重复的元素 , 有序的选取 , 对应 集合的排列 ;

P(n,r) = \dfrac{n!}{(n-r)!}

不可重复的元素 , 无序的选取 , 对应 集合的组合 ;

C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}

可重复的元素 , 有序的选取 , 对应 多重集的排列 ;

全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!}

, 非全排列

k^r , \ \ r\leq n_i

可重复的元素 , 无序的选取 , 对应 多重集的组合 ;

N= C(k + r - 1, r)

2 . 不定方程非负整数解个数 :

x_1 + x_2 + \cdots + x_k = r

非负整数解个数为 :

N= C(k + r - 1, r)

同时也是多重集的组合数 ;

3 . 非降路径问题 :

基本模型 : 从

(0,0)

到

(m, n)

的非降路径条数

\dbinom{m + n}{m}

;

拓展模型 1 : 从

(a,b)

到

(m, n)

的非降路径条数

\dbinom{m-a + n-b}{m-a}

;

拓展模型 2 : 从

(a,b)

经过

(c, d)

到

(m, n)

的非降路径条数

\dbinom{c-a + c-b}{c-a}\dbinom{m-c + n-d}{m-c}

限制条件的非降路径数 : 从

(0,0)

到

(n,n)

除端点外 , 不接触对角线的非降路径数

参考 : 【组合数学】非降路径问题 ( 限制条件的非降路径数 )

二、常见的组合计数

常见的组合计数 :

I . 二项式系数

(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}

\dbinom{n}{k}

是二项式系数 ;

二项式系数相关组合恒等式 :

1 . 组合恒等式 ( 递推式 ) :

( 1 ) 递推式 1 :

\dbinom{n}{k} = \dbinom{n}{n-k}

①

( 2 ) 递推式 2 :

\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}

②

( 3 ) 递推式 3 ( 帕斯卡 / 杨辉三角公式 ) :

\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}

③

2 . 回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式中的组合数

\dbinom{n}{k}

, 是下项

k

一直在累加改变 , 具有

\sum\limits_{k=0}^{n}

累加性质 , 上项

n

是不变的 ;

( 1 ) 简单和 :

\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n

④

( 2 ) 交错和 :

\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0

⑤

( 3 ) 变下项求和 3 :

\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}

⑥

( 4 ) 变下项求和 4 :

\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}

⑦

3 . 变上项求和 :

\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}

⑧

4 . 积 :

\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}

⑨

5 . 积之和 :

( 1 ) 组合恒等式 ( 积之和 ) 1 :

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}

⑩

( 2 ) 组合恒等式 ( 积之和 ) 2 :

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}

⑪

II . 多项式系数

\ \ \ \ (x_1 + x_2 + \cdots + x_t)^n

= \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}

\dbinom{n}{n_1 n_2 \cdots n_t}

是多项式系数

多项式系数相关组合恒等式 :

1 . 多项式定理推论 3 :

\sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n

2 . 多重集全排列 :

\dbinom{n}{n_1 n_2 \cdots n_t} = \cfrac{n!}{n_1! n_2! \cdots n_k!}

3 . 递推式 :

\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)}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除

集合

模型

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

集合

模型

数学

登录后参与评论

0 条评论

热度