组合数学 ppt课件

• • • • • 7.1生成函数的定义和性质 7.2多重集的r-组合数 7.3正整数的划分 7.4指数生成函数与多重集的排列问题 7.5Catalan数和Stiring
§7.1 生成函数概念
§4.1 生成函数的基本概念
4.1.1 生成函数
定义 4.1
给定一无穷序列(a0,a1,…an,…)(简记为{an})，称函
e
1! 2! 1 4 7 ... (3n 1) n x n! n0 4 7 ... 3n 1 3 3 3n x n 1 3 n! n 1 4 4 1 ... 4 n 1 3 3 3 1 ( 3 x )n n! n 1 4 1 3 ( 3 x )n n n 1
§7.1 生成函数的基本概念 7.1.2 指数生成函数
定义 7.2 给定一无穷序列(a0,a1,…an,…)（简记为{an}），称函 xi 数 f e ( x ) ai 为序列{an}的指数生成函数。 i! i 0 注： fe(x)也是形式幂函数。 经常可结合以下公式运算： 2 n x x x e x 1 2 ... n ... 1! 2! n! n x x2 x n x e 1 ... ( 1) ... 1! 2! n! x x3 x 2 n 1 e x e x sin x ... ... 1! 3! (2n 1)! 2
********************** 课程总结
第7章 生成函数
本章重点介绍生成函数（生成函数、指数生成函 数）的基本概念及其在排列组合中的应用 ： 生成函数的基本概念 生成函数的基本运算 生成函数在排列、组合中的应用 整数拆分 生成函数在组合恒等式中的应用

超鸽巢原理
总结词
超鸽巢原理是鸽巢原理的一种扩展，它考虑 了多于两种元素的情况。
详细描述
超鸽巢原理是在鸽巢原理的基础上，进一步 推广到多于两种元素的情况。它涉及到多个 元素和多个鸽巢之间的关系，并用于解决一 些更为复杂的问题。超鸽巢原理的应用范围 广泛，包括组合计数、图论等领域。
鸽巢原理的变体
总结词
鸽巢原理与其他数学原理的结合
总结词
将鸽巢原理与其他数学原理结合使用，可以 产生更强大的理论工具。
ቤተ መጻሕፍቲ ባይዱ
详细描述
鸽巢原理是组合数学中的重要原理，但它的 应用范围有限。为了解决更复杂的问题，一 些数学家尝试将鸽巢原理与其他数学原理结 合使用。这种结合可以产生更强大的理论工 具，能够解决一些单独使用鸽巢原理无法解 决的问题。通过与其他数学原理的结合，鸽
鸽巢原理证明中的注意事项
在证明过程中，需要注意鸽巢原理的适用条件，即每个鸽 巢中的物体数量必须相同。如果每个鸽巢中的物体数量不 同，那么鸽巢原理就不适用。
另外，在证明过程中还需要注意逻辑推理的严密性，确保 每一步推理都是正确的，没有出现逻辑错误或遗漏。同时 ，还需要注意数学符号和公式的正确使用，以确保证明的 准确性和可读性。
鸽巢原理的变体是对原原理的某种修改或扩展，以适应特定的问题或情境。
详细描述
随着数学的发展，人们发现鸽巢原理在某些情况下可能并不适用，或者需要对它进行一 些修改以更好地解决问题。因此，一些数学家提出了鸽巢原理的变体。这些变体可能涉
及到对原原理的修改、扩展或与其他数学原理的结合，以适应更广泛的问题和情境。
02
在数学中，鸽巢原理常用于证明 一些组合数学和数论中的问题， 如整数分拆、集合的划分等。
鸽巢原理的适用范围

§ 7.1 生成函数例6 § 7.1指数 生成函数的基本概念
7.1.2 指数生成函数
例 题
例6、求序列(p(0,0), p(2,1), p(4,2),…, p(2n,n),…)的指数生成函数fe(x)。
解：由定义7.2及公式P(n,r)=r!C(n,r)，以及例3的结论，有 x x2 xn f e ( x ) p(0, 0) p(2,1) p(4, 2) ... p(2n, n) ... 1! 2! n! 0 2 x 4 x 2 ... 2n x n ... 0 1 2 n (1 4 x )1 2


§7.1 指数生成函数例7 §7.1 生成函数的基本概念
7.1.2 指数生成函数
例 题
例7、求序列{1,α,α2,…,αn,…}的指数生成函 数fe(x)。其中α是实数。
2 n x x x fe ( x ) 1 2 ... n ... e x 1! 2! n!
组合数学课件
制作讲授：王继顺
目录（1）
目
第1章 什么是组合数学 1.1引例 1.2组合数学研究对象、内容和方法 第2章 鸽巢原理 2.1 鸽巢原理：简单形式 2.2 鸽巢原理：加强形式 2.3 Ramsey定理 2.4 鸽巢原理与Ramsey定理的应用 本章小结 习题 第3章 排列与组合 3.1 两个基本的计数原理 3.2 集合的排列与组合 3.3 多重集的排列与组合 本章小结 习题
例 题
例2、求序列(C(n-1,0), -C(n,1), C(n+1,2), …, (1)kC(n+k-1,k), … )的生成函数。
§7.1 生成函数例2
解：由定义7.1及二项式定理的推论3.10.2有

积分性质
若G(x)是母函数，则它的不定积分∫G(x)dx （其中C为常数）也是母函数。
线性性质
若G1(x)和G2(x)是两个母函数，则它们的 线性组合k1*G1(x)+k2*G2(x)（k1和k2是 常数）也是母函数。
微分性质
若G(x)是母函数，则它的导数G'(x)也是母 函数。
乘积性质
若G1(x)和G2(x)是两个母函数，则它们的 乘积G1(x)*G2(x)也是母函数。
对称性
C(n,m) = C(n,n-m)，即从n个元素中取出m个元 素的组合数与从n个元素中取出n-m个元素的组 合数相等。
递推关系
C(n,m) = C(n-1,m-1) + C(n-1,m)，即当前组合 数等于前一个元素在组合中和不在组合中的两种 情况之和。
边界条件
C(n,0) = C(n,n) = 1，即从n个元素中取出0个或 n个元素的组合数均为1。
典型例题解析
例1
从10个数中任取4个数，求其中最大数为6的组合数。
解析
此问题等价于从6个数（1至6）中取4个数的组合数，即 C(6,4)。
例2
在所有的三位数中，各位数字之和等于10的三位数有 多少个？
解析
此问题可转化为从9个数字（1至9）中取3个数字的组合 数，即C(9,3)，然后考虑三个数字的全排列，即3!，因此 总共有C(9,3) × 3!个符合条件的三位数。
组合与排列的关系
组合数可以看作是从n个元素中取出m个元素进行排 列的种数除以m的阶乘，即C(n，m)=A(n，m)/m!。 因此，在计算组合数时也可以利用排列数和容斥原 理来进行计算。
THANKS
隔板法
将n个相同的元素分成r组的方法数可以用母函数表示为 C(n+r-1,r)，其中C表示组合数。

Δ［x］n=［x+1］n-［x］n =(x+1)［x］n-1-(x-n+1)［x］n-1 =n［x］n-1
反演公式

使用［x］n的Taylor公式展开φ(x)=［x+y］n， Δkφ(0)=n(n-1) …(n-k+1)［y］n-k
就有Δ二项式公式：
n n
[ x
y ]n
k0 k
[x]k [ y]nk
证明 易证每个n次多项式φn(x)都可以唯一地表示为
n ( x) ak Pk ( x) anPn ( x) an P 1 n1( x) a0P0 ( x)
0k n
其中an, an-1, …, a0是常数。事实上，取an为φn(x)中xn的系数除以 Pn(x)中xn的系数所得的商，则φn-1(x)=φn(x)-anPn(x)至多是n-1次的， 再取an-1为φn-1(x)中xn-1的系数除以Pn-1(x)中xn-1的系数所得的商， 接着考虑
常 的 微 商 d/dx ， 上 述 命 题 中 的 公 式 ， 就 是 标 准 的 Taylor-
Maclaurin展开式。
反演公式 1.
令y为一常数，考虑多项式φ(x)=(x+y)n，
Pn(x)=xn (P0(x)=1, Pn(0)=0, n≥1) 这时，伴随族Pn(x)的微分算子就是通常的微商：
a=(αnk)b
b=(βnk)a
其中，a
{an
}m n0
,
b
{bn
}m n0
都
是
m+1
维
空
间
的
列
向
量
。
亦
即
（4.1.6）式成立。
反演公式

A B

500 15

33.
根据容斥原理，从1到500的整数中不能被3和5整除的数的个数为
| A B || S | | A | | B | | A B | 267
§5.1 包含排§斥原5.理1 例包2含排斥原理 5.1.3 包含排斥原理
习题训练
练2、求a,b,c,d,e,f六个字母的全排列中不 允许出现ace和df图像的排列数。

1000 [5,6,8]
8;
根据容斥原理，不能被5,6,8中任何一个数整除的数目为
A B C 1000 (200 166 125) (33 41 25) 8 600.
§5.1 包含排§斥原5.理1 例包9含排斥原理
5.1.3 包含排斥原理
5.1.3 包含排斥原理 例6、证明以下等式：§5.1 包含排斥原理例8
例
题 nr

m m



m 0

n r



m
1


n
1
r



(1)m

m m


n
r
m

.
其中n,r,m为正整数，m≤r ≤ n.
组合数学课件
制作讲授：王继顺
第5章 包含排斥原理
本章重点介绍包含排斥原理及其在排列组合 中的应用：
• §5.1包含排斥原理 • §5.2 多重集的r-组合数 • §5.3错位排列 • §5.4 有限制条件的排列问题 • §5.5有禁区的排列问题
第5章 包含排斥原理
教学目标：

H(x) A B A(12x)B(1x) 1x 12x (1x(12x)
(A B)2-A(B)x (1x)1(2x)
( A B ) ( 2 A B ) x x
§2.2 递推关系
由上式可得：
{ A 2 A B B 01 A 1 , B1 .
即：H(x) 1 1 12x 1x
(12x22x223x3)(1xx2) (21)x(21)x(21)x
C(mn,mn)xmn
§2.1 母函数
比较等号两端项对应系数，可得一等式
C ( m n ,r ) C ( m , 0 ) C ( n ,r ) C ( m , 1 ) C ( n ,r 1 ) C ( m ,r ) C ( n , 0 )
§2.1 同母样函对数于
，〔设
用类似的方法可得等式：
§2.2 递推关系
Hanoi问题是个典型的问题，第一步要设 计算法，进而估计它的复杂性，集估计工作量。
算法： N=2时 第最第一后二步把步先B上把把的下最圆面上盘的面移一的到个一C圆个上盘圆移盘到套C在上B上 到此转移完毕
A
B
C
§2.2 递推关系
假定n-1个盘子的转移算法已经确定。 对于一般n个圆盘的问题，
x 2 x 3 x 2 /1 ( x )
§2.2 递推关系
整理得
(1 2 x)H (x)x2 xx 1 x 1 x
这两种做法得到的结果是一样的。即：
H(x) x (1x)1(2x)
§2.2 递推关系
如何从母函数得到序列h(1 )h ,(2) , ？下 面介绍一种化为局部分数的算法。 令
以依次求得h(2)h ,(3) , ，这样的连锁反应关
系，叫做递推关系。
§2.2 递推关系

11
一、序数法
怎样建立a(3)a(2)a(1)p(1)p(2)p(3)p(4)
a(3) 确定4的位置,a(2)确定3的位置
a(1)确定2的位置,剩余的位置就是1的位置 例3:021, 3 2 1 4 例3: 201, 2 4 1 3
12
一、序数法
求n个不同的数的全排列，主要有以下两步：
1、求出0到n!-1之间各数对应的序列{an-1, an-2,…, a1} m=an-1(n-1)!+an-2(n-2)!+…a2 * 2!+a1*1! 2、由{an-1, an-2,…, a1}确定排列序列p1p2…pn an-1,确定n的位置， an-2确定n-1的位置， ……………………… a1确定2的位置， 剩下的是1的位置。
9
一、序数法
推论 从0到n!-1的n!个整数与序列{an-1, an-2,…, a1} 一一对应。这里 0a1 1,0 a2 2, …, 0 an-1 n-1 算法: int a[]={0}; int m,n;// 0=<m<=n!-1 int b=m； int index =1; do { a[index]=b%(index+1); b = b/(index+1); index++; } while(b);
14
一、序数法
2、对于0,1,2,…,n!-1共n!个数求序列a[i]
for( i = 0; i < fact; i++ ) { int b=i, index =1; do { a[index]=b%(index+1); b = b/(index+1); index++; } while(b);

1 jn
1i j n
命题 3（加法的结合律） 如果1≤m≤n， 则
aj aj aj aj aj
1 jn
1 jm m jn
1 jm
m jn
第二章 基本计数原理
命题 4（乘法交换律）
ai aj aj ai
1 jm 1 jn
1 jn 1im
命题 5（乘法对加法的分配律）
推论
a aj aaj
1 jn
j0
第二章 基本计数原理
3. 双下标
(a11 a12 a1n ) (a21 a22 a2n ) (am1 am2 amn )
a1 j a2 j amj ( aij )
1 jn
1 jn
1 jn
1im 1 jn
4. 给定数42的所有因子之和
1+2+3+6+7+14+21+42= k
注: 本例指围棋，现代围棋采用十九路，即有19×19=361 个交叉点可落黑子、 白子或留空。
第二章 基本计数原理
例 5 求含有数字1的4位数的个数。 解 先求不含有1的4位数的个数，即求由{0, 2, 3, 4, 5, 6, 7, 8, 9}9个数字组成的4位数的个数（第一位不得出现0）。由乘法原 理，
2a1 b1,2a2 b2 ,,2an bn ,2an1 bn1
第二章 基本计数原理
例 3 某次会议有n位代表参加，已知每一位代表至少认识 其余n-1位中的一位，则n位代表中至少有两位认识的人数相等。
证明 n位代表认识的人数有1, 2, …, n-1， 由鸽巢原理知至少 两位代表认识的人数相等。
第二章 基本计数原理
· 对（2.1.10 №1 定义数组A(1∶N, 1∶N)； №2 对i=1, N, 输入A(i, i)；

20
1.8：应用举例
(2)编码中的纠错功能
编码中的纠错功能是这样处理的，如果收到 a=a 1a 2…a n假设a 与a的汉明距离小于或等于r, 则认为a是由a的错误引起的，将它作为a处理。 可能存在a与a和b的汉明距离都小于或等于r, 怎么才能避免这种情况呢？对编码有什么要求呢？
码b与码a之间的汉明距离要大于或等于2r+1.
(n+1,r)
(0,0)
(n,0)
12
1.7 组合的解释
1.35 C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m
1 0 2 0 3 1 … … m-2 m-1 m 1 0 0
没有0，C（m,0）
只有一个0，C（m,1） 只有二个0，C（m,2） ……………….
M个全是0，C（m,m）
为
9999-6560=3449。
25
1.9 例题 1.15试求从1到1000的整数中，0出现的次数。 解：先将1到999的整数都看作3位数,例如2就看 作是002，这样从000到999。0出现了多少次呢？ 3×102，某一位取0，其它各位任取。 0出现在最前面的次数应该从中去掉 000到999中最左1位的0出现了102次， 000到099中左数第2位的0出现了10次， 000到009左数第3位的0出现了1次, 因此不合法的0的个数为 102+101+1=111，不合法的应该去掉，再加整 数1000中的3个0，这样，从1到1000的整数中0出 现的次数为3×102-111+6=195。
13
1.7 组合的解释 1.35 C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m (0,m) (1,m-1)

进阶练习题
题目4
在7个不同元素中取出5个 元素有多少种不同的取法 ？
题目5
从8个人中选出3个人来组 成一个小组，其中某个人 必须被选中，有多少种不 同的选法？
题目6
从10个不同的元素中取出 4个元素的组合数是多少？
答案解析
题目1答案
$C_{5}^{3} = frac{5!}{3!2!} = 10$种不同的 选法。
组合数的性质在计算中的应用
利用组合数的性质简化计算
通过组合数的性质，可以将复杂的组合数计算转化为简单的计算，例如利用性质 公式和递推公式简化计算。
解决实际问题
组合数在现实生活中有着广泛的应用，例如在概率论、统计学、计算机科学等领 域中都有涉及。通过掌握组合数的性质，可以更好地解决实际问题。
03
组合数公式的推导
题目2答案
$C_{5}^{3} = frac{5!}{3!2!} = 10$种不同的组 合数。
题目3答案
$C_{4}^{2} = frac{4!}{2!2!} = 6$种不同的取法 。
题目4答案
$C_{7}^{5} = frac{7!}{5!2!} = 21$种不同的取法。
题目5答案
$C_{8}^{3} - C_{7}^{2} = 56 - 21 = 35$种不同 的选法。
组合数的性质
总结词
组合数具有一些重要的性质，包括组合数的 对称性、组合数的递推关系、组合数的性质 等。
详细描述
组合数具有对称性，即C(n, m) = C(n, nm)，这意味着从n个不同元素中取出m个元 素和从n个不同元素中取出n-m个元素的方 式数量是相等的。此外，组合数还具有递推 关系，即C(n, m) = C(n-1, m-1) + C(n-1,

二项式定理
汇报人：
2023-11-28
目录
• 二项式定理的背景和定义 • 二项式定理的公式和证明 • 二项式定理的应用 • 二项式定理的扩展和推广 • 二项式定理的意义和影响 • 二项式定理的实例和分析
01
二项式定理的背景和定义
背景介绍
二项式定理在数学中有着悠久的历史，它起源于17世纪，是组合数学中的一种基本理论。
03
二项式定理的应用
组合数学中的应用
排列数公式
二项式定理可以用于计算排列数公式，即从n个不同的元素中取出m个元素的所有排列的个数。
组合数公式
二项式定理可以用于计算组合数公式，即从n个不同的元素中取出m个元素的所有组合的个数。
插入与删除操作
二项式定理可以用于计算在n个元素中进行插入或删除操作的总次数，以及进行特定次数的插入或删除操 作的所有可能方式的个数。
概率论中的应用
概率分布
二项式定理可以用于计算二项分布的概率分布，即某个事 件在n次独立试验中发生的次数的概率分布。
01
组合概率
二项式定理可以用于计算多个事件同时 发生的概率，即组合事件发生的概率。
02
03
事件的独立性
二项式定理可以用于判断两个事件是 否独立，即一个事件的发生是否会影 响另一个事件发生的概率。
组合数性质：在二项式定理中，我们 使用了组合数的性质。组合数 $C(n,k)$ 等于 $C(n-1,k-1) + C(n1,k)$，这是组合数的一个重要性质。 这个性质可以帮助我们在二项式定理 的证明过程中进行简化。
指数性质：在证明二项式定理的过程 中，我们还使用了指数的性质。例如 ，当 $n$ 为偶数时，$(a+b)^n = (a+b)^{n/2} \times (a+b)^{n/2}$ ；当 $n$ 为奇数时，$(a+b)^n = (a+b)^{n/2} \times (a+b)^{n/2-1} \times b$。这些指数性质可以帮助 我们在计算过程中进行简化。

关系
超几何分布的概率值可以通过组合数公式进行计 算，特别是当总体大小远大于样本大小时。
二项式系数与组合数的关系
二项式系数
二项式系数表示在n次独立实验中成功k次的概率，通常表 示为C(n, k) = binomial(n, k) / k!
组合数公式
组合数公式是计算从n个不同元素中选取k个元素的不同方 式的数量。
关系
二项式系数是组合数的一种特例，当n次实验中每次成功 的概率为p时，二项式系数可以表示为C(n, k) = p^k * (1p)^(n-k)。
组合数与卡特兰数的关系
卡特兰数
卡特兰数是组合数学中的一类特殊数，通常用于计数排列、组合等 问题的解中选取k个元素的不同方式的数量 。
组合数的定义
总结词
组合数表示从n个不同元素中取出 m个元素的组合方式数量，记作 C(n, m)或C_n^m。
详细描述
组合数的定义基于组合的定义， 通过数学公式表示为C(n, m) = n! / (m!(n-m)!)，其中"!"表示阶乘 。
组合数的性质
总结词
组合数具有一些重要的性质，包括组合数的递推关系、对称性、非负性等。
组合数的计算公式具有对称性 ，即C(n，m)=C(n，n-m)，同 时还有C(n，0)=C(n，n)=1的 特殊性质。
组合数的性质在计算中的应用
利用组合数的性质可以简化组合数的计算，例如利用对称性可以避免一些不必要的 计算。
利用组合数的性质可以推导出一些重要的组合恒等式，例如二项式定理、帕斯卡三 角等。
当m=n时，排列就是组合；当取出元素不同时，排列和组合是不同的。
组合数的计算公式
组合数的计算公式为C(n， m)=n!/(m!(n-m)!)，其中n是 总的元素个数，m是需要取出 的元素个数，C(n，m)表示从n 个元素中取出m个元素的组合 数。

由归纳法，命题成立。
§6.1 递推关系的建立
Fibonacci数列性质 §6.1 Fibonacci数列应用及性质（2） 2. Fibonacci数
f (0) f (1) f (n) f (n 2) 1.
证明
f (0) f (2) f (1), f (1) f (3) f (2),
********************** 课程总结
第6章 递推关系 本章主要介绍递推关系的建立及几种 常见的求解方法： •6.1 Fibonacci数列 •6.2 常系数线性齐次递推关系的求解 •6.3 常系数线性非齐次递推关系的求解 •6.4 用迭代和归纳法求解递推关系
第6章 递推关系 第6章 递推关系
f (n) f (n 2) f (n 1).

把以上各式的左边和右边分别相加，得
f (0) f (1) f (n) f (n 2) f (1) f (n 2) 1.
§6.1 递推关系的建立
Fibonacci数列性质 §6.1 Fibonacci数列应用及性质（3-4） 3. Fibonacci数 f (0) f (2) f (2n) f (2n 1).
教学目标： 1．掌握几种递推关系的建立方法； 2．理解并掌握常系数线性齐次及非齐次递推关系的求解方法； 3．能运用迭代归纳法求解递推关系； 4．记住并理解Fibonacci数的定义及递推公式，会推导 Fibonacci数的一些性质，能运用它们解决一些组合计数问 题。 重点： 递推关系的建立方法、常系数线性齐次及非齐次递推关系的求 解方法、Fibonacci数和Catalan数的定义、递推公式及性质 难点： Catalan数的定义、递推公式及性质

2020/12/10
14
§4.2 生成组合
生成组合
4.2.1 基2算法 若S是n个元素的集合，元素为{xn-1,...,x1,x0}， 则生成组合就是生成S的所有2n个子集。 任一子集可以描述成：
(an-1,...,a1,a0)=an-1...a1a0 其中，ai为1或0，表示xi在或不在子集中。
于是S的全部子集可以用0~2n-1的整数来描 述，只要生成这些整数，也就得到了所有组合。
其中，0表示空集，2n-1表示S本身。
全排列生 成算法
2020/12/10
6
3. 直接生成全排列的算法
全排列生 成算法
[定义]对排列中的每个元素k，赋予其一
个方向：k 或 k 。如果一个整数k的箭头 指向一个与其相邻但比它小的整数，则
称k是活动的。
例如，对于：263154
只有6、3、5是活动的。
2020/12/10
7
显然：
全排列生 成算法
a1+a2+...+an 度量了排列的无序程度。
2020/12/10
11
全排列生
[例]31524的逆序列是1,2,0,1,0。 成算法
[结论]对于逆序列，显然有0≤ak≤n-k。且 任何一个排列都可确定一个逆序列。
[定理]若b1,b2,...,bn是满足0≤bk≤n-k的整数 序列，则存在{1,2,...,n}的唯一的一个排 列，其逆序列为b1,b2,...,bn 。
21
2020/12/10
4
{1,2,3}的排列
全排列生
1 2 3 成算法 2 31 31 2 32 1 13 2 2 13
2020/12/10
5

(1 x) n 1 C (n,1) x C (n,2) x 2 C (n, n) x n (2 - 1 - 2)
§2.1
母函数
另一方面：
(1 x) m (1 x) n (1 x) m n
[C (n,0) C (n,1) x C (n, n) x n ] [C (m,0) C (m,1) x 1 C (m, m) x m ] x [C (m n,0) C (m n,1) x C (m n, m n) x
242问题的求解242问题的求解242问题的求解242问题的求解242问题的求解其中25线性常系数递推关系定义如果序列满足阶常系数线性递推关系称为的初始条件称为的特征多项式25线性常系数递推关系25线性常系数递推关系将这些式子两边分别相加得到25线性常系数递推关系25线性常系数递推关系因此次多项式我们知道在复数域中25线性常系数递推关系25线性常系数递推关系253式是有理式且分子的次数低于分母的次数有分项表示即
G( x) a0 a1 x a2 x , 称函数G(x)是序列a0 , a1 , a2 , 的母函数
§2.1
母函数
例如
如若已知序列 a0 , a1 , a2 ,, 则对应的母函 数G(x)便可根据定义给出。反之，如若以求得 序列的母函数G(x)，则该序列也随之确定。 序列 a0 , a1 , a2 ,, 可记为 {an }。
2 3 2
§2.2
递推关系
整理得
x x (1 2 x) H ( x) x 1 x 1 x
这两种做法得到的结果是一样的。即：
2
x H ( x) (1 x)(1 2 x)
§2.2

并约定，若某个ai＝0 (i＝0,1,2,…)，则项aixi可以略去，且x0可简记为1。
{1·a1,1·a2,4·a3,1·a4}
x1 x1 x4 x1＝x7
S＝{2·a1,1·a2,∞·a3,9·a4} (1)求{a1,a2,…,an}的r组合数
设x是一个抽象符号，an(n＝0,1,2,…)为实数列，若函数F(x)可表示成 (2)求{∞·a1,∞·a2,…,∞
x1＋x2＋…＋x9)
{2·a1,2·a3,3·a4}
x2 x0 x2 x3＝x7
{1·a1,1·a2,4·a3,1·a4}
x1 x1 x4 x1＝x7
{7·a4}
x0 x0 x0 x7＝x7
题意分配方案 F(x)右边展开式中x7项(未合并同类)
b7＝F(x)右边展开式中x7项的系数
2.1.2 重集的组合
11 n
22 n
nn n
F(x)＝(x1＋x3＋x5＋…)(x0＋x2＋x4＋…)(x2＋x3＋x4＋x5)(x0＋x1＋x2＋x3＋…)(x0＋x1＋x2＋x3＋…)
解 用xk表示k个球，圆括号表示盒子，做
试讨论S的7组合的个数b7
无穷序列1,1,1,…的生成函数为 题意分配方案 F(x)右边展开式中x7项(未合并同类)
x4＋x5)(x0＋x1＋x2＋x3＋…)(x0＋x1＋x2＋x3＋…) 盒1 盒2 盒3 盒4 盒5
球的个数 (3) (0) (2) (2) (2) x3 x0 x2 x2 x2＝x9 球的个数 (3) (2) (3) (0) (1) x3 x2 x3 x0 x1＝x9 题意分配方案 F(x)右边展开式中x9项(未合并同类) a9＝F(x)右边展开式中x9项的系数
2.1.2 重集的组合