【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )

2023-03-28 18:41:33 浏览数 (1)

文章目录

  • 一、正整数拆分
  • 二、无序拆分
  • ​
    • 1、无序拆分 不允许重复
    • 2、无序拆分 允许重复

参考博客 :

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

一、正整数拆分

正整数拆分 涉及内容 :

  • 拆分定义与分类
  • 无序拆分
  • 有序拆分

一个正整数可以 拆分成若干正整数 的和 , 每种不同的拆分方法 , 就可以 看做一个方案 ;

按照拆分顺序进行分类 :

4

拆分成

1

和

3

,

4

拆分成

3

和

1

;

  • 有序拆分 : 上述
2

个 正整数拆分 , 是 两种不同的拆分方法 ;

  • 无序拆分 : 上述
2

个 正整数拆分 , 是 同一种拆分方法 ;

按照是否重复进行分类 :

  • 允许重复 : 拆分时 , 允许拆分成若干个重复的正整数 , 如
3

拆分成

3

个

1

;

  • 不允许重复 : 拆分时 , 拆分的正整数 不允许重复 , 如
3

拆分成

3

个

1

是错误的 , 只能拆分成

1,2

;

正整数拆分可以按照性质 , 分为

4

类 ;

  • 有序重复
  • 有序不重复
  • 无序重复
  • 无序不重复

二、无序拆分

无序拆分基本模型 :

将 正整数

N

无序拆分成正整数 ,

a_1, a_2, cdots , a_n

是拆分后的

n

个数 ,

该拆分是无序的 , 上述拆分的

n

个数的个数可能是不一样的 ,

假设

a_1

有

x_1

个 ,

a_2

有

x_2

个 ,

cdots

,

a_n

有

x_n

个 , 那么有如下方程 :

a_1x_1 a_2x_2 cdots a_nx_n = N

这种形式可以使用 不定方程非负整数解个数 的生成函数计算 , 是 带系数 , 带限制条件的情况 , 参考 : 组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

无序拆分的情况下 , 拆分后的正整数 , 允许重复 和 不允许重复 , 是两类组合问题 ;

如果不允许重复 , 那么这些

x_i

的取值 , 只能 取值

0, 1

; 相当于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

如果 允许重复 , 那么这些

x_i

的取值 , 就是 自然数 ; 相当于 带系数 的 不定方程非负整数解 的情况 ;

1、无序拆分 不允许重复

讨论 无序拆分 , 不允许重复的情况 , 该方式 等价于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

a_1

项对应的生成函数项 ,

x_1

取值

0,1

, 则对应的生成函数项是

(y^{a_1})^{0} (y^{a_1})^{1}= 1 y^{a_1}
a_2

项对应的生成函数项 ,

x_2

取值

0,1

, 则对应的生成函数项是

(y^{a_2})^{0} (y^{a_2})^{1}= 1 y^{a_2}
vdots
a_n

项对应的生成函数项 ,

x_n

取值

0,1

, 则对应的生成函数项是

(y^{a_n})^{0} (y^{a_n})^{1}= 1 y^{a_n}

将上述生成函数项相乘 , 则可得到完整生成函数 :

G(x) = (1 y^{a_1}) (1 y^{a_2}) cdots (1 y^{a_n})

将上述生成函数写好之后 , 计算 展开 ,

y

的

N

次幂的系数 , 就是 正整数

N

的拆分方案数 ;

2、无序拆分 允许重复

讨论 无序拆分 , 允许重复的情况 , 该方式 等价于 不带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

a_1

项对应的生成函数项 ,

x_1

取值

0,1, cdots

, 则对应的生成函数项是

(y^{a_1})^{0} (y^{a_1})^{1} (y^{a_1})^{2}= 1 y^{a_1} y^{2a_1}cdots
a_2

项对应的生成函数项 ,

x_2

取值

0,1, cdots

, 则对应的生成函数项是

(y^{a_2})^{0} (y^{a_2})^{1} (y^{a_2})^{2}= 1 y^{a_2} y^{2a_2}cdots
vdots
a_n

项对应的生成函数项 ,

x_n

取值

0,1, cdots

, 则对应的生成函数项是

(y^{a_n})^{0} (y^{a_n})^{1} (y^{a_n})^{2}= 1 y^{a_n} y^{2a_n}cdots

将上述生成函数项相乘 , 则可得到完整生成函数 :

G(x) = (1 y^{a_1} y^{2a_1}cdots) (1 y^{a_2} y^{2a_2}cdots) cdots (1 y^{a_n} y^{2a_n}cdots )

上述生成函数可以根据 如下生成函数的常用取值 :

{a_n}

,

a_n = 1^n

;

begin{aligned} A(x) & = sum_{n=0}^{infty} x^n = frac{1}{1-x} end{aligned}

将

1 y^{a_1} y^{2a_1}cdots

中的

y^{a_1}

换元成

x

, 则可得到

1 x x^2 x^3 cdots

对应的数列是

1^n

则上述

1 y^{a_1} y^{2a_1}cdots =cfrac{1}{1-y^{a_1}}

最终化简结果 :

G(x) = (1 y^{a_1} y^{2a_1}cdots) (1 y^{a_2} y^{2a_2}cdots) cdots (1 y^{a_n} y^{2a_n}cdots )
=cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) cdots (1-y^{a_n}) }

将上述生成函数写好之后 , 计算 展开 ,

y

的

N

次幂的系数 , 就是 正整数

N

的拆分方案数 ;

博客 函数 模型 数学

0 人点赞