1、Lecture 2Generating FunctionsBy Yuhong Zhang (张玉宏 ) , 186-2371-8860 （O）, 159-3629-0516（H）ACM-Association for Computing Machinery ICPC-International Collegiate Programming Contest问题的导入一道一道 ACM试题试题 (offered by Weilong Zhang)求求 装有苹果、香蕉、橘子和梨的果篮装有苹果、香蕉、橘子和梨的果篮的数量的数量 hn，其中在每个果篮中苹果数，其中在每个果篮中苹果数是偶数，香蕉是是偶数，香
2、蕉是 5的倍数，橘子最多是的倍数，橘子最多是4个，而梨的个数是个，而梨的个数是 0或或 1。比如比如 h1=2,h2=3.数学方法解决问题 利用 generate function的方法，因此得到因此得到 hn=n+1.公式从何而来？*4问题 2： 若 有 1克、 2克、 3克、 4克的砝码各一 枚，能称出哪几种重量？各有几种可能方案？ 如何解决这个问题呢？考虑构造母函数。如果用 x的指数表示称出的重量，则：1个 1克的砝码可以用函数 1+x表示，1个 2克的砝码可以用函数 1+x2表示，1个 3克的砝码可以用函数 1+x3表示，1个 4克的砝码可以用函数 1+x4表示，*5几种砝码的组合可以
3、称重的情况，可以用以上几个函数的乘积表示：(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 从上面的函数知道： 可称出从 1克到 10克，系数便是方案数。例如右端有 2x5 项，即称出 5克的方案有 2： 5=3+2=4+1；同样， 6=1+2+3=4+2； 10=1+2+3+4。故称出 6克的方案有 2，称出 10克的方案有 1 Why?这是最简单的方式吗？问题还在继续？ x+2y=10的非 负 整数解的个数 将 这 个思想表示 为 如下的公式： (1 + x + x2 +
4、 x3+.)(1 + x2 + x4 + x6 +.) 求 x10的系数。Why?How？Problem Description：HDU1028 “Well, it seems the first problem is too easy. I will let you know how foolish you are later.“ feng5166 says.“The second problem is, given an positive integer N, we define an equation like this:N=a1+a2+a3+.+am;ai0,1=m=N;My ques
5、tion is how many different equations you can find for a given N.Problem Description：HDU1028 For example, assume N is 4, we can find:4 = 4;4 = 3 + 1;4 = 2 + 2;4 = 2 + 1 + 1;4 = 1 + 1 + 1 + 1;so the result is 5 when N is 4. Note that “4 = 3 + 1“ and “4 = 1 + 3“ is the same in this problem. Now, you do
6、 it!“A binomial is a polynomial with two terms such as x + a. Often we need to raise a binomial to a power. In this section well explore a way to do just that without lengthy multiplication.Can you see a pattern?Can you make a guess what the next one would be?We can easily see the pattern on the xs and the as. But what about the coefficients? Make a guess and then as we go well see how you did.
