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

参考博客 : 按照顺序看

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

一、重复有序拆分

将 正整数 N N N 重复地 , 有序拆分 成 r r r 部分 , 方案数为 C ( N − 1 , r − 1 ) C(N-1, r-1) C(N−1,r−1) ★

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

如果对 正整数 N N N 作 任意重复的有序拆分 , 即可以拆分成 1 1 1 个数 , 2 2 2 个数 , ⋯ \cdots ⋯ , N N N 个数 ,

拆分成 1 1 1 个数方案个数是 ( N − 1 1 − 1 ) \dbinom{N-1}{1-1} (1−1N−1​)

拆分成 2 2 2 个数方案个数是 ( N − 1 2 − 1 ) \dbinom{N-1}{2-1} (2−1N−1​)

⋮ \vdots ⋮

拆分成 N N N 个数方案个数是 ( N − 1 N − 1 ) \dbinom{N-1}{N-1} (N−1N−1​)

上述总的方案个数是 : ∑ r = 1 N = 2 N − 1 \sum\limits_{r=1}^{N}=2^{N-1} r=1∑N​=2N−1

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

二、不重复有序拆分

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

1、无序拆分基本模型

无序拆分基本模型 :

将 正整数 N N N 无序拆分成正整数 , a 1 , a 2 , ⋯   , a n a_1, a_2, \cdots , a_n a1​,a2​,⋯,an​ 是拆分后的 n n n 个数 ,

该拆分是无序的 , 上述拆分的 n n n 个数的个数可能是不一样的 ,

假设 a 1 a_1 a1​ 有 x 1 x_1 x1​ 个 , a 2 a_2 a2​ 有 x 2 x_2 x2​ 个 , ⋯ \cdots ⋯ , a n a_n an​ 有 x n x_n xn​ 个 , 那么有如下方程 :

a 1 x 1 + a 2 x 2 + ⋯ + a n x n = N a_1x_1 + a_2x_2 + \cdots + a_nx_n = N a1​x1​+a2​x2​+⋯+an​xn​=N

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

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

如果不允许重复 , 那么这些 x i x_i xi​ 的取值 , 只能 取值 0 , 1 0, 1 0,1 ; 相当于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

对应的生成函数是 : G ( x ) = ( 1 + y a 1 ) ( 1 + y a 2 ) ⋯ ( 1 + y a n ) G(x) = (1+ y^{a_1}) (1+ y^{a_2}) \cdots (1+ y^{a_n}) G(x)=(1+ya1​)(1+ya2​)⋯(1+yan​) ★ 重点看这里

如果 允许重复 , 那么这些 x i x_i xi​ 的取值 , 就是 自然数 ; 相当于 带系数 的 不定方程非负整数解 的情况 ;

对应的生成函数是 : G ( x ) = ( 1 + y a 1 + y 2 a 1 ⋯   ) ( 1 + y a 2 + y 2 a 2 ⋯   ) ⋯ ( 1 + y a n + y 2 a n ⋯   ) 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)=(1+ya1​+y2a1​⋯)(1+ya2​+y2a2​⋯)⋯(1+yan​+y2an​⋯)

或 G ( x ) = 1 ( 1 − y a 1 ) ( 1 − y a 2 ) ⋯ ( 1 − y a n ) G(x) =\cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) \cdots (1-y^{a_n}) } G(x)=(1−ya1​)(1−ya2​)⋯(1−yan​)1​

2、全排列

n n n 的全排列是 n ! n! n!

n n n 元集 S S S , 从 S S S 集合中选取 r r r 个元素 ;

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

元素不重复元素可以重复有序选取集合排列 P ( n , r ) P(n,r) P(n,r)多重集排列无序选取集合组合 C ( n , r ) C(n,r) C(n,r)多重集组合

选取问题中 :

• 不可重复的元素 , 有序的选取 , 对应 集合的排列 ; P ( n , r ) = n ! ( n − r ) ! P(n,r) = \dfrac{n!}{(n-r)!} P(n,r)=(n−r)!n!​
• 不可重复的元素 , 无序的选取 , 对应 集合的组合 ; C ( n , r ) = P ( n , r ) r ! = n ! r ! ( n − r ) ! C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!} C(n,r)=r!P(n,r)​=r!(n−r)!n!​
• 可重复的元素 , 有序的选取 , 对应 多重集的排列 ; 全 排 列 = n ! n 1 ! n 2 ! ⋯ n k ! 全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!} 全排列=n1​!n2​!⋯nk​!n!​ , 非全排列 k r ,    r ≤ n i k^r , \ \ r\leq n_i kr,  r≤ni​
• 可重复的元素 , 无序的选取 , 对应 多重集的组合 ; N = C ( k + r − 1 , r ) N= C(k + r - 1, r) N=C(k+r−1,r)

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

使用一一对应的方法证明 : 将 正整数 N N N 重复地 , 有序拆分 成 r r r 部分 , 方案数为 C ( N − 1 , r − 1 ) C(N-1, r-1) C(N−1,r−1) ★

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

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

假设 N = a 1 + a 2 + ⋯ + a r N=a_1 + a_2 + \cdots + a_r N=a1​+a2​+⋯+ar​ 是满足条件的拆分 , 该拆分 重复 , 有序 ;

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

拆分方案 与 拆分序列 :

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

原始方案 6 = 1 + 2 + 3 6=1+2+3 6=1+2+3 , 由原始方案作部分序列 ,

第一个序列 S 1 = 1 S_1 = 1 S1​=1 , 取原始方案的第一个成分 1 1 1 出来 ,

第二个序列 S 2 = 1 + 2 = 3 S_2 = 1 + 2 = 3 S2​=1+2=3 , 取原始方案的前两个成分 1 + 2 1 + 2 1+2 出来 ,

第三个序列 S 3 = 1 + 2 + 3 = 6 S_3 = 1 + 2 + 3 = 6 S3​=1+2+3=6 , 取原始方案的前三个成分 1 + 2 + 3 1 + 2 + 3 1+2+3 出来 ,

第一个序列是第一个数 , 第二个序列是前两个数 , 第 n n n 个序列是前 n n n 个数 , 最后一个序列包含了所有的拆分的正整数 ;

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

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

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

反之 , 给定一个序列 , 可以 还原出一个拆分方案来 , 如给出序列 S 1 = 1 , S 2 = 3 , S 3 = 6 S_1 = 1 , S_2=3, S_3=6 S1​=1,S2​=3,S3​=6 , 对应的拆分方案 :

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

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

第二个正整数 是第二序列减去第一序列 S 2 − S 1 = 3 − 1 = 2 S_2 - S_1 = 3-1=2 S2​−S1​=3−1=2

第三个正整数 是第三序列减去第二序列 S 3 − S 2 = 6 − 3 = 3 S_3-S_2=6-3=3 S3​−S2​=6−3=3

拆分方案是 6 = 1 + 2 + 3 6 = 1+2+3 6=1+2+3

N = a 1 + a 2 + ⋯ + a r N=a_1 + a_2 + \cdots + a_r N=a1​+a2​+⋯+ar​ 的拆分序列是

S 1 = a 1 S_1 = a_1 S1​=a1​

S 2 = a 1 + a 2 S_2= a_1 + a_2 S2​=a1​+a2​

S 3 = a 1 + a 2 + a 3 S_3= a_1 + a_2 + a_3 S3​=a1​+a2​+a3​

⋮ \vdots ⋮

S i = a 1 + a 2 + a 3 + ⋯ + a i = ∑ k = 1 t a i   ,       i = 1 , 2 , 3 , ⋯ S_i= a_1 + a_2 + a_3 + \cdots + a_i = \sum\limits_{k=1}^ta_i\ , \ \ \ \ \ i=1,2,3, \cdots Si​=a1​+a2​+a3​+⋯+ai​=k=1∑t​ai​ ,     i=1,2,3,⋯

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

0 < S 1 < S 2 < ⋯ < S r = N 0 < S_1 < S_2 < \cdots < S_r = N 0