IDEA激活码
文章目录
- 一、使用生成函数求解多重集 r 组合数
- 二、使用生成函数求解多重集 r 组合数 示例
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
一、使用生成函数求解多重集 r 组合数
S
=
{
n
1
⋅
a
1
,
n
2
⋅
a
2
,
⋯
,
n
k
⋅
a
k
}
S = \{ n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k \}
S={n1⋅a1,n2⋅a2,⋯,nk⋅ak} 是多重集 , 其含有
k
k
k 个种类的元素 ,
n
1
,
n
2
,
⋯
,
n
k
n_1, n_2, \cdots, n_k
n1,n2,⋯,nk 是每种元素的重复度 ,
该 多重集的
r
r
r 组合数 , 是 不定方程
x
1
+
x
2
+
⋯
+
x
k
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r 的非负整数解 , 前提是
x
i
≤
n
i
x_i \leq n_i
xi≤ni , 每个元素所取的个数
x
i
x_i
xi , 不能超过其重复度
n
i
n_i
ni ;
相当于
a
1
a_1
a1 取
x
1
x_1
x1 个 ,
a
2
a_2
a2 取
x
2
x_2
x2 个 ,
⋯
\cdots
⋯ ,
a
k
a_k
ak 取
x
k
x_k
xk 个 , 总共取
r
r
r 个 ;
n
i
n_i
ni 是无穷个数时 , 多重集的
r
r
r 组合数是
C
(
k
+
r
−
1
,
r
)
C(k + r - 1, r)
C(k+r−1,r)
回顾多重集排列组合 :
- 可重复的元素 , 有序的选取 , 对应 多重集的排列 ;
全
排
列
=
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)
上述的 多重集
r
r
r 组合数
C
(
k
+
r
−
1
,
r
)
C(k + r - 1, r)
C(k+r−1,r) 是在重复度不受限制的情况下的选取结果 , 如果重复度受限制 , 就需要使用生成函数进行计算 ;
如添加如下限制 :
a
1
a_1
a1 最多能取
3
3
3 个 ,
a
2
a_2
a2 最少取
4
4
4 个 , 最多取
10
10
10 个 ;
生成函数 :
G
(
y
)
=
G(y) =
G(y)=
(
1
+
y
+
⋯
+
y
n
1
)
(1 + y + \cdots + y^{n_1})
(1+y+⋯+yn1)
(
1
+
y
+
⋯
+
y
n
2
)
(1 + y + \cdots + y^{n_2})
(1+y+⋯+yn2)
⋯
\cdots
⋯
(
1
+
y
+
⋯
+
y
n
k
)
(1 + y + \cdots + y^{n_k})
(1+y+⋯+ynk)
多重集中的每个元素的取值个数作为
y
y
y 的次幂 , 如
a
1
a_1
a1 元素的取值个数是
0
0
0 到
n
1
n_1
n1 , 则该项对应的 生成函数项是 从
y
y
y 的
0
0
0 次幂 , 到
y
y
y 的
n
1
n_1
n1 次幂 相加 ; 构成项
(
1
+
y
+
⋯
+
y
n
1
)
(1 + y + \cdots + y^{n_1})
(1+y+⋯+yn1) ;
将所有元素的上述 生成函数项 乘到一起 , 就构成上述生成函数 ;
按照多项式乘法 , 多重集中取
r
r
r 个元素 ,
从第一个因式
(
1
+
y
+
⋯
+
y
n
1
)
(1 + y + \cdots + y^{n_1})
(1+y+⋯+yn1) 拿出
y
x
1
y^{x_1}
yx1 ,
从第二个因式
(
1
+
y
+
⋯
+
y
n
2
)
(1 + y + \cdots + y^{n_2})
(1+y+⋯+yn2) 拿出
y
x
2
y^{x_2}
yx2 ,
⋮
\vdots
⋮
从第
k
k
k 个因式
(
1
+
y
+
⋯
+
y
n
k
)
(1 + y + \cdots + y^{n_k})
(1+y+⋯+ynk) 拿出
y
x
k
y^{x_k}
yxk ,
如果上述乘积
y
x
1
y
x
2
⋯
y
x
k
y^{x_1}y^{x_2}\cdots y^{x_k}
yx1yx2⋯yxk 的结果 是
y
r
y^{r}
yr , 即
y
x
1
y
x
2
⋯
y
x
k
=
y
r
y^{x_1}y^{x_2}\cdots y^{x_k} = y^{r}
yx1yx2⋯yxk=yr , 相当于指数
x
1
+
x
2
+
⋯
+
x
k
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r , 也就是不定方程的非负整数解 ;
二、使用生成函数求解多重集 r 组合数 示例
多重集
S
=
{
3
⋅
a
,
4
⋅
b
,
5
⋅
c
}
S = \{3\cdot a , 4 \cdot b , 5 \cdot c \}
S={3⋅a,4⋅b,5⋅c} , 求该多重集的
10
10
10 组合数 ;
上述多重集元素的 重复度
3
,
4
,
5
3,4,5
3,4,5 都不超过
10
10
10 ;
对应
a
a
a 元素 , 其 重复度取值范围是
0
0
0 ~
3
3
3 , 对应的生成函数项是
y
0
+
y
1
+
y
2
+
y
3
y^0 +y^1 + y^2 + y^3
y0+y1+y2+y3
对应
b
b
b 元素 , 其 重复度取值范围是
0
0
0 ~
4
4
4 , 对应的生成函数项是
y
0
+
y
1
+
y
2
+
y
3
+
y
4
y^0 +y^1 + y^2 + y^3 + y^4
y0+y1+y2+y3+y4
对应
c
c
c 元素 , 其重 复度取值范围是
0
0
0 ~
5
5
5 , 对应的生成函数项是
y
0
+
y
1
+
y
2
+
y
3
+
y
4
+
y
5
y^0 +y^1 + y^2 + y^3 + y^4 + y^5
y0+y1+y2+y3+y4+y5
将上述项相乘 , 得到完整的生成函数 ;
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
)
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)
G(x)=(y0+y1+y2+y3)(y0+y1+y2+y3+y4)(y0+y1+y2+y3+y4+y5)
=
(
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 +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+y1+y2+y3)(1+y1+y2+y3+y4)(1+y1+y2+y3+y4+y5)
=
(
1
+
2
y
1
+
3
y
2
+
4
y
3
+
4
y
4
+
3
y
5
+
2
y
6
+
y
7
)
(
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)
=(1+2y1+3y2+4y3+4y4+3y5+2y6+y7)(1+y1+y2+y3+y4+y5)
统计上述两项相乘 ,
y
y
y 的次幂值为
10
10
10 的项 :
第一个因式的
3
y
5
3y^5
3y5 与第二个因式的
y
5
y^5
y5 , 相乘为
3
y
10
3y^{10}
3y10
第一个因式的
2
y
6
2y^6
2y6 与第二个因式的
y
4
y^4
y4 , 相乘为
2
y
10
2y^{10}
2y10
第一个因式的
y
7
y^7
y7 与第二个因式的
y
3
y^3
y3 , 相乘为
y
10
y^{10}
y10
y
10
y^{10}
y10 项前的系数是
3
+
2
+
1
=
6
3 + 2+1 = 6
3+2+1=6
因此上述 多重集的
10
10
10 组合 ,选择方案有
6
6
6 种 ;
