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

2023-03-28 18:40:20 浏览数 (1)

文章目录

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

参考博客 :

  • 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
  • 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
  • 【组合数学】生成函数 ( 移位性质 )
  • 【组合数学】生成函数 ( 求和性质 )
  • 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
  • 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
  • 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
  • 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )

一、使用生成函数求解多重集 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 , rleq 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 = {3cdot 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}
y^{10}

项前的系数是

3 2 1 = 6

因此上述 多重集的

10

组合 ,选择方案有

6

种 ;

博客 函数 数学 统计

0 人点赞