【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )

2023-03-28 18:42:22 浏览数 (1)

文章目录

  • 一、重复有序拆分
  • 二、不重复有序拆分
  • ​
    • 1、无序拆分基本模型
    • 2、全排列
  • 三、重复有序拆分方案数证明

参考博客 : 按照顺序看

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

一、重复有序拆分

将 正整数

N

重复地 , 有序拆分 成

r

部分 , 方案数为

C(N-1, r-1)

★

( 三、中有该组合数由来证明 )

如果对 正整数

N

作 任意重复的有序拆分 , 即可以拆分成

1

个数 ,

2

个数 ,

cdots

,

N

个数 ,

拆分成

1

个数方案个数是

dbinom{N-1}{1-1}

拆分成

2

个数方案个数是

dbinom{N-1}{2-1}
vdots

拆分成

N

个数方案个数是

dbinom{N-1}{N-1}

上述总的方案个数是 :

sumlimits_{r=1}^{N}=2^{N-1}

( 根据基本组合恒等式计算出来 )

二、不重复有序拆分

先进行 不重复无序拆分 , 再进行 全排列 ;

1、无序拆分基本模型

无序拆分基本模型 :

将 正整数

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

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

对应的生成函数是 :

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

★ 重点看这里

如果 允许重复 , 那么这些

x_i

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

对应的生成函数是 :

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 )

或

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

2、全排列

n

的全排列是

n!
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 , rleq n_i
  • 可重复的元素 , 无序的选取 , 对应 多重集的组合 ;
N= C(k r - 1, r)

三、重复有序拆分方案数证明

使用一一对应的方法证明 : 将 正整数

N

重复地 , 有序拆分 成

r

部分 , 方案数为

C(N-1, r-1)

★

拆分后的正整数 , 如果交换了次序之后 , 排列不同 , 其所代表的方案数也不同 ;

将该拆分转换成组合计数问题 ;

假设

N=a_1 a_2 cdots a_r

是满足条件的拆分 , 该拆分 重复 , 有序 ;

将上述方案 , 做成部分序列 ,

拆分方案 与 拆分序列 :

根据拆分方案写出拆分序列 :

原始方案

6=1 2 3

, 由原始方案作部分序列 ,

第一个序列

S_1 = 1

, 取原始方案的第一个成分

1

出来 ,

第二个序列

S_2 = 1 2 = 3

, 取原始方案的前两个成分

1 2

出来 ,

第三个序列

S_3 = 1 2 3 = 6

, 取原始方案的前三个成分

1 2 3

出来 ,

第一个序列是第一个数 , 第二个序列是前两个数 , 第

n

个序列是前

n

个数 , 最后一个序列包含了所有的拆分的正整数 ;

只要给定一个原始方案 , 就可以作出上述部分序列出来 ;

只要方案相同 , 作出的序列完全相同 , 方案不同 , 作出的序列肯定不相同 ;

根据拆分序列写出拆分方案 :

反之 , 给定一个序列 , 可以 还原出一个拆分方案来 , 如给出序列

S_1 = 1 , S_2=3, S_3=6

, 对应的拆分方案 :

最后一个序列式所有数之和 , 被拆分的正整数就是最后一个序列的数值

6

第一个正整数 就是第一个序列

1

第二个正整数 是第二序列减去第一序列

S_2 - S_1 = 3-1=2

第三个正整数 是第三序列减去第二序列

S_3-S_2=6-3=3

拆分方案是

6 = 1 2 3
N=a_1 a_2 cdots a_r

的拆分序列是

S_1 = a_1
S_2= a_1 a_2
S_3= a_1 a_2 a_3
vdots
S_i= a_1 a_2 a_3 cdots a_i = sumlimits_{k=1}^ta_i , i=1,2,3, cdots

上述的拆分序列一定有下面的性质 :

0 < S_1 < S_2 < cdots < S_r = N

因为

S_2

肯定是

S_1

加上一个正整数 ,

S_r

肯定是

S_{r-1}

加上一个正整数 , 最后一项是所有的

r

个正整数之和 , 是被拆分的正整数

N

;

上述拆分序列

S_1, S_2, cdots , S_r

, 最后一个数

S_r = N

,

最后一个数不管 , 前面的

r-1

个数的取值范围是

1, 2, 3, cdots , N-1

, 上述取值范围内 有

n-1

个正整数 ;

从

n-1

个正整数中 , 选取

r-1

个正整数 ,

因此, 将 正整数

N

重复地 , 有序拆分 成

r

部分 , 方案数为

C(N-1, r-1)

★

博客 函数 集合 模型 数学

0 人点赞