3.2母函数及其性质2014

《3.2母函数及其性质2014》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、组合论第三章母函数(GeneratingFunction)1组合论第三章母函数§3.2母函数及其性质21本讲内容一、形式幂级数二、母函数的定义三、母函数的性质四、一些常见母函数的闭公式3知识点：母函数与形式幂级数母函数的性质内容及其掌握程度：理解用形式幂级数定义母函数的意义理解掌握母函数的性质熟练掌握一些母函数的闭公式42回顾上讲内容母函数将组合计数问题的计数结果表示成数列{ak:k≥0}=a0,a1,a2,…,称幂级数g(x)=a0+a1x+a2x2+…=∑k≥0akxk为数列{ak:k≥0}的母函数(普通型母函数).

2、母函数是组合论中求解计数问题的重要工具.5例1求以A(8,0,0),B(0,8,0),C(-8,0,0),D(0,-8,0),E(0,0,8),F(0,0,-8)为顶点的正8面体V内(包括表面)的整点个数。z分析：Ey一个整点(x,y,z)在CxV内所满A足的条件D是什么？F63例1解：一个整点（x,y,z）在V内所满足的充要条件是：

3、x

4、+

5、y

6、+

7、z

8、≤8等价于

9、x

10、+

11、y

12、+

13、z

14、+w=8(w≥0)7例1设

15、x

16、+

17、y

18、+

19、z

20、+w=n(w≥0)的整数解的个数为Cn一种自然的想法是化为熟知的知识来求解！84例1变形：

21、x

22、+

23、

24、y

25、+

26、z

27、+w=n+1(w≥1)的整数解的个数也为Cn在这里当

28、x

29、=0时x=0只有一种取值，当

30、x

31、>0时，x有两个取值。按照

32、x

33、,

34、y

35、,

36、z

37、中0的个数来进行分类:（1）没有一个等于0该类整数解的个数＝C(3,0)23C(n,3)9例1按照

38、x

39、,

40、y

41、,

42、z

43、=0的情况来进行分类:（2）有1个等于0该类整数解的个数＝C(3,1)22C(n,2)（3）有2个等于0该类整数解的个数＝C(3,2)21C(n,1)（4）有3个等于0该类整数解的个数＝C(3,3)20C(n,0)105例1设

44、x

45、+

46、y

47、+

48、z

49、+w=n(w≥0

50、)的整数解的个数为CnC＝C(3,0)23C(n,3)n乘加+C(3,1)22C(n,2)法法+C(3,2)21C(n,1)原原0理理+C(3,3)2C(n,0)11例1设

51、x

52、+

53、y

54、+

55、z

56、+w=n(w≥0)的整数解的个数为Cn求数列Cn的母函数：考虑x的取法：

57、x

58、=0，x=0，只有一种取法；

59、x

60、=t≥1，x=±t，有两种取法；可用幂级数（1＋2x+2x2+…）来表示126例1设

61、x

62、+

63、y

64、+

65、z

66、+w=n(w≥0)的整数解的个数为Cn求数列Cn的母函数：考虑y,z的取法，同x的取法；考虑w的取法:可用幂级数（1＋x+x2

67、+…）来表示13例1设

68、x

69、+

70、y

71、+

72、z

73、+w=n(w≥0)的整数解的个数为Cn求数列Cn的母函数g(x)：232(12+x+x+2)(1+x+x+)213=(-1)1-xx1-34(1xx)(1)147例1求数列Cn的母函数g(x)：34gx()(1x)(1x)41k23k(13x3xx)xk0k3k23k(13x3xx)xk0315例1求数列Cn：3n2n1nnC33n333338

74、373635C3383333168启示?211xx(1-)x避开考虑幂级数的敛散性问题,而又不影响母函数方法的适用性.我们将以形式幂级数的形式来定义数列的母函数.17本讲内容一、形式幂级数二、母函数的定义三、母函数的性质四、一些常见母函数的闭公式189一、形式幂级数用C表示复数域(可以是任一数域),x是不定元,看作是抽象符号.对C上任一数列{ak:k≥0}=a0,a1,a2,…,我们称表示式k2gx()axka0axax12k0为C上的形式幂级数.1

75、9一、形式幂级数两个形式幂级数是相等的当且仅当它们的同次项的系数相等。即kk若gx(())axhxkkbxkk00则g(x)=h(x)当且仅当ak=bk,k=0,1,2,….2010一、形式幂级数记C上所有形式幂级数的集合为C[[x]]，设kkgx()axhxkk,()bxCx[[]]kk00在C[[x]]上定义加法和乘法如下：k加法：()gxhx()(akkbx)k0k乘法：gx()hx()(abk0abk-11abx0k)k0C[[x]]构成一个有单位元的交换环,且无零因子

76、.实际上,由乘法定义知，若g(x)≠0,h(x)≠0,则g(x)h(x)≠0,故C[[x]]是整环.21一、形式幂级数整环C[[x]]的特殊元素2零元：000xx0单位元：2110x0x2常元：aa00xx