【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )

韩曙亮

发布于 2023-03-28 18:40:20

1K0

发布于 2023-03-28 18:40:20

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

文章目录

参考博客 :

一、使用生成函数求解多重集 r 组合数

S = \{ n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k \}

是多重集 , 其含有

k

个种类的元素 ,

n_1, n_2, \cdots, n_k

是每种元素的重复度 ,

该多重集的

r

组合数 , 是不定方程

x_1 + x_2 + \cdots + x_k = r

的非负整数解 , 前提是

x_i \leq n_i

, 每个元素所取的个数

x_i

, 不能超过其重复度

n_i

;

相当于

a_1

取

x_1

个 ,

a_2

取

x_2

个 ,

\cdots

,

a_k

取

x_k

个 , 总共取

r

个 ;

n_i

是无穷个数时 , 多重集的

r

组合数是

C(k + r - 1, r)

回顾多重集排列组合 :

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

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

, 非全排列

k^r , \ \ r\leq n_i

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

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

上述的多重集

r

组合数

C(k + r - 1, r)

是在重复度不受限制的情况下的选取结果 , 如果重复度受限制 , 就需要使用生成函数进行计算 ;

如添加如下限制 :

a_1

最多能取

3

个 ,

a_2

最少取

4

个 , 最多取

10

个 ;

生成函数 :

G(y) =

(1 + y + \cdots + y^{n_1})

(1 + y + \cdots + y^{n_2})

\cdots

(1 + y + \cdots + y^{n_k})

多重集中的每个元素的取值个数作为

y

的次幂 , 如

a_1

元素的取值个数是

0

到

n_1

, 则该项对应的生成函数项是从

y

的

0

次幂 , 到

y

的

n_1

次幂相加 ; 构成项

(1 + y + \cdots + y^{n_1})

;

将所有元素的上述生成函数项乘到一起 , 就构成上述生成函数 ;

按照多项式乘法 , 多重集中取

r

个元素 ,

从第一个因式

(1 + y + \cdots + y^{n_1})

拿出

y^{x_1}

,

从第二个因式

(1 + y + \cdots + y^{n_2})

拿出

y^{x_2}

,

\vdots

从第

k

个因式

(1 + y + \cdots + y^{n_k})

拿出

y^{x_k}

,

如果上述乘积

y^{x_1}y^{x_2}\cdots y^{x_k}

的结果是

y^{r}

, 即

y^{x_1}y^{x_2}\cdots y^{x_k} = y^{r}

, 相当于指数

x_1 + x_2 + \cdots + x_k = r

, 也就是不定方程的非负整数解 ;

二、使用生成函数求解多重集 r 组合数示例

多重集

S = \{3\cdot a , 4 \cdot b , 5 \cdot c \}

, 求该多重集的

10

组合数 ;

上述多重集元素的重复度

3,4,5

都不超过

10

;

对应

a

元素 , 其重复度取值范围是

0

~

3

, 对应的生成函数项是

y^0 +y^1 + y^2 + y^3

对应

b

元素 , 其重复度取值范围是

0

~

4

, 对应的生成函数项是

y^0 +y^1 + y^2 + y^3 + y^4

对应

c

元素 , 其重复度取值范围是

0

~

5

, 对应的生成函数项是

y^0 +y^1 + y^2 + y^3 + y^4 + y^5

将上述项相乘 , 得到完整的生成函数 ;

G(x) = (y^0 +y^1 + y^2 + y^3)(y^0 +y^1 + y^2 + y^3 + y^4)(y^0 +y^1 + y^2 + y^3 + y^4 + y^5)

\ \ \ \ \ \ \ \ \ \ =(1 +y^1 + y^2 + y^3)(1 +y^1 + y^2 + y^3 + y^4)(1 +y^1 + y^2 + y^3 + y^4 + y^5)

\ \ \ \ \ \ \ \ \ \ =(1 +2y^1 + 3y^2 + 4y^3 + 4y^4 + 3y^5 + 2y^6 + y^7 )(1 +y^1 + y^2 + y^3 + y^4 + y^5)

统计上述两项相乘 ,

y

的次幂值为

10

的项 :

第一个因式的

3y^5

与第二个因式的

y^5

, 相乘为

3y^{10}

第一个因式的

2y^6

与第二个因式的

y^4

, 相乘为

2y^{10}

第一个因式的

y^7

与第二个因式的

y^3

, 相乘为

y^{10}

项前的系数是

3 + 2+1 = 6

因此上述多重集的

10

组合 ,选择方案有

6

种 ;

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

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

博客

函数

数学

统计

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

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

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

登录后参与评论

0 条评论

热度