【组合数学】指数型母函数应用 ( 多重集排列问题 | 不同球放在不同盒子里

文章目录

- - - 多重集全排列公式
    - 指数型母函数处理多重集排列问题引入
    - 指数型母函数处理多重集排列问题公式推导
    - 指数型母函数处理有限数字串问题
    - 指数型母函数处理 n 位数字串问题
    - 指数型母函数处理 n 位数字串问题 ( 考试题 )

多重集全排列公式

给定多重集 , 有

k

k

$k$ 种元素 , 每种元素

n

i

n_i

$n_{i}$ 个 ;

{

⋅

⋯
 

⋅

}

S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k\}

$S = {n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}$

多重集全排列公式是

⋯

\cfrac{n!}{n_1! n_2!\cdots n_k!}

$\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$

其中

n

=

n

1

+

n

2

+

n

3

+

⋯

+

n

k

n=n_1 + n_2 + n_3 + \cdots + n_k

$n = n_{1} + n_{2} + n_{3} + \dots + n_{k}$ ;

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

给定多重集 , 有

k

k

$k$ 种元素 , 每种元素

n

i

n_i

$n_{i}$ 个 ;

{

⋅

⋯
 

⋅

}

S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k\}

$S = {n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}$

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

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

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

指数型母函数公式推导 :

① 每个元素都要找到其通项

x

k

k

!

\cfrac{x^k}{k!}

$\frac{x ^{k}}{k !}$ ;

② 对于第一个元素

a

1

a_1

$a_{1}$ 可取的个数的范围是

{

0

,

1

,

2

,

3

,

⋯
 

,

n

1

}

\{0, 1, 2, 3, \cdots , n_1\}

${0, 1, 2, 3, \dots, n_{1}}$ ,

其指数型生成函数是

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}!}

$\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{1}}}{n _{1} !}$

化简后为 :

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 + \frac{x}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{1}}}{n _{1} !}$

③ 对于第二个元素

a

2

a_2

$a_{2}$ 可取的个数的范围是

{

0

,

1

,

2

,

3

,

⋯
 

,

n

2

}

\{0, 1, 2, 3, \cdots , n_2\}

${0, 1, 2, 3, \dots, n_{2}}$ ;

其指数型生成函数是

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}!}

$\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{2}}}{n _{2} !}$

化简后为 :

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 + \frac{x}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{2}}}{n _{2} !}$

④ 对于第

k

k

$k$ 个元素

a

k

a_k

$a_{k}$ 可取的个数的范围是

{

0

,

1

,

2

,

3

,

⋯
 

,

n

k

}

\{0, 1, 2, 3, \cdots , n_k\}

${0, 1, 2, 3, \dots, n_{k}}$ ;

其指数型生成函数是

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}!}

$\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{k}}}{n _{k} !}$

化简后为 :

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 + \frac{x}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{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}!})

$G_{e} (x) = (1 + \frac{x}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{1}}}{n _{1} !}) (1 + \frac{x}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{2}}}{n _{2} !}) \dots (1 + \frac{x}{1 !} + \frac{x ^{2}}{2 !} + \dots \frac{x ^{n_{k}}}{n _{k} !})$

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

题目 :
有

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$ 出现次数不超过

2

2

$2$ 次, 不能不出现, 因此至少要出现

1

1

$1$ 次, 其出现此处序列是

{

1

,

2

}

\{1, 2\}

${1, 2}$ ;
- 其对应指数型母函数为 : $(\cfrac{x^1}{1!} + \cfrac{x^2}{2!})$
  $(\frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !})$ ;
2.
$2$ 出现次数 :

2

2

$2$ 出现次数不超过

1

1

$1$ 次 , 其出现此处序列是

{

0

,

1

}

\{0, 1\}

${0, 1}$ ;
- 其对应指数型母函数为 : $\cfrac{x^0}{0!} + \cfrac{x^1}{1!} )$
  $(\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !})$ ;
3.
$3$ 出现次数 :

3

3

$3$ 出现次数可达到

3

3

$3$ 次, 可以不出现, 其出现此处序列是

{

0

,

1

,

2

,

3

}

\{0, 1, 2, 3\}

${0, 1, 2, 3}$ ;
- 其对应指数型母函数为 : $\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} )$
  $(\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !})$ ;
4.
$4$ 出现次数 :

4

4

$4$ 出现次数为偶数, 其出现此处序列是

{

0

,

2

,

4

}

\{0, 2, 4\}

${0, 2, 4}$ ;
- 其对应指数型母函数为 : $\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} )$
  $(\frac{x ^{0}}{0 !} + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !})$ ;

解 :

① 写出其对应的母函数 : 这里是排列 , 因此母函数通项必须是除以

k

!

k!

$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) = (\frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !}) (\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !}) (\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !}) (\frac{x ^{0}}{0 !} + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !}) = (x + \frac{x ^{2}}{2 !}) (1 + x) (1 + x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !}) (1 + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !})$

② 将上述式子展开 :

(

)

(

)

(

144

)

288

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}

$G_{e} (x) = (x + \frac{3}{2} x^{2} + \frac{1}{2} x^{3}) (1 + x + x^{2} + \frac{2}{3} x^{3} + \frac{7}{2 4} x^{4} + \frac{1}{8} x^{5} + \frac{1}{4 8} x^{6} + \frac{1}{1 4 4} x^{7}) = x + \frac{5}{2} x^{2} + 3 x^{3} + \frac{8}{3} x^{4} + \frac{4 3}{2 4} x^{5} + \frac{4 3}{4 8} x^{6} + \frac{1 7}{4 8} x^{7} + \frac{1}{2 8 8} x^{8} + \frac{1}{4 8} x^{9} + \frac{1}{2 8 8} x^{10}$

③ 将上述式子中的

43

24

x

5

\cfrac{43}{24}x^5

$\frac{4 3}{2 4} x^{5}$ 项转换为

x

k

k

!

\cfrac{x^k}{k!}

$\frac{x ^{k}}{k !}$ 的形式 :

215

\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!}

$\frac{4 3 \times 5 !}{2 4 \times 5 !} x^{5} = \frac{4 3 \times 5 !}{2 4} \times \frac{x ^{5}}{5 !} = \frac{4 3 \times 5 \times 4 \times 3 \times 2}{2 4} \times \frac{x ^{5}}{5 !} = 215 \times \frac{x ^{5}}{5 !}$

④ 上述计算结果

x

5

5

!

\cfrac{x^5}{5!}

$\frac{x ^{5}}{5 !}$ 的系数是

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, \dots}$ ;
- 对应的指数生成函数项为 : $(\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \dots)$
  $(\frac{x ^{0}}{0 !} + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots)$ ;
1

,

5

,

9

1,5,9

$1, 5, 9$ 出现次数分析 : 其出现的次数不加限制 , 那么出现的次数序列是

0

,

1

,

2

,

⋯

{0, 1, 2, \cdots}

$0, 1, 2, \dots$
- 对应的指数生成函数项为 : $\cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cdots ) = e^x$
  $(\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \dots) = e^{x}$ ;

解 :

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

(

)

(

⋯
 

)

(

⋯
 

)

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

$G_{e} (x) = (\frac{x ^{0}}{0 !} + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots)^{2} (\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots)^{3}$

② 出现次数正常自然数序列

{

0

,

1

,

2

,

3

,

4

,

⋯
 

}

\{ 0, 1, 2, 3, 4, \cdots\}

${0, 1, 2, 3, 4, \dots}$ 指数型母函数计算 :

⋯

∑

∞

⋅

\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}

$= = = \frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots 1 + x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots \sum_{k = 0}^{\infty} 1 \cdot \frac{x ^{k}}{k !} e^{x}$

② 出现偶数次数序列

{

0

,

2

,

4

,

6

,

⋯
 

}

\{0 , 2, 4, 6 , \cdots\}

${0, 2, 4, 6, \dots}$ 指数型母函数计算 : 消掉奇数项 , 留下偶数项 ;

已知两个公式 :

⋯

e^x = 1+ x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots

$e^{x} = 1 + x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots$
( 该公式所有项都是正的 )

−

⋯

e^{-x} = 1 - x + \cfrac{x^2}{2!} - \cfrac{x^3}{3!} + \cdots

$e^{- x} = 1 - x + \frac{x ^{2}}{2 !} - \frac{x ^{3}}{3 !} + \dots$
( 该公式所有偶数项都是正的 , 所有奇数向都是负的 )

将两个式子相加 :

−

⋯

−

⋯

\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}

$e^{x} + e^{- x} = = 1 + x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots + 1 - x + \frac{x ^{2}}{2 !} - \frac{x ^{3}}{3 !} + \dots 1 \times 2 + \frac{x ^{2}}{2 !} \times 2 + \frac{x ^{4}}{4 !} \times 2 + \dots$
( 该结果是偶数序列指数生成函数的 2 倍 )

偶数序列生成函数计算 :

⋯

(

−

)

1 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots = \cfrac{1}{2} (e^x + e^{-x})

$1 + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots = \frac{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}

$G_{e} (x) = = = = = = (\frac{x ^{0}}{0 !} + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots)^{2} (\frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots)^{3} (\frac{1}{2} (e^{x} + e^{- x}))^{2} (e^{x})^{3} \frac{1}{4} (2 e^{x} e^{- x} + e^{2 x} + e^{- 2 x}) e^{3 x} \frac{1}{4} (2 e^{3 x} + e^{5 x} + e^{x}) \frac{1}{4} (\sum_{n = 0}^{\infty} \frac{5 ^{n}}{n !} x^{n} + 2 \sum_{n = 0}^{\infty} \frac{3 ^{n}}{n !} x^{n} + \sum_{n = 0}^{\infty} \frac{1}{n !} x^{n}) \frac{1}{4} \sum_{n = 0}^{\infty} (5^{n} + 2 \cdot 3^{n} + 1) \frac{x ^{n}}{n !}$

至此 , 可以得到

x

n

n

!

\cfrac{x^n}{n!}

$\frac{x ^{n}}{n !}$ 的系数为

1

4

(

5

n

+

2

⋅

3

n

+

1

)

\cfrac{1}{4} ( 5^n + 2 \cdot 3^n + 1 )

$\frac{1}{4} (5^{n} + 2 \cdot 3^{n} + 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 )

$\frac{1}{4} (5^{n} + 2 \cdot 3^{n} + 1)$ 种 ;

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

题目 : 把

n

n

$n$ 个编号的球 , 放入

3

3

$3$ 个不同的盒子里 , 同时还要满足以下要求 ;
第

1

1

$1$ 个盒子至少放一个 ;
第

2

2

$2$ 个盒子放奇数个 ;
第

3

3

$3$ 个盒子放偶数个 ;

分析 :

第 $\{1, 2, 3, \cdots\}$
${1, 2, 3, \dots}$
- 第 $(\cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots)$
  $(\frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots)$
第 $\{1, 3, 5, \cdots\}$
${1, 3, 5, \dots}$
- 第 $(\cfrac{x^1}{1!} + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots)$
  $(\frac{x ^{1}}{1 !} + \frac{x ^{3}}{3 !} + \frac{x ^{5}}{5 !} + \dots)$
第 $\{2, 4, 6, \cdots\}$
${2, 4, 6, \dots}$
- 第 $(\cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots)$
  $(\frac{x ^{0}}{0 !} + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots)$

解 :

① 写出生成函数 :

(

)

(

⋯
 

)

(

⋯
 

)

(

⋯
 

)

(

⋯
 

)

(

⋯
 

)

(

⋯
 

)

\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}

$G_{e} (x) = = (\frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots) (\frac{x ^{1}}{1 !} + \frac{x ^{3}}{3 !} + \frac{x ^{5}}{5 !} + \dots) (\frac{x ^{0}}{0 !} + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots) (x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots) (x + \frac{x ^{3}}{3 !} + \frac{x ^{5}}{5 !} + \dots) (1 + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots)$

② 计算第

1

1

$1$ 个盒子的指数生成函数项 ( 除

0

0

$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}

$e^{x} = = \frac{x ^{0}}{0 !} + \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots 1 + x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots$

−

⋯

−

⋯

\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} = = \frac{x ^{0}}{0 !} - \frac{x ^{1}}{1 !} + \frac{x ^{2}}{2 !} - \frac{x ^{3}}{3 !} + \dots 1 - x + \frac{x ^{2}}{2 !} - \frac{x ^{3}}{3 !} + \dots$

第一个盒子对应的指数生成函数 :

⋯

−

\begin{array}{lcl}\\ x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} + \cdots = e^x-1 \end{array}

$x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots = e^{x} - 1$

③ 计算第

2

2

$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}

$e^{x} - e^{- x} = = (1 + x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots) - (1 - x + \frac{x ^{2}}{2 !} - \frac{x ^{3}}{3 !} + \dots) 2 (x + \frac{x ^{3}}{3 !} + \frac{x ^{5}}{5 !} + \dots)$

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

⋯

−

x + \cfrac{x^3}{3!} + \cfrac{x^5}{5!} + \cdots = \cfrac{e^x - e^{-x}}{2}

$x + \frac{x ^{3}}{3 !} + \frac{x ^{5}}{5 !} + \dots = \frac{e ^{x} - e ^{- x}}{2}$

④ 计算第

3

3

$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}

$e^{x} + e^{- x} = = (1 + x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots) + (1 - x + \frac{x ^{2}}{2 !} - \frac{x ^{3}}{3 !} + \dots) 2 (0 + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots)$

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

⋯

−

1 + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} + \cdots = \cfrac{e^x + e^{-x}}{2}

$1 + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots = \frac{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}

$G_{e} (x) = = = = = = = = (x + \frac{x ^{2}}{2 !} + \frac{x ^{3}}{3 !} + \dots) (x + \frac{x ^{3}}{3 !} + \frac{x ^{5}}{5 !} + \dots) (1 + \frac{x ^{2}}{2 !} + \frac{x ^{4}}{4 !} + \dots) (e^{x} - 1) (\frac{e ^{x} - e ^{- x}}{2}) (\frac{e ^{x} + e ^{- x}}{2}) \frac{1}{4} (e^{x} - 1) ((e^{x})^{2} - (e^{- x})^{2}) \frac{1}{4} (e^{x} - 1) (e^{2 x} - e^{- 2 x}) \frac{1}{4} (e^{x} e^{2 x} - e^{x} e^{- 2 x} - e^{2 x} + e^{- 2 x}) \frac{1}{4} (e^{3 x} - e^{- x} - e^{2 x} + e - 2 x) \frac{1}{4} (\sum_{n = 0}^{\infty} \frac{x ^{n}}{n !} 3^{n} - \sum_{n = 0}^{\infty} \frac{x ^{n}}{n !} (- 1)^{n} - \sum_{n = 0}^{\infty} \frac{x ^{n}}{n !} 2^{n} + \sum_{n = 0}^{\infty} \frac{x ^{n}}{n !} (- 2)^{n}) \sum_{n = 0}^{\infty} \frac{x ^{n}}{n !} (\frac{1}{4} (3^{n} - (- 1)^{n} - 2^{n} + (- 2)^{n}))$

至此 , 可以看到

x

n

n

!

\cfrac{x^n}{n!}

$\frac{x ^{n}}{n !}$ 前的系数为

1

4

(

3

n

−

(

−

1

)

n

−

2

n

+

(

−

2

)

n

)

\cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n)

$\frac{1}{4} (3^{n} - (- 1)^{n} - 2^{n} + (- 2)^{n})$ ;

⑥ 最终结果计算 :
根据上述计算 ,

x

n

n

!

\cfrac{x^n}{n!}

$\frac{x ^{n}}{n !}$ 前的系数为

1

4

(

3

n

−

(

−

1

)

n

−

2

n

+

(

−

2

)

n

)

\cfrac{1}{4} ( 3^n - (-1)^n - 2^n + (-2)^n)

$\frac{1}{4} (3^{n} - (- 1)^{n} - 2^{n} + (- 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)

$\frac{1}{4} (3^{n} - (- 1)^{n} - 2^{n} + (- 2)^{n})$ ;

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

文章目录

多重集全排列公式

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

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

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

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

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

相关推荐

一个分享Java & Python知识的社区

文章目录

多重集全排列公式

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

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

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

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

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

相关推荐

一个分享Java & Python知识的社区

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

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

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

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

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