IDEA激活码
文章目录
- 一、指数生成函数求解多重集排列示例 2
参考博客 : 按照顺序看
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
- 【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )
- 【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )
- 【组合数学】指数生成函数 ( 指数生成函数性质 | 指数生成函数求解多重集排列 )
- 【组合数学】指数生成函数 ( 指数生成函数求解多重集排列示例 )
一、指数生成函数求解多重集排列示例 2
使用 白色 红色 蓝色 涂色
n
n
n 个格子 , 白色的涂色个数是偶数 , 求涂色方案个数
这是一个 排列问题 , 当不同的方格涂色交换之后 , 就变成了不同的方案 ,
红色 , 蓝色 涂色 , 没有限制 , 涂色个数可以是
0
,
1
,
2
,
3
,
4
,
⋯
0, 1,2,3,4,\cdots
0,1,2,3,4,⋯
白色 涂色 , 涂色个数是偶数个 , 涂色个数是
0
,
2
,
4
,
6
,
8
,
⋯
0, 2, 4, 6, 8 , \cdots
0,2,4,6,8,⋯
红色 , 蓝色 涂色个数
0
,
1
,
2
,
3
,
4
,
⋯
0, 1,2,3,4,\cdots
0,1,2,3,4,⋯ 序列 , 对应的生成函数项为 :
x
0
0
!
+
x
1
1
!
+
x
2
2
!
⋯
=
1
+
x
+
x
2
2
!
+
⋯
\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} \cdots = 1 + x + \cfrac{x^2}{2!} + \cdots
0!x0+1!x1+2!x2⋯=1+x+2!x2+⋯
白色 涂色个数
0
,
2
,
4
,
6
,
8
,
⋯
0, 2, 4, 6, 8 , \cdots
0,2,4,6,8,⋯ 序列 , 对应的生成函数项为 :
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!} \cdots = 1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots
0!x0+2!x2+4!x4⋯=1+2!x2+4!x4+⋯
上述涂色方案个数的指数生成函数是 :
G
e
(
x
)
=
(
1
+
x
+
x
2
2
!
+
⋯
)
(
1
+
x
+
x
2
2
!
+
⋯
)
(
1
+
x
2
2
!
+
x
4
4
!
+
⋯
)
G_e(x) = (1 + x + \cfrac{x^2}{2!} + \cdots) (1 + x + \cfrac{x^2}{2!} + \cdots) (1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots)
Ge(x)=(1+x+2!x2+⋯)(1+x+2!x2+⋯)(1+2!x2+4!x4+⋯)
其中
1
+
x
+
x
2
2
!
+
⋯
1 + x + \cfrac{x^2}{2!} + \cdots
1+x+2!x2+⋯ 可以 写成
e
x
e^x
ex 形式 ;
其中
1
+
x
2
2
!
+
x
4
4
!
+
⋯
1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots
1+2!x2+4!x4+⋯ 可以写成如下形式 :
1
+
x
2
2
!
+
x
4
4
!
+
⋯
=
1
2
(
e
x
+
e
−
x
)
1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots = \cfrac{1}{2}(e^x + e^{-x})
1+2!x2+4!x4+⋯=21(ex+e−x)
e
x
+
e
−
x
e^x + e^{-x}
ex+e−x 相加 , 奇次幂符号相反 , 直接约掉 , 偶数次幂 变为原来的两倍, 因此在外面乘以
1
2
\cfrac{1}{2}
21 ;
将上述
e
x
e^x
ex 和
1
2
(
e
x
+
e
−
x
)
\cfrac{1}{2}(e^x + e^{-x})
21(ex+e−x) 替换到 指数生成函数中 ;
G
e
(
x
)
=
(
1
+
x
+
x
2
2
!
+
⋯
)
(
1
+
x
+
x
2
2
!
+
⋯
)
(
1
+
x
2
2
!
+
x
4
4
!
+
⋯
)
G_e(x) = (1 + x + \cfrac{x^2}{2!} + \cdots) (1 + x + \cfrac{x^2}{2!} + \cdots) (1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots)
Ge(x)=(1+x+2!x2+⋯)(1+x+2!x2+⋯)(1+2!x2+4!x4+⋯)
=
1
2
(
e
x
+
e
−
x
)
(
e
x
)
(
e
x
)
\ \ \ \ \ \ \ \ \ \ \ \, =\cfrac{1}{2}(e^x + e^{-x})(e^x )(e^x)
=21(ex+e−x)(ex)(ex)
=
1
2
e
3
x
+
1
2
e
x
\ \ \ \ \ \ \ \ \ \ \ \, =\cfrac{1}{2}e^{3x} + \cfrac{1}{2}e^{x}
=21e3x+21ex
将
1
2
e
x
\cfrac{1}{2}e^{x}
21ex 展开后为
1
2
(
1
+
x
+
x
2
2
!
+
⋯
)
=
1
2
∑
n
=
0
∞
x
n
n
!
\cfrac{1}{2}(1 + x + \cfrac{x^2}{2!} + \cdots)=\cfrac{1}{2}\sum\limits_{n=0}^\infty \cfrac{x^n}{n!}
21(1+x+2!x2+⋯)=21n=0∑∞n!xn
将
1
2
e
3
x
\cfrac{1}{2}e^{3x}
21e3x 展开后为
1
2
(
1
+
3
x
+
(
3
x
)
2
2
!
+
⋯
)
=
1
2
∑
n
=
0
∞
3
n
x
n
n
!
\cfrac{1}{2}(1 + 3x + \cfrac{(3x)^2}{2!} + \cdots)=\cfrac{1}{2}\sum\limits_{n=0}^\infty \cfrac{3^nx^n}{n!}
21(1+3x+2!(3x)2+⋯)=21n=0∑∞n!3nxn
=
1
2
∑
n
=
0
∞
3
n
x
n
n
!
+
1
2
∑
n
=
0
∞
x
n
n
!
\ \ \ \ \ \ \ \ \ \ \ \, =\cfrac{1}{2}\sum\limits_{n=0}^\infty \cfrac{3^nx^n}{n!} + \cfrac{1}{2}\sum\limits_{n=0}^\infty \cfrac{x^n}{n!}
=21n=0∑∞n!3nxn+21n=0∑∞n!xn
=
∑
n
=
0
∞
3
n
+
1
2
⋅
x
n
n
!
\ \ \ \ \ \ \ \ \ \ \ \, =\sum\limits_{n=0}^\infty \cfrac{3^n + 1}{2} \cdot \cfrac{x^n}{n!}
=n=0∑∞23n+1⋅n!xn
x
n
n
!
\cfrac{x^n}{n!}
n!xn 前的系数是
3
n
+
1
2
\cfrac{3^n + 1}{2}
23n+1
因此 白色 红色 蓝色 涂色
n
n
n 个格子 , 白色是偶数的情况下 , 涂色方案有
3
n
+
1
2
\cfrac{3^n + 1}{2}
23n+1 种 ;
