离散数学课件-第3章-5,6.ppt

第三章 计数技术Example 1 序列{ak}具有ak=3,ak=k+1和ak=2k的生成函数分别是我们通过置an+1=0，an+2=0，依次下去把一个有限序列a0,a1,…an扩 充成一个无限序列，就可以定义一个实数的有限序列的生成函数。这个无限序列{an}的生成函数G(x)是一个n次多项式，因为当jn 时没有形如ajxj的项出现，即 G(x)=a0+a1x+a2x2+a3x3+…+anxn Solution：1，1，1，1，1，1的生成函数是 1+x+x2+x3+x4+x5 由3.2节的定理1，有 (x6-1)/(x-1)=1+x+x2+x3+x4+x5 因此，G(x)= (x6-1)/(x-1)是序列1，1，1，1，1，1的生成函数。 Example 3 设m是正整数。令ak=C( m, k) ,k=0,1,2,…m. 那么序列a0,a1,a2,…,am的生成函数是什么？ Solution：这个序列的生成函数是 G(x)=C(m,0)+C(m,1)x+C(m,2)x2+…+C(m,m)xm 由二项式定理 (x+y)n=C(n,0)xn+ C(n,1)xn-1y+C(n,2)xn-2y2+…+C(n,n-1)xyn-1+C(n,n)yn 可以证明G(x)=(1+x)m 由于使用生成函数求解计数问题时，忽略了这些级数的收敛问题，所以只是形式幂级数。 下面我们将叙述某些与无穷级数有关的重要事实，以用于研究生成函数。 Example 4 函数f (x)=1/(1-x)是序列1，1，1，1，... 的生成函数， 因为对|x|1，有 1/(1-x)=1+x+x2+… 【 Theorem 1 】 Example 6 设f(x)=1/(1-x)2. 用例4求出表达式 中的系数a0, a1, a2, …。 为了用生成函数求解许多重要的计数问题，需要在指数不是正整数的情况下应用二项式定理。 在叙述和定义广义二项式定理之前，我们先熟悉一下二项式定理。 二项式定理设x和y是变量，n是非负整数，那么Solution：在定义2中取u=-2和k=3得 类似地取u=1/2和k=3得 Example 8 当上边的参数是负整数时，广义二项式系数可以用通常的二项式系数的项表示。为此只需注意到 【 Theorem 2】广义二项式定理 设x是实数，|x|1, u是实数，那么 Example 9 当n是正整数时，使用广义二项式定理求(1+x) –n 和 (1-x) -n的生成函数。 生成函数可以用于计数各种类型的组合数。 在第4章中我们开发了一些技术计数n元素集合的允许重复的r组合数，在这些组合中可能存在某些附加的约束。这种问题与计数形如 e1+e2+e3+…+en=C方程的解是等价的，其中C是常数，每个ei是可能具有某些约束的非负整数。 这种类型的计数问题也可以用生成函数来求解。 Solution：具有上述限制的解的个数是 (x2+x3+x4+x4)(x3+x4+x5+x6)(x4+x5+x6+x7) 的展开式种x17的系数。这是因为我们在乘积中得到等于x17的项是通过在第一个和中取项 xe1,在第二个项中取项xe2,在第三个和中取项xe3，其中幂指数e1, e2, e3满 足方程 e1+e2+e3=17 和给定的限制。不难看出造这个乘积中的x17的系数是3.因此，存在3个解。 （注意，计算这个系数与枚举方程的具有给定约束的所有解几乎 要做同样的工作。但是，正如我们将看到的，这里说明的方法常 常可以用于求解各种各样的具有特殊规则的计数问题。此外，可 以用计算机代数系统做这种计算。） Solution：因为每个孩子至少接受2块饼干且不超过4块饼干，在关于序列{Cn}的生 成函数中对每个孩子存在一个等于 (x2+x3+x4) 的因式，其中Cn是分配n块饼干的方式数。因为存在3个孩子，这个生成函数是 (x2+x3+x4) 3我们要求这个乘积中的x8的系数，理由就是在展开式中x8的项对应于 选3项的方式数，其中每个因式选1项且指数加起来等于8.此外，来自第 一、第二和第三个因式的项的指数分别是第一、第二和第三个孩子接受 的饼干数。通过计算说明这个系数等于6. example 12 把价值1美元、2美元和5美元的代币插入售货机为价值r 美元的某种物品付款，使用生成函数确定在代币插入是有序的和无 序的两种情况下付款的方式数。 （例如为一种价值3美元的物品付款，当不考虑代币插入的次序 时存在2种方式：插入3个1美元的代币或1个1美元和1个2美元的代 币。当考虑代币的插入的次序时有3种方式：插入3个1美元的代币， 插入1个1美元代币然后1个2美元的代币，插入1个2美元代币然后1 个1美元代币。） Solution：在不考虑代币