二、有限多重集的r-组合数设多重集s={n1a1,n2a2,…,nk

二、有限多重集的r-组合数设多重集s={n1a1,n2a2,…,nk内容摘要：

5544  相邻禁位排列问题  定义：设集合 S={1,2,… ,n}， 如果 S的一个排列的任何两个相邻位置上不出现i,i+1(i=1,2,… ,n)的模式 ,则称该排列是 S的一个相邻禁位排列。 S的所有相邻禁位排列数记为 Qn。  当 n=1时 ， 只有一个数 ， 当然不相邻 ， 所以 Q1=1；  当 n=2时 ， 只能排成 2,1， 所以 Q2=1；  当 n=3时 ， 可排成 1,3,2或 2,1,3， 或 3,2,1,所以 Q3=3；  定理：对任意的正整数 n， 有  Qn=n!C(n1,1)(n1)!+C(n1,2)(n2)!… +(1)n1C(n1,n1)0!  证明：设 S={1,2,… ,n}， 用 X表示 S的所有排列集合 ， 则 |X|=n!。  对于 j=1,2,… ,n， 规定在一个排列中 ， 有j(j+1)出现 ， 则该排列具有性质 pj。  令 Aj表示具有性质 pj的所有排列集合。  则 S的相邻禁位排列全体是： 121 nAAA  例： 8人一列行走一天 ,现要变换位置 ,使得第 2天行走时 ,没有一个人的前面是第一天在他前面的人 ,求变换位置方式数 .  解：把这些人用 1,2,3,4,5,6,7,8按第一天的位置编号 ,排在最后的为 1,排在首位的为 8,则所求问题就是 8个数的相邻禁位排列问题 ,所以 Q8=8!C(7,1)(7)!+C(7,2)(6)! C(7,3)(5)!+C(7,4)(4)!C(7,5)(3)!+C(7,6)(2)!C(7,7)1!。  相邻禁位排列与错位排列之间有着密切的联系 :  Qn=Dn+Dn1  3. 相邻禁位环排列问题  定义：设集合 S={1,2,… ,n}， 如果 S的一个环排列的任何两个相邻位置上不出现i,i+1(i=1,2,… ,n)的模式 ,并且也没有出现n,1的模式 ,则称该环排列是 S的一个相邻禁位环排列。 S的所有相邻禁位环排列数记为 An。  当 n=1时 ， 只有一个数 ， 当然不相邻 ， 所以 A1=1；  当 n=2时 ， 无法满足要求 ,所以 A2=0；  定理：对任意的正整数 n， 有  An=(n1)!C(n,1)(n2)!+C(n,2)(n3)!… +(1)n1C(n,n1)0!+(1)nC(n,n)1!  例： 8个小孩坐在旋转的木马上 ,如果让他们交换位置 ,使得每个小孩前面都不是原来在他前面的孩子 ,问有多少种变换位置方式 ?  解：把这些孩子用 1,2,3,4,5,6,7,8编号 ,则所求问题就是 8个数的相邻禁位环排列问题 ,所以 Q8=7!C(8,1)(6)!+C(8,2)(5)!C(8,3)(4)!+C(8,4)(3)!C(8,5)(2)! +C(8,6)1! C(8,8)1!=1625。 第十二章 生成函数与递推关系 生成函数 (称为母函数 )是组合数学中的一个重要内容 ， 可用来求解组合计数问题。  在前面讨论多重集 S={n1a 1,n2a 2,… , nka k}(n=n1+n2+… +nk})的 r组合数时 ，  当对一切 i=1,2,… ,k有 nir时 ， 有计算公式 N=C(k+r1,r)；  当 rn， 且存在某个 nir,利用容斥原理予以解决。  利用下面的组合模型来模拟多重集的 r组合数  设有 n个标志为 1 , 2 , … , n的网袋 ， 第 i个(i=1,2,… n)网袋里放有 ni个球  (不同网袋里的球是不同的 ， 同一网袋里的球则是没有差别的 ， 认为是相同的 )。  因此多重集 S的一个 6组合 {a1a1a3a3a3a4}就相应于从第 1个网袋里取 2个球 ， 第 3个网袋里取 3个球 ， 第 4个网袋里取 1个球。  反之 ， 从第 1个网袋里取 2个球 ， 第 3个网袋里取 3个球 ， 第 4个网袋里取 1个球。 就对应了 S的一个 6组合 a1a1a3a3a3a4。  一般地 ， 多重集 S的 r组合数就等于从 n个网袋里取 r个球的取法数。  现在用 x代表球 ， xi1代表从第 1个网袋里取 i1个球 ， xi2代表从第 2个网袋里取 i2个球 ， … , xik代表从第 k个网袋里取 ik个球。  i1,i2,… ,ik 个 满 足 条 件 i1+i2+… +i。