【组合数学】指数型母函数 应用 ( 多重集排列问题 | 不同球放在不同盒子里 | 奇/偶数序列的指数生成函数推导 )

多重集全排列公式

给定多重集 , 有 k k k 种元素 , 每种元素 n i n_i ni​ 个 ; 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​}

多重集全排列 公式是

n ! n 1 ! n 2 ! ⋯ n k ! \cfrac{n!}{n_1! n_2!\cdots n_k!} n1​!n2​!⋯nk​!n!​

其中 n = n 1 + n 2 + n 3 + ⋯ + n k n=n_1 + n_2 + n_3 + \cdots + n_k n=n1​+n2​+n3​+⋯+nk​ ;

指数型母函数 处理多重集排列问题 引入

给定多重集 , 有 k k k 种元素 , 每种元素 n i n_i ni​ 个 ; 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​}

但是如果不是全排列 , 是选取其中某些元素进行排列 , 就要用到 指数型母函数了 ;

指数型母函数 可以处理多重集排列问题 :

指数型母函数 处理多重集排列问题 公式推导

指数型母函数公式推导 :

① 每个元素都要找到其 通项 x k k ! \cfrac{x^k}{k!} k!xk​ ;

② 对于第一个元素 a 1 a_1 a1​ 可取的 个数 的 范围是 { 0 , 1 , 2 , 3 , ⋯   , n 1 } \{0, 1, 2, 3, \cdots , n_1\} {0,1,2,3,⋯,n1​} ,

其指数型生成函数是 x 0 0 ! + x 1 1 ! + x 2 2 ! + ⋯ x n 1 n 1 ! \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_1}}{{n_1}!} 0!x0​+1!x1​+2!x2​+⋯n1​!xn1​​

化简后为 : 1 + x 1 ! + x 2 2 ! + ⋯ x n 1 n 1 ! 1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_1}}{{n_1}!} 1+1!x​+2!x2​+⋯n1​!xn1​​

③ 对于第二个元素 a 2 a_2 a2​ 可取的个数 的 范围是 { 0 , 1 , 2 , 3 , ⋯   , n 2 } \{0, 1, 2, 3, \cdots , n_2\} {0,1,2,3,⋯,n2​} ;

其指数型生成函数是 x 0 0 ! + x 1 1 ! + x 2 2 ! + ⋯ x n 2 n 2 ! \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_2}}{{n_2}!} 0!x0​+1!x1​+2!x2​+⋯n2​!xn2​​

化简后为 : 1 + x 1 ! + x 2 2 ! + ⋯ x n 2 n 2 ! 1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_2}}{{n_2}!} 1+1!x​+2!x2​+⋯n2​!xn2​​

④ 对于第 k k k 个元素 a k a_k ak​ 可取的个数 的 范围是 { 0 , 1 , 2 , 3 , ⋯   , n k } \{0, 1, 2, 3, \cdots , n_k\} {0,1,2,3,⋯,nk​} ;

其指数型生成函数是 x 0 0 ! + x 1 1 ! + x 2 2 ! + ⋯ x n k n k ! \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_k}}{{n_k}!} 0!x0​+1!x1​+2!x2​+⋯nk​!xnk​​

化简后为 : 1 + x 1 ! + x 2 2 ! + ⋯ x n k n k ! 1 + \cfrac{x}{1!} + \cfrac{x^2}{2!} + \cdots \cfrac{x^{n_k}}{{n_k}!} 1+1!x​+2!x2​+⋯nk​!xnk​​

⑤ 最终的指数型母函数为 :

G e ( x ) = ( 1 + x 1 ! + x 2 2 ! + ⋯ x n 1 n 1 ! ) ( 1 + x 1 ! + x 2 2 ! + ⋯ x n 2 n 2 ! ) ⋯ ( 1 + x 1 ! + x 2 2 ! + ⋯ 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}!}) Ge​(x)=(1+1!x​+2!x2​+⋯n1​!xn1​​)(1+1!x​+2!x2​+⋯n2​!xn2​​)⋯(1+1!x​+2!x2​+⋯nk​!xnk​​)

指数型母函数 处理 有限数字串问题

题目 : 有 4 4 4 个数字 1 , 2 , 3 , 4 1, 2,3,4 1,2,3,4 构成 5 5 5 位数 方案数 ; 其中 1 1 1 出现次数不超过 2 2 2 次 , 不能不出现 ; 其中 2 2 2 出现此处不超过 1 1 1 次 ; 其中 3 3 3 出现次数可以达到 3 3 3 次 , 也可以不出现 ; 其中 4 4 4 出现次数必须是 偶数 ;

分析 :

• 1. 1 1 1 出现次数 : 1 1 1 出现次数不超过 2 2 2 次, 不能不出现, 因此 至少要出现 1 1 1 次, 其出现此处序列是 { 1 , 2 } \{1, 2\} {1,2} ;
  • 其对应指数型母函数为 : ( x 1 1 ! + x 2 2 ! ) (\cfrac{x^1}{1!} + \cfrac{x^2}{2!}) (1!x1​+2!x2​) ;
• 2. 2 2 2 出现次数 : 2 2 2 出现次数不超过 1 1 1 次 , 其出现此处序列是 { 0 , 1 } \{0, 1\} {0,1} ;
  • 其对应指数型母函数为 : ( x 0 0 ! + x 1 1 ! ) ( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} ) (0!x0​+1!x1​) ;
• 3. 3 3 3 出现次数 : 3 3 3 出现次数可达到 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 ! ) ( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} ) (0!x0​+1!x1​+2!x2​+3!x3​) ;
• 4. 4 4 4 出现次数 : 4 4 4 出现次数为偶数, 其出现此处序列是 { 0 , 2 , 4 } \{0, 2, 4\} {0,2,4} ;
  • 其对应指数型母函数为 : ( x 0 0 ! + x 2 2 ! + x 4 4 ! ) ( \cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} ) (0!x0​+2!x2​+4!x4​) ;

解 :

① 写出其对应的母函数 : 这里是排列 , 因此母函数通项必须是除以 k ! k! k! ; G e ( x ) = ( x 1 1 ! + x 2 2 ! ) ( x 0 0 ! + x 1 1 ! ) ( x 0 0 ! + x 1 1 ! + x 2 2 ! + x 3 3 ! ) ( x 0 0 ! + x 2 2 ! + x 4 4 ! ) = ( x + x 2 2 ! ) ( 1 + x ) ( 1 + x + x 2 2 ! + x 3 3 ! ) ( 1 + x 2 2 ! + x 4 4 ! ) 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!} ) Ge​(x)=(1!x1​+2!x2​)(0!x0​+1!x1​)(0!x0​+1!x1​+2!x2​+3!x3​)(0!x0​+2!x2​+4!x4​)=(x+2!x2​)(1+x)(1+x+2!x2​+3!x3​)(1+2!x2​+4!x4​)

② 将上述式子展开 :

G e ( x ) = ( x + 3 2 x 2 + 1 2 x 3 ) ( 1 + x + x 2 + 2 3 x 3 + 7 24 x 4 + 1 8 x 5 + 1 48 x 6 + 1 144 x 7 ) = x + 5 2 x 2 + 3 x 3 + 8 3 x 4 + 43 24 x 5 + 43 48 x 6 + 17 48 x 7 + 1 288 x 8 + 1 48 x 9 + 1 288 x 10 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} Ge​(x)=(x+23​x2+21​x3)(1+x+x2+32​x3+247​x4+81​x5+481​x6+1441​x7)=x+25​x2+3x3+38​x4+2443​x5+4843​x6+4817​x7+2881​x8+481​x9+2881​x10

③ 将上述式子 中 的 43 24 x 5 \cfrac{43}{24}x^5 2443​x5 项 转换为 x k k ! \cfrac{x^k}{k!} k!xk​ 的形式 :

43 × 5 ! 24 × 5 ! x 5 = 43 × 5 ! 24 × x 5 5 ! = 43 × 5 × 4 × 3 × 2 24 × x 5 5 ! = 215 × x 5 5 ! \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!} 24×5!43×5!​x5=2443×5!​×5!x5​=2443×5×4×3×2​×5!x5​=215×5!x5​

④ 上述计算结果 x 5 5 ! \cfrac{x^5}{5!} 5!x5​ 的 系数是 215 215 215 ; 因此 四个数字 构成 5 5 5 位数的方案数是 215 215 215 个 ;

指数型母函数 处理 n 位数字串问题

题目 : 求 1 , 3 , 5 , 7 , 9 1,3,5,7,9 1,3,5,7,9 五个数字 , 组成 n n n 位数的方案数 , 同时还要满足以下要求 ; 3 , 7 3,7 3,7 出现的此处为 偶数 ; 1 , 5 , 9 1,5,9 1,5,9 出现次数不加限制 ;

分析 : 相当于把 n n n 个不同的球放到 1 , 3 , 5 , 7 , 9 1,3,5,7,9 1,3,5,7,9 五个盒子中 , 每个盒子的球数 方案数 ;

• 3 , 7 3,7 3,7 出现次数分析 : 其只能出现 偶数次 , 即 出现次数是序列 { 0 , 2 , 4 , ⋯   } \{0, 2, 4, \cdots\} {0,2,4,⋯} ;

  • 对应的指数生成函数项为 : ( x 0 0 ! + x 2 2 ! + x 4 4 ! + …   ) (\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \dots) (0!x0​+2!x2​+4!x4​+…) ;

• 1 , 5 , 9 1,5,9 1,5,9 出现次数分析 : 其出现的次数不加限制 , 那么出现的次数序列是 0 , 1 , 2 , ⋯ {0, 1, 2, \cdots} 0,1,2,⋯

  • 对应的指数生成函数项为 : ( x 0 0 ! + x 1 1 ! + x 2 2 ! + ⋯   ) = e x ( \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots ) = e^x (0!x0​+1!x1​+2!x2​+⋯)=ex ;

解 :

① 写出对应的 指数生成函数 :

G e ( x ) = ( x 0 0 ! + x 2 2 ! + x 4 4 ! + ⋯   ) 2 ( x 0 0 ! + x 1 1 ! + x 2 2 ! + x 3 3 ! + ⋯   ) 3 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 Ge​(x)=(0!x0​+2!x2​+4!x4​+⋯)2(0!x0​+1!x1​+2!x2​+3!x3​+⋯)3

② 出现次数 正常自然数 序列 { 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 ! + x 3 3 ! + ⋯ = 1 + x + x 2 2 ! + x 3 3 ! + ⋯ = ∑ k = 0 ∞ 1 ⋅ x k k ! = e x \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!x0​+1!x1​+2!x2​+3!x3​+⋯1+x+2!x2​+3!x3​+⋯∑k=0∞​1⋅k!xk​ex​

② 出现 偶数次数 序列 { 0 , 2 , 4 , 6 , ⋯   } \{0 , 2, 4, 6 , \cdots\} {0,2,4,6,⋯} 指数型母函数计算 : 消掉奇数项 , 留下偶数项 ;

已知两个公式 :

e x = 1 + x + x 2 2 ! + x 3 3 ! + ⋯ e^x = 1+ x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots ex=1+x+2!x2​+3!x3​+⋯ ( 该公式所有项都是正的 )

e − x = 1 − x + x 2 2 ! − x 3 3 ! + ⋯ e^{-x} = 1 - x + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots e−x=1−x+2!x2​−3!x3​+⋯ ( 该公式所有偶数项 都是正的 , 所有奇数向都是负的 )

将两个式子相加 : e x + e − x = 1 + x + x 2 2 ! + x 3 3 ! + ⋯ + 1 − x + x 2 2 ! − x 3 3 ! + ⋯ = 1 × 2 + x 2 2 ! × 2 + x 4 4 ! × 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 \\ \\ & = & 1 \times 2 + \cfrac{x^2}{2!} \times 2 + \cfrac{x^4}{4!} \times 2 + \cdots \end{array} ex+e−x​==​1+x+2!x2​+3!x3​+⋯+1−x+2!x2​−3!x3​+⋯1×2+2!x2​×2+4!x4​×2+⋯​ ( 该结果是 偶数 序列 指数生成函数的 2 倍 )

偶数序列生成函数计算 : 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)

③ 将 ① ② 的结果代入到指数生成函数中 :

G e ( x ) = ( x 0 0 ! + x 2 2 ! + x 4 4 ! + ⋯   ) 2 ( x 0 0 ! + x 1 1 ! + x 2 2 ! + x 3 3 ! + ⋯   ) 3 = ( 1 2 ( e x + e − x ) ) 2 ( e x ) 3 = 1 4 ( 2 e x e − x + e 2 x + e − 2 x ) e 3 x = 1 4 ( 2 e 3 x + e 5 x + e x ) = 1 4 ( ∑ n = 0 ∞ 5 n n ! x n + 2 ∑ n = 0 ∞ 3 n n ! x n + ∑ n = 0 ∞ 1 n ! x n ) = 1 4 ∑ n = 0 ∞ ( 5 n + 2 ⋅ 3 n + 1 ) x n n ! \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} Ge​(x)​======​(0!x0​+2!x2​+4!x4​+⋯)2(0!x0​+1!x1​+2!x2​+3!x3​+⋯)3(21​(ex+e−x))2(ex)341​(2exe−x+e2x+e−2x)e3x41​(2e3x+e5x+ex)41​(∑n=0∞​n!5n​xn+2∑n=0∞​n!3n​xn+∑n=0∞​n!1​xn)41​∑n=0∞​(5n+2⋅3n+1)n!xn​​

至此 , 可以得到 x n n ! \cfrac{x^n}{n!} n!xn​ 的系数为 1 4 ( 5 n + 2 ⋅ 3 n + 1 ) \cfrac{1}{4} ( 5^n + 2 \cdot 3^n + 1 ) 41​(5n+2⋅3n+1)

④ 5 5 5 位数按照要求组成 n n n 位数的个数方案数 是 1 4 ( 5 n + 2 ⋅ 3 n + 1 ) \cfrac{1}{4} ( 5^n + 2 \cdot 3^n + 1 ) 41​(5n+2⋅3n+1) 种 ;

指数型母函数 处理 n 位数字串问题 ( 考试题 )

题目 : 把 n n n 个编号的球 , 放入 3 3 3 个不同的盒子里 , 同时还要满足以下要求 ; 第 1 1 1 个盒子至少放一个 ; 第 2 2 2 个盒子放奇数个 ; 第 3 3 3 个盒子放偶数个 ;

分析 :

• 第 1 1 1 个盒子放球数分析 : 至少放一个 , 其放球的 个数 序列是 { 1 , 2 , 3 , ⋯   } \{1, 2, 3, \cdots\} {1,2,3,⋯}
  • 第 1 1 1个盒子 的 放球序列 对应 指数生成函数 : ( x 1 1 ! + x 2 2 ! + x 3 3 ! + ⋯   ) (\cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots) (1!x1​+2!x2​+3!x3​+⋯)
• 第 2 2 2 个盒子放球数分析 : 放奇数个球 , 其放球的 个数 序列是 { 1 , 3 , 5 , ⋯   } \{1, 3, 5, \cdots\} {1,3,5,⋯}
  • 第 2 2 2个盒子 的 放球序列 对应 指数生成函数 : ( x 1 1 ! + x 3 3 ! + x 5 5 ! + ⋯   ) (\cfrac{x^1}{1!} + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots) (1!x1​+3!x3​+5!x5​+⋯)
• 第 3 3 3 个盒子放球数分析 : 放偶数个球 , 其放球的 个数 序列是 { 2 , 4 , 6 , ⋯   } \{2, 4, 6, \cdots\} {2,4,6,⋯}
  • 第 3 3 3个盒子 的 放球序列 对应 指数生成函数 : ( x 0 0 ! + x 2 2 ! + x 4 4 ! + ⋯   ) (\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots) (0!x0​+2!x2​+4!x4​+⋯)

解 :

① 写出生成函数 :

G e ( x ) = ( x 1 1 ! + x 2 2 ! + x 3 3 ! + ⋯   ) ( x 1 1 ! + x 3 3 ! + x 5 5 ! + ⋯   ) ( x 0 0 ! + x 2 2 ! + x 4 4 ! + ⋯   ) = ( x + x 2 2 ! + x 3 3 ! + ⋯   ) ( x + x 3 3 ! + x 5 5 ! + ⋯   ) ( 1 + x 2 2 ! + x 4 4 ! + ⋯   ) \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} Ge​(x)​==​(1!x1​+2!x2​+3!x3​+⋯)(1!x1​+3!x3​+5!x5​+⋯)(0!x0​+2!x2​+4!x4​+⋯)(x+2!x2​+3!x3​+⋯)(x+3!x3​+5!x5​+⋯)(1+2!x2​+4!x4​+⋯)​

② 计算 第 1 1 1 个 盒子 的 指数生成函数 项 ( 除 0 0 0 外的序列 ) :

已知公式 : e x = x 0 0 ! + x 1 1 ! + x 2 2 ! + x 3 3 ! + ⋯ = 1 + x + x 2 2 ! + x 3 3 ! + ⋯ \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} ex​==​0!x0​+1!x1​+2!x2​+3!x3​+⋯1+x+2!x2​+3!x3​+⋯​

e − x = x 0 0 ! − x 1 1 ! + x 2 2 ! − x 3 3 ! + ⋯ = 1 − x + x 2 2 ! − x 3 3 ! + ⋯ \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} e−x​==​0!x0​−1!x1​+2!x2​−3!x3​+⋯1−x+2!x2​−3!x3​+⋯​

第一个盒子对应的指数生成函数 : x + x 2 2 ! + x 3 3 ! + ⋯ = e x − 1 \begin{array}{lcl}\\ x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots = e^x-1 \end{array} x+2!x2​+3!x3​+⋯=ex−1​

③ 计算 第 2 2 2 个 盒子 的 指数生成函数 项 ( 奇数序列 ) :

e x − e − x = ( 1 + x + x 2 2 ! + x 3 3 ! + ⋯   ) − ( 1 − x + x 2 2 ! − x 3 3 ! + ⋯   ) = 2 ( x + x 3 3 ! + x 5 5 ! + ⋯   ) \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} ex−e−x​==​(1+x+2!x2​+3!x3​+⋯)−(1−x+2!x2​−3!x3​+⋯)2(x+3!x3​+5!x5​+⋯)​

因此奇数序列 对应指数生成函数 是 :

x + x 3 3 ! + x 5 5 ! + ⋯ = e x − e − x 2 x + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots = \cfrac{e^x - e^{-x}}{2} x+3!x3​+5!x5​+⋯=2ex−e−x​

④ 计算 第 3 3 3 个 盒子 的 指数生成函数 项 ( 偶数序列 ) :

e x + e − x = ( 1 + x + x 2 2 ! + x 3 3 ! + ⋯   ) + ( 1 − x + x 2 2 ! − x 3 3 ! + ⋯   ) = 2 ( 0 + x 2 2 ! + x 4 4 ! + ⋯   ) \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} ex+e−x​==​(1+x+2!x2​+3!x3​+⋯)+(1−x+2!x2​−3!x3​+⋯)2(0+2!x2​+4!x4​+⋯)​

因此奇数序列 对应指数生成函数 是 :

1 + x 2 2 ! + x 4 4 ! + ⋯ = e x + e − x 2 1 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots = \cfrac{e^x + e^{-x}}{2} 1+2!x2​+4!x4​+⋯=2ex+e−x​

⑤ 将 ② ③ ④ 结果 代入 指数生成函数 :

G e ( x ) = ( x + x 2 2 ! + x 3 3 ! + ⋯   ) ( x + x 3 3 ! + x 5 5 ! + ⋯   ) ( 1 + x 2 2 ! + x 4 4 ! + ⋯   ) = ( e x − 1 ) ( e x − e − x 2 ) ( e x + e − x 2 ) = 1 4 ( e x − 1 ) ( ( e x ) 2 − ( e − x ) 2 ) = 1 4 ( e x − 1 ) ( e 2 x − e − 2 x ) = 1 4 ( e x e 2 x − e x e − 2 x − e 2 x + e − 2 x ) = 1 4 ( e 3 x − e − x − e 2 x + e − 2 x ) = 1 4 ( ∑ n = 0 ∞ x n n ! 3 n − ∑ n = 0 ∞ x n n ! ( − 1 ) n − ∑ n = 0 ∞ x n n ! 2 n + ∑ n = 0 ∞ x n n ! ( − 2 ) n ) = ∑ n = 0 ∞ x n n ! ( 1 4 ( 3 n − ( − 1 ) n − 2 n + ( − 2 ) n ) ) \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} Ge​(x)​========​(x+2!x2​+3!x3​+⋯)(x+3!x3​+5!x5​+⋯)(1+2!x2​+4!x4​+⋯)(ex−1)(2ex−e−x​)(2ex+e−x​)41​(ex−1)((ex)2−(e−x)2)41​(ex−1)(e2x−e−2x)41​(exe2x−exe−2x−e2x+e−2x)41​(e3x−e−x−e2x+e−2x)41​(∑n=0∞​n!xn​3n−∑n=0∞​n!xn​(−1)n−∑n=0∞​n!xn​2n+∑n=0∞​n!xn​(−2)n)∑n=0∞​n!xn​(41​(3n−(−1)n−2n+(−2)n))​

至此 , 可以看到 x n n ! \cfrac{x^n}{n!} n!xn​ 前的系数为 1 4 ( 3 n − ( − 1 ) n − 2 n + ( − 2 ) n ) \cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n) 41​(3n−(−1)n−2n+(−2)n) ;

⑥ 最终结果计算 : 根据上述计算 , x n n ! \cfrac{x^n}{n!} n!xn​ 前的系数为 1 4 ( 3 n − ( − 1 ) n − 2 n + ( − 2 ) n ) \cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n) 41​(3n−(−1)n−2n+(−2)n) , 那么对应的 n n n 个编号的球 放入 3 个不同的盒子中 , 满足一系列条件的方案数为 1 4 ( 3 n − ( − 1 ) n − 2 n + ( − 2 ) n ) \cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n) 41​(3n−(−1)n−2n+(−2)n) ;