文章目录 多重集全排列公式 指数型母函数 处理多重集排列问题 引入 指数型母函数 处理多重集排列问题 公式推导 指数型母函数 处理 有限数字串问题 指数型母函数 处理 n 位数字串问题 指数型母函数 处理 n 位数字串问题 ( 考试题 ) 多重集全排列公式 给定多重集 , 有
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 2sum_{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) ;
