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

文章目录

一、计数模型
二、常见的组合计数

一、计数模型

当前涉及到的计数模型 :

1 . 选取问题 :

元集

, 从

集合中选取

个元素 ;

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

	元素不重复	元素可以重复
有序选取	集合排列 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 , rleq 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}

, 是下项

一直在累加改变 , 具有

sumlimits_{k=0}^{n}

累加性质 , 上项

是不变的 ;

( 1 ) 简单和 :

sumlimits_{k=0}^{n}dbinom{n}{k} = 2^n

④

( 2 ) 交错和 :

sumlimits_{k=0}^{n} (-1)^k dbinom{n}{k} = 0

⑤

( 3 ) 变下项求和 3 :

sumlimits_{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 . 变上项求和 :

sumlimits_{l=0}^{n} dbinom{l}{k} = dbinom{n 1}{k 1}

⑧

4 . 积 :

sumlimits_{l=0}^{n} dbinom{l}{k} = dbinom{n 1}{k 1}

⑨

5 . 积之和 :

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

sumlimits_{k=0}^{r}dbinom{m}{k}dbinom{n}{r-k} = dbinom{m n }{r} , r= min { m, n }

⑩

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

sumlimits_{k=0}^{r}dbinom{m}{k}dbinom{n}{k} = dbinom{m n }{m}

⑪

II . 多项式系数

(x_1 x_2 cdots x_t)^n

= sumlimits_{满足 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 :

sumdbinom{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)}

集合模型数学

0 人点赞