文章目录
多重集全排列公式
给定多重集 , 有
k 种元素 , 每种元素
n_i 个 ;
S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k\}多重集全排列 公式是
\cfrac{n!}{n_1! n_2!\cdots n_k!}其中
n=n_1 + n_2 + n_3 + \cdots + n_k ;
指数型母函数 处理多重集排列问题 引入
给定多重集 , 有
k 种元素 , 每种元素
n_i 个 ;
S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k\}但是如果不是全排列 , 是选取其中某些元素进行排列 , 就要用到 指数型母函数了 ;
指数型母函数 可以处理多重集排列问题 :
指数型母函数 处理多重集排列问题 公式推导
指数型母函数公式推导 :
① 每个元素都要找到其 通项
\cfrac{x^k}{k!} ;
② 对于第一个元素
a_1 可取的 个数 的 范围是
\{0, 1, 2, 3, \cdots , n_1\} ,
其指数型生成函数是
\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_1}}{{n_1}!}化简后为 :
1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_1}}{{n_1}!}③ 对于第二个元素
a_2 可取的个数 的 范围是
\{0, 1, 2, 3, \cdots , n_2\} ;
其指数型生成函数是
\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_2}}{{n_2}!}化简后为 :
1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_2}}{{n_2}!}④ 对于第
k 个元素
a_k 可取的个数 的 范围是
\{0, 1, 2, 3, \cdots , n_k\} ;
其指数型生成函数是
\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_k}}{{n_k}!}化简后为 :
1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_k}}{{n_k}!}⑤ 最终的指数型母函数为 :
G_e(x) = (1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_1}}{{n_1}!}) (1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_2}}{{n_2}!}) \cdots (1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_k}}{{n_k}!})
指数型母函数 处理 有限数字串问题
题目 :
有
4 个数字
1, 2,3,4 构成
5 位数 方案数 ;
其中
1 出现次数不超过
2 次 , 不能不出现 ;
其中
2 出现此处不超过
1 次 ;
其中
3 出现次数可以达到
3 次 , 也可以不出现 ;
其中
4 出现次数必须是 偶数 ;
分析 :
1 出现次数 :
1 出现次数不超过
2 次, 不能不出现, 因此 至少要出现
1 次, 其出现此处序列是
\{1, 2\} ;
(\cfrac{x^1}{1!} + \cfrac{x^2}{2!}) ;
2 出现次数 :
2 出现次数不超过
1 次 , 其出现此处序列是
\{0, 1\} ;
( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} ) ;
3 出现次数 :
3 出现次数可达到
3 次, 可以不出现, 其出现此处序列是
\{0, 1, 2, 3\} ;
( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} ) ;
4 出现次数 :
4 出现次数为偶数, 其出现此处序列是
\{0, 2, 4\} ;
( \cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} ) ;
解 :
① 写出其对应的母函数 : 这里是排列 , 因此母函数通项必须是除以
k! ;
G_e(x) = (\cfrac{x^1}{1!} + \cfrac{x^2}{2!}) ( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} ) ( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} ) ( \cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} )\\ = ( 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!} )② 将上述式子展开 :
G_e(x) = (x + \cfrac{3}{2} x^2 + \cfrac{1}{2} x^3) (1 + x + x^2 + \cfrac{2}{3}x^3+ \cfrac{7}{24}x^4 + \cfrac{1}{8}x^5 + \cfrac{1}{48}x^6 + \cfrac{1}{144}x^7) \\ = x + \cfrac{5}{2}x^2 + 3x^3 + \cfrac{8}{3}x^4 + \cfrac{43}{24}x^5 + \cfrac{43}{48}x^6 + \cfrac{17}{48}x^7 + \cfrac{1}{288}x^8 + \cfrac{1}{48}x^9 + \cfrac{1}{288}x^{10}③ 将上述式子 中 的
\cfrac{43}{24}x^5 项 转换为
\cfrac{x^k}{k!} 的形式 :
\cfrac{43 \times 5!}{24 \times 5!}x^5 =\cfrac{43 \times 5!}{24} \times \cfrac{x^5}{5!} =\cfrac{43 \times 5 \times 4 \times 3 \times 2}{24} \times \cfrac{x^5}{5!} = 215 \times \cfrac{x^5}{5!}④ 上述计算结果
\cfrac{x^5}{5!} 的 系数是
215 ; 因此 四个数字 构成
5 位数的方案数是
215 个 ;
指数型母函数 处理 n 位数字串问题
题目 : 求
1,3,5,7,9 五个数字 , 组成
n 位数的方案数 , 同时还要满足以下要求 ;
3,7 出现的此处为 偶数 ;
1,5,9 出现次数不加限制 ;
分析 : 相当于把
n 个不同的球放到
1,3,5,7,9 五个盒子中 , 每个盒子的球数 方案数 ;
3,7 出现次数分析 : 其只能出现 偶数次 , 即 出现次数是序列
\{0, 2, 4, \cdots\} ;
(\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \dots) ;
1,5,9 出现次数分析 : 其出现的次数不加限制 , 那么出现的次数序列是
{0, 1, 2, \cdots}解 :
① 写出对应的 指数生成函数 :
G_e(x) = ( \cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots )^2 ( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots)^3② 出现次数 正常自然数 序列
\{ 0, 1, 2, 3, 4, \cdots\} 指数型母函数计算 :
\begin{array}{lcl} & \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots\\ \\ = & 1+ x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots\\ \\ =& \sum_{k=0}^{\infty} 1 \cdot \cfrac{x^k}{k!} \\ = & e^x \end{array}② 出现 偶数次数 序列
\{0 , 2, 4, 6 , \cdots\} 指数型母函数计算 : 消掉奇数项 , 留下偶数项 ;
已知两个公式 :
e^x = 1+ x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots
( 该公式所有项都是正的 )
e^{-x} = 1 - x + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots
( 该公式所有偶数项 都是正的 , 所有奇数向都是负的 )
将两个式子相加 :
\begin{array}{lcl}e^x + e^{-x} & = & 1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots \\ \\ && +1 - x + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots \\ \\ & = & 1 \times 2 + \cfrac{x^2}{2!} \times 2 + \cfrac{x^4}{4!} \times 2 + \cdots \end{array}
( 该结果是 偶数 序列 指数生成函数的 2 倍 )
偶数序列生成函数计算 :
1 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots = \cfrac{1}{2} (e^x + e^{-x})③ 将 ① ② 的结果代入到指数生成函数中 :
\begin{array}{lcl}G_e(x) &=& ( \cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots )^2 ( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots)^3\\ \\ &=& ( \cfrac{1}{2} (e^x + e^{-x}))^2 (e^x)^3 \\ &=& \cfrac{1}{4}( 2 e^x e^{-x} + e^{2x} + e^{-2x} ) e^{3x} \\ &=& \cfrac{1}{4}( 2 e^{3x} + e^{5x} + e^{x} ) \\ &=& \cfrac{1}{4} ( \sum_{n=0}^{\infty} \cfrac{5^n}{n!} x^n + 2\sum_{n=0}^{\infty} \cfrac{3^n}{n!} x^n + \sum_{n=0}^{\infty} \cfrac{1}{n!} x^n ) \\ &=& \cfrac{1}{4} \sum_{n=0}^{\infty} ( 5^n + 2 \cdot 3^n + 1 ) \cfrac{x^n}{n!} \\ \end{array}至此 , 可以得到
\cfrac{x^n}{n!} 的系数为
\cfrac{1}{4} ( 5^n + 2 \cdot 3^n + 1 )④
5 位数按照要求组成
n 位数的个数方案数 是
\cfrac{1}{4} ( 5^n + 2 \cdot 3^n + 1 ) 种 ;
指数型母函数 处理 n 位数字串问题 ( 考试题 )
题目 : 把
n 个编号的球 , 放入
3 个不同的盒子里 , 同时还要满足以下要求 ;
第
1 个盒子至少放一个 ;
第
2 个盒子放奇数个 ;
第
3 个盒子放偶数个 ;
分析 :
1 个盒子放球数分析 : 至少放一个 , 其放球的 个数 序列是
\{1, 2, 3, \cdots\}2 个盒子放球数分析 : 放奇数个球 , 其放球的 个数 序列是
\{1, 3, 5, \cdots\}3 个盒子放球数分析 : 放偶数个球 , 其放球的 个数 序列是
\{2, 4, 6, \cdots\}解 :
① 写出生成函数 :
\begin{array}{lcl}\\ G_e(x) &=& (\cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots) ( \cfrac{x^1}{1!} + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots ) ( \cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots )\\ \\ &=& ( x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots ) ( x + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots ) ( 1 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots ) \\ \end{array}② 计算 第
1 个 盒子 的 指数生成函数 项 ( 除
0 外的序列 ) :
已知公式 :
\begin{array}{lcl}e^x &=& \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots\\ \\ &=& 1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots \\ \end{array}\begin{array}{lcl}e^{-x} &=& \cfrac{x^0}{0!} - \cfrac{x^1}{1!} + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots\\ \\ &=& 1 - x + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots \\ \end{array}第一个盒子对应的指数生成函数 :
\begin{array}{lcl}\\ x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots = e^x-1 \end{array}③ 计算 第
2 个 盒子 的 指数生成函数 项 ( 奇数序列 ) :
\begin{array}{lcl}\\ e^x - e^{-x} &=& (1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots) - (1 - x + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots) \\ &=& 2 ( x + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots) \\ \end{array}因此奇数序列 对应指数生成函数 是 :
x + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots = \cfrac{e^x - e^{-x}}{2}④ 计算 第
3 个 盒子 的 指数生成函数 项 ( 偶数序列 ) :
\begin{array}{lcl}\\ e^x + e^{-x} &=& (1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots) + (1 - x + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots) \\ &=& 2 ( 0 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots) \\ \end{array}因此奇数序列 对应指数生成函数 是 :
1 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots = \cfrac{e^x + e^{-x}}{2}⑤ 将 ② ③ ④ 结果 代入 指数生成函数 :
\begin{array}{lcl}\\ G_e(x) &=& ( x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots ) ( x + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots ) ( 1 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots )\\ \\ \\ &=& ( e^x - 1) ( \cfrac{e^x - e^{-x}}{2} ) ( \cfrac{e^x + e^{-x}}{2} ) \\ \\ &=& \cfrac{1}{4} (e^x - 1) ( (e^x)^2 - (e^{-x})^2 ) \\ \\ &=& \cfrac{1}{4} (e^x - 1) ( e^{2x} - e^{-2x} ) \\ \\ &=& \cfrac{1}{4} ( e^x e^{2x} - e^x e^{-2x} - e^{2x} + e^{-2x} ) \\ \\ &=& \cfrac{1}{4} (e^{3x} - e^{-x} - e^{2x} + e{-2x} ) \\ \\ &=& \cfrac{1}{4} ( \sum_{n=0}^{\infty}\cfrac{x^n}{n!} 3^n - \sum_{n=0}^{\infty}\cfrac{x^n}{n!} (-1)^n - \sum_{n=0}^{\infty}\cfrac{x^n}{n!} 2^n + \sum_{n=0}^{\infty}\cfrac{x^n}{n!} (-2)^n) \\ \\ &=& \sum_{n=0}^{\infty}\cfrac{x^n}{n!} ( \cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n) ) \\ \\ \end{array}至此 , 可以看到
\cfrac{x^n}{n!} 前的系数为
\cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n) ;
⑥ 最终结果计算 :
根据上述计算 ,
\cfrac{x^n}{n!} 前的系数为
\cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n) , 那么对应的
n 个编号的球 放入 3 个不同的盒子中 , 满足一系列条件的方案数为
\cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n) ;
