【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )

一. 生成函数 ( 母函数 ) 的定义 1. 生成函数定义 ( 1 ) 生成函数的定义

生成函数定义 :

• 1.假设条件 : 设 a 0 , a 1 , ⋯   , a n a_0 , a_1 , \cdots , a_n a0​,a1​,⋯,an​ 是一个数列 ;
• 2.形式幂级数 : 使用 该 数列 做 形式幂级数 A ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a n x n + ⋯ A(x) = a_0 + a_1x +a_2x^2 + \cdots + a_nx^n + \cdots A(x)=a0​+a1​x+a2​x2+⋯+an​xn+⋯
• 3.生成函数 : 称上述 A ( x ) A(x) A(x) 是 数列 a 0 , a 1 , ⋯   , a n a_0 , a_1 , \cdots , a_n a0​,a1​,⋯,an​ 的 生成函数 ;

( 2 ) 形式幂级数 ( 参考 )

形式幂级数 :

• 1.幂级数 : 数学分析 中 重要概念 , 在 指数级的 每一项 均为 与 级数项 序号 n n n 相对应的 以 常数倍的 ( x − a ) (x-a) (x−a) 的 n n n 次方 ( n n n 是从 0 0 0 开始计数的整数 , a a a 为常数 ) ;
  • 幂级数用途 : 其 被 作为 基础内容 应用到了 实变函数 , 复变函数 , 等众多领域 中 ;
• 2.形式幂级数 : 是 数学中 的 抽奖概念 , 从 幂级数 中 抽离出来 的 代数对象 ; 形式幂级数 和 从 多项式 中 剥离出的 多项式环 类似 , 但是 其 允许 无穷多项式 因子 相加 , 但不像 幂级数 一般 要求 研究 是否收敛 和 是否有确定的 取值 ;
  • ① 假设条件 : 设 x x x 是一个符号 , a i ( i = 0 , 1 , 2 , ⋯   ) a_i ( i = 0 , 1 , 2 , \cdots ) ai​(i=0,1,2,⋯) 为实数 ;
  • ② 未定元 形式幂级数 : A ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a n x n + ⋯ = ∑ n = 0 ∞ A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots = \sum_{n=0}^{\infty} A(x)=a0​+a1​x+a2​x2+⋯+an​xn+⋯=n=0∑∞​ 称为 x x x 的未定元 的 一个 形式幂级数 ;
• 3.研究重点 : 形式幂级数 中 , x x x 从来 不指定具体数值 , 不关心 收敛 或 发散 , 关注的重点是其 系数序列 a 0 , a 1 , ⋯   , a n a_0 , a_1 , \cdots , a_n a0​,a1​,⋯,an​ , 研究形式幂级数 完全可以 归结为 讨论 这些系数序列 ;

2. 生成函数 示例 ( 1 ) 生成函数 示例 1 ( a n = ( m n ) a_n = \dbinom{m}{n} an​=(nm​) )

示例题目 : 设 a n = ( m n ) a_n = \dbinom{m}{n} an​=(nm​) , m m m 为正整数 , 求数列 { a n } \{a_n\} {an​} 的生成函数 A ( x ) A(x) A(x) ;

解 :

① 列出生成函数 : A ( x ) = ( m 0 ) x 0 + ( m 1 ) x 1 + ( m 2 ) x 2 + ⋯ + ( m n ) x n A(x) = \dbinom{m}{0}x^0 + \dbinom{m}{1}x^1 + \dbinom{m}{2}x^2 + \cdots + \dbinom{m}{n}x^n A(x)=(0m​)x0+(1m​)x1+(2m​)x2+⋯+(nm​)xn

② 列出其累加生成函数 : A ( x ) = ∑ n = 0 ∞ ( m n ) x n A(x) = \sum_{n=0}^\infty \dbinom{m}{n}x^n A(x)=n=0∑∞​(nm​)xn

③ 当 n n n 大于 m m m 时 , 从 m m m 中 取 n n n , 即 ( m n ) \dbinom{m}{n} (nm​) 为 0 , 因此可以 直接计算 从 n = 0 n=0 n=0 到 n = m n=m n=m 的值 , 即 得到如下步骤 : A ( x ) = ∑ n = 0 ∞ ( m n ) x n = ∑ n = 0 m ( m n ) x n A(x) = \sum_{n=0}^\infty \dbinom{m}{n}x^n = \sum_{n=0}^m \dbinom{m}{n}x^n A(x)=n=0∑∞​(nm​)xn=n=0∑m​(nm​)xn

④ 根据 二项式定理 的推论内容 ( 设 n n n 是正整数 , 对一切 x x x 有 ( 1 + x ) n = ∑ k = 0 n ( n k ) x k (1+x)^n=\sum_{k=0}^n\dbinom{n}{k}x^k (1+x)n=∑k=0n​(kn​)xk ) 可以得到 A ( x ) = ∑ n = 0 ∞ ( m n ) x n = ∑ n = 0 m ( m n ) x n = ( 1 + x ) m A(x) = \sum_{n=0}^\infty \dbinom{m}{n}x^n = \sum_{n=0}^m \dbinom{m}{n}x^n = (1 + x)^m A(x)=n=0∑∞​(nm​)xn=n=0∑m​(nm​)xn=(1+x)m

⑤ 数列 a n = ( m n ) a_n = \dbinom{m}{n} an​=(nm​) ( m m m 为正整数 ) , 的 生成函数 为 : A ( x ) = ( 1 + x ) m A(x) = (1 + x)^m A(x)=(1+x)m

注意 : 生成函数 从属于 一个数列 , 说明生成函数时 , 先说明其数列 , 指明 数列 的 生成函数 是 某个函数 ;

( 2 ) 生成函数 示例 2 ( { k n } \{k^n\} {kn} )

题目 : 给定 正整数 k k k , 求 { k n } \{k^n\} {kn} 的生成函数 ;

① 写出生成函数 : 将 { k n } \{k^n\} {kn} 作为形式幂级数 系数 , 可以得到 如下 等比数列 , 当 x x x 充分小的时候 , 其收敛到 1 1 − k x \frac{1}{1-kx} 1−kx1​ ; A ( x ) = k 0 x 0 + k 1 x 1 + k 2 x 2 + k 3 x 3 + ⋯ = 1 1 − k x A(x) = k^0x^0 + k^1x^1 + k^2x^2 + k^3x^3 + \cdots = \frac{1}{1-kx} A(x)=k0x0+k1x1+k2x2+k3x3+⋯=1−kx1​

② { k n } \{k^n\} {kn} 数列的 生成函数 为 : A ( x ) = 1 1 − k x A(x) = \frac{1}{1-kx} A(x)=1−kx1​

2. 牛顿二项式 ( 1 ) 牛顿二项式 系数

牛顿二项式 系数 : 组合数的扩展 , C ( m , n ) C(m, n) C(m,n) 上项不再是大于等于 n n n 的数了 , 而是任意实数 ;

• 1.条件 : 任意 实数 r r r , 和 整数 n n n ;
• 2.公式 : ( r n ) = { 0 , n < 0 1 , n = 0 r ( r − 1 ) ⋯ ( r − n + 1 ) n ! , n > 0 \dbinom{r}{n} = \begin{cases} 0, & n < 0 \\ 1, & n=0 \\ \cfrac{r(r-1)\cdots(r-n+1)}{n!}, & n>0 \end{cases} (nr​)=⎩⎪⎪⎨⎪⎪⎧​0,1,n!r(r−1)⋯(r−n+1)​,​n0​
• 3.结论 : 该 ( r n ) \dbinom{r}{n} (nr​) 没有 组合意义 , 只是 记号 , 称为 牛顿二项式系数 ;

选取问题中 :

• 不可重复的元素 , 有序的选取 , 对应 集合的排列 ; P ( n , r ) = n ! ( n − r ) ! P(n,r) = \dfrac{n!}{(n-r)!} P(n,r)=(n−r)!n!​
• 不可重复的元素 , 无序的选取 , 对应 集合的组合 ; C ( n , r ) = P ( n , r ) r ! = n ! r ! ( n − r ) ! C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!} C(n,r)=r!P(n,r)​=r!(n−r)!n!​
• 可重复的元素 , 有序的选取 , 对应 多重集的排列 ; 全 排 列 = n ! n 1 ! n 2 ! ⋯ n k ! 全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!} 全排列=n1​!n2​!⋯nk​!n!​ , 非全排列 k r ,    r ≤ n i k^r , \ \ r\leq n_i kr,  r≤ni​
• 可重复的元素 , 无序的选取 , 对应 多重集的组合 ; N = C ( k + r − 1 , r ) N= C(k + r - 1, r) N=C(k+r−1,r)

( 2 ) 牛顿二项式 定理

牛顿二项式定理 :

• 1.条件 : α \alpha α 为 实数 , 对于一切 x , y x , y x,y , 并且 ∣ x y ∣ < 1 \left| \frac{x}{y} \right| < 1 ∣∣∣​yx​∣∣∣​ m n > m n>m 时 , ( m n ) = 0 \dbinom{m}{n}=0 (nm​)=0 , 因此只需要考虑 n < m n{(1-x)}^m} \end{aligned} {(1+x)}^m} \end{aligned} {(1-x)}^2} \end{aligned}