it技术南开大学acm暑期集训之组合数学(编辑修改稿)

it技术南开大学acm暑期集训之组合数学(编辑修改稿)内容摘要：

119   nnn abb{ 1 ,8 11  ba)222(  也有类似解释。 递推关系 (222)式中的 表达了含有偶数个 5的 n位十进制数的两个组成部分。 表达由含有偶数个 5的 n1位十进制数 ，令 取 5以外的 0， 1， 2， 3， 4，6， 7， 8， 9九个数中的一个数构成的。 项表示当 是含有奇数个 5的 n1位十进制数，令 而得 是含偶数个 5的 n位十进制数。 119   nnn abb119   nnn baa19 na121 nppp  np1nb121 nppp 5np nppp 21 (222)是关于序列 和 的连立关系。 递推关系 设序列 的母函数为 ，序列 的母函数为。 }{ na }{ nb}{ na )(xA }{ nb)(xB22122123212321)( )99)(9 )( )( xbxbxxBxaxaxxAxbxbbxBxaxaaxA即： _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _8)()()91(  xxBxAx递推关系 承前页：  )9 : 9 : 9 : 33432232112baaxbaaxbaax___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _)()(98)( xxBxxAxA 8)()()91(  xxBxAx递推关系 又： ___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _1)()()91(  xxAxBx故得关于母函数 和 得连立方程组： )(xA )(xB1)()91()(8)()()91(xBxxxAxxBxAx{2212212321)( )99)(9)(xaxaxxAxbxbxxBxbxbxbxB递推关系 xxxxD91 91  xx  )91( 280181 xx )101)(81( xx )101)(81(87191 18801811)(2 xxxxxxxxA)101)(81(118 91)101)(81(1)(xxxxxxxxB递推关系 0)10987(21)101 981 7(21)( kkkk xxxxA11 1029827   kkka递推关系 解法二： n1位的十进制数的全体共 从中去掉含有偶数个 5的数，余下的便是 n1位中含有奇数个 5的数。 故有： 2109  n121111099nnnnnnabbaa8 ,1098 121   aaa nnn递推关系 令 221232188)(8 ))(xaxaxxAxaxaaxA___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ 22312 )8()8(8)()81( xaaxaaxAx递推关系 xxxxxxxAx10171810198 10998)()81( 2 0)10987(21 )1019817(21)101)(101(718)( kkkkxxxxxxxA11 1029827   kka母函数和递推关系应用举例 例 6： 设有 n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。 求这样的 n条曲线把平面分割成几个部分。 设满足条件的 n条封闭 曲线所分割成的域的数目为 ，其中 条封闭曲线 所分割成的域的数目为 图 283 na 1n1na母函数和递推关系应用举例 第 n条封闭曲线和这些曲线相交于 个点，这 个点把第 n条封闭曲线截成 条。