IDEA激活码
文章目录
- 一、指数生成函数求解多重集排列示例
参考博客 : 按照顺序看
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
- 【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )
- 【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )
- 【组合数学】指数生成函数 ( 指数生成函数性质 | 指数生成函数求解多重集排列 )
一、指数生成函数求解多重集排列示例
使用
1
,
2
,
3
,
4
1,2,3,4
1,2,3,4 四个数字组成五位数 , 要求
1
1
1 出现次数不能超过
2
2
2 次 , 但必须出现 ,
2
2
2 出现次数不超过
1
1
1 次 ,
3
3
3 出现次数最多
3
3
3 次 ,
4
4
4 出现偶数次 ,
求上述五位数的个数 ;
这就是一个求解 多重集排列 的题目 , 使用 指数生成函数 ;
一共有
5
5
5 个位置 , 使用
1
,
2
,
3
,
4
1,2,3,4
1,2,3,4 向这
5
5
5 个位置中填充 ,
选取个数分析 :
1
1
1 出现不超过
2
2
2 次 , 不能不出现 , 也就是必须大于
0
0
0 , 则可选取的个数是
1
,
2
1,2
1,2 ,
2
2
2 出现不超过
1
1
1 次 , 可选取个数
0
,
1
0,1
0,1 ,
3
3
3 出现可以达到
3
3
3 次 , 可选取的个数
0
,
1
,
2
,
3
0,1,2,3
0,1,2,3 ,
4
4
4 出现偶数次 , 可选取个数是
0
,
2
,
4
,
6
,
8
,
⋯
0, 2, 4, 6, 8, \cdots
0,2,4,6,8,⋯ , 这里注意一共选择
5
5
5 个 , 最终求解多重集时 , 主要是看
x
5
x^5
x5 前的次幂数 , 因此这里的 可选取个数就是单个因式中的
x
x
x 次幂数 , 没必要超过
5
5
5 , 选择
0
,
2
,
4
0,2,4
0,2,4 即可 ;
按照下面的模型 , 写出指数生成函数 ;
多重集
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}
多重集
S
S
S 的
r
r
r 排列数 组成数列
{
a
r
}
\{ a_r \}
{ar} , 对应的指数生成函数是 :
G
e
(
x
)
=
f
n
1
(
x
)
f
n
2
(
x
)
⋯
f
n
k
(
x
)
G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)
Ge(x)=fn1(x)fn2(x)⋯fnk(x) ★
其中每个生成函数项
f
n
i
(
x
)
f_{n_i}(x)
fni(x) 是
f
n
i
(
x
)
=
1
+
x
+
x
2
2
!
+
⋯
+
x
n
i
n
i
!
f_{n_i}(x) = 1 + x + \cfrac{x^2}{2!} + \cdots + \cfrac{x^{n_i}}{n_i!}
fni(x)=1+x+2!x2+⋯+ni!xni ★
将
G
e
(
x
)
G_e(x)
Ge(x) 展开 , 其中的
r
r
r 系数就是多重集的排列数 ; ★
指数生成函数写法 :
① 确定生成函数项个数 : 多重集元素种类个数
② 确定生成函数项中的分项个数 : 选取值 个数 ;
③ 分项格式 :
x
n
n
!
\cfrac{x^n}{n!}
n!xn
④ 分项次幂 : 选取值 ;
总共有
4
4
4 种元素
1
,
2
,
3
,
4
1,2,3,4
1,2,3,4 , 因此生成函数是
4
4
4 个生成函数项相乘 ;
1
1
1 元素对应的生成函数项 :
- 选取值 :
1
,
2
1,2
1,2 - 最终结果 :
x
1
1
!
+
x
2
2
!
=
x
+
x
2
2
!
\cfrac{x^1}{1!} + \cfrac{x^2}{2!} = x + \cfrac{x^2}{2!}
1!x1+2!x2=x+2!x2
2
2
2 元素对应的生成函数项 :
- 选取值 :
0
,
1
0,1
0,1 - 最终结果 :
x
0
0
!
+
x
1
1
!
=
1
+
x
\cfrac{x^0}{0!} + \cfrac{x^1}{1!} = 1 + x
0!x0+1!x1=1+x
3
3
3 元素对应的生成函数项 :
- 选取值 :
0
,
1
,
2
,
3
0,1,2,3
0,1,2,3 - 最终结果 :
x
0
0
!
+
x
1
1
!
+
x
2
2
!
+
x
3
3
!
=
1
+
x
+
x
2
2
!
+
x
3
3
!
\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} = 1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!}
0!x0+1!x1+2!x2+3!x3=1+x+2!x2+3!x3
4
4
4 元素对应的生成函数项 :
- 选取值 :
0
,
2
,
4
,
6
,
⋯
0,2,4,6 , \cdots
0,2,4,6,⋯ , 这里只选取5
5
5 个 , 求x
x
x 的次幂的5
5
5 前的系数 , 这里只需要选取到0
,
2
,
4
0 , 2, 4
0,2,4 即可 ,5
5
5 以上的数完全不需要 , 可以忽略 ; - 最终结果 :
x
0
0
!
+
x
2
2
!
+
x
4
4
!
=
1
+
x
2
2
!
+
x
4
4
!
\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} = 1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!}
0!x0+2!x2+4!x4=1+2!x2+4!x4
将上述指数生成函数中四个 指数生成函数项相乘 , 计算出
x
5
x^5
x5 前的系数 , 就是多重集的排列数 ;
G
e
(
x
)
=
(
x
+
x
2
2
!
)
(
1
+
x
)
(
1
+
x
+
x
2
2
!
+
x
3
3
!
)
(
1
+
x
2
2
!
+
x
4
4
!
)
G_e(x) = (x + \cfrac{x^2}{2!}) (1 + x) (1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!}) (1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!})
Ge(x)=(x+2!x2)(1+x)(1+x+2!x2+3!x3)(1+2!x2+4!x4)
=
x
+
5
x
2
2
!
+
18
x
3
3
!
+
64
x
4
4
!
+
215
x
5
5
!
⋯
\ \ \ \ \ \ \ \ \ \ \ \,= x + 5\cfrac{x^2}{2!} + 18\cfrac{x^3}{3!} + 64\cfrac{x^4}{4!} + 215\cfrac{x^5}{5!} \cdots
=x+52!x2+183!x3+644!x4+2155!x5⋯
后面的就不算了 , 其中
x
5
x^5
x5 的项是
215
x
5
5
!
215\cfrac{x^5}{5!}
2155!x5 , 因此题目中要求的
5
5
5 位数的个数是
215
215
215 个 ;
