从圆排列的相嵌到组合的枚举

【www.zhangdahai.com--其他范文】

【摘要】国内外的《组合数学》中，有的还没有讨论圆排列问题，更没有讨论圆排列的相对计数法和圆排列相嵌问题.本文引入这两种新概念，利用新发现的圆排列相嵌与线排列相嵌的关系，才完成命题的证明，解决了两种元素的圆排列的枚举问题，这也可以说明圆排列理论基本成熟，同时也为组合枚举提供了一种具有理论依据的新方法，这里不做实例演示，只给出理论证明和枚举所需的步骤.

【关键词】圆排列；线排列；相嵌；相对数之和

预备知识

(A)f，g是以n的约数为变量的函数，d是主变量，k是负变量，则有：

①fnd=∑k|ndgndkgnd=∑k|ndu(k)fndk；

②∑d|nd∑k|ndu(k)fndk=∑d|n(d)fnd.

（B）a1元素有n1个，a2元素有n2个，…，ai元素有ni个，n1+n2+…+ni=N，D是n1，n2，…，ni的最大公约数，D≥1，N个元素的圆排列的总数是1N∑d|D(d)Nd!n1d!n2d!…nid!.

定义 不改变圆排列元素的顺序，将所有元素平均分成元素相同，排列顺序相同的若干组，并且使所分的组数是最多的，每组元素的个数称为圆排列的周期，组数的倒数称为圆排列的相对数；不能够进行分组的圆排列称为整圆排，能够进行分组的圆排列称为分圆排.

整圆排的周期等于元素总数，相对数是一.相对数之和与线排列的关系：多种周期、任意数量的圆排列的相对数之和（每个圆排列的元素总数均为N）乘以N，等于这些圆排列展开所产生的线排列之和，这是因为任意一个圆排列展开所产生的线排列数，等于这个圆排列的周期.

规定 圆排列展开变成线排列，要顺时针展开，线排列变成圆排列，元素也要顺时针摆放.

圆排列性质 （1）一个周期为k的分圆排，任意取k个连续的元素，不改变原有顺序所组成的新圆排列，每次都相同，且是整圆排.（2）任意一个圆排列展开所产生的任意一个线排列，复制k个再组成一个分圆排，每一个线排列所组成的分圆排均相同，且周期与原圆排列相同.

(C)n无序拆分成k个正整数之和，即a1+a2+…+ak=n（a1≥a2≥…≥ak≥1）.n有序拆分成k个正整数之和，即a1+a2+…+ak=n有Ck-1n-1组正整数解.无序拆分与有序拆分的关系：每一个无序拆分都进行线排列，k个数字的线排列之和就是有序拆分数Ck-1n-1.

说明 本文中u（k）表示Mbius函数，(d)表示Euler函数.A（全部）,B（部分）出自本人的论文，新恒等式与Mbius反演公式的新理解及其在圆排列计数中的应用［J］.数学学习与研究2009年第四期（下半月刊）.

引 言

从n+m个不同数字中，取m个数字的组合数，与n个黑球、m个红球的线排列数是相等的，这里通过圆排列使得组合与线排列形成具有规律的对应关系.两个同心圆，将1，2，3，…，n+m从小到大均匀的放在一个圆周上，将n个黑球m个红球的任意一个整圆排放在另一个圆周上，整圆排每转动一个数字的距离，m个红球所对应的m个数字就是一个组合，转动一周可以得到m+n个不同的组合；如果是分圆排转动一周，得到的组合个数与分圆排的周期相等，因此任意一个圆排列转动一周所得到的组合数，与这个圆排列所产生的线排列数是相等的.绝大多数圆排列正反面是不同的，因此很多圆排列的反面转动一周，也可得到与周期相等的组合数，因此互为正反面的两个圆排列，只需保留一个.由以上可知组合的枚举，关键是两种元素的圆排列的枚举.

定义 两个圆排列的元素个数相等，不改变元素的顺序，将一个圆排列的元素，放在另一个圆排列的元素之间，且每个位置只能放一个元素，这就称做两个圆排列的相嵌.

命题1 d1与d2的最大公约数是r，周期分别是nd1，nd2的两个圆排列之间不存在相同的元素，相嵌可得到周期是2的圆排列d1d2个.

理解说明 d1，d2，r是可以等于一的，n是元素个数.

证明 两个圆排列的元素，从任意一个元素开始都可以分成完全相同的r组，r是d1，d2的最大公约数，因此两个圆排列的元素，在所分的组数相等，每组元素完全相同的条件下，r组是最多的，所以两个圆排列相嵌，所得到新圆排列的周期均为2.

两个圆排列相嵌，可转化成nd1个线排列与nd2个线排列的相嵌，可组成n2d1d2对线排列进行相嵌，每对线排列相嵌可得到两个新线排列，因此得到新线排列的总数是2n2d1d2个，因而新圆排列的个数是2n2d1d2÷2=d1d2.

推论1 两个相等的同心圆，从一点起将一圆周d1等分，另一个圆周d2等分，将一圆任意转动，若d1与d2的最大公约数是r，则每转动360rd1d2度就有r个重合点均分两圆.

证明 略.

提示 d1，d2，r是可以等于一的.起点视为重合点.

将两个圆排列放在同心圆的位置进行相嵌，在得到d1d2个新圆排列的过程中，有一个圆排列转动了d1d2个元素的距离，d1d2个元素所对应的圆心角就是360n×d1d2=360rd1d2度.

推论2 两组圆排列之间不存在相同的元素，且每一个圆排列的元素个数均相等，两组圆排列展开的线排列之和分别是A和B，若一组中的每一个圆排列都与另一组所有的圆排列进行相嵌，则得到新圆排列展开的线排列之和是2AB.

证明 略.

命题2 n个黑球、m个红球分别分成k组排列在圆周上，每组至少有一个球，并且使相邻两组的小球不同色，D是n，m，k的最大公约数，n≥m≥k≥1，D≥1.

（1）符合条件的圆排列展开所产生的线排列数是

n+mkCk-1n-1Ck-1m-1.

（2）符合条件的圆排列数是

1k∑d|D(d)Cnd-1，kd-1Cmd-1，kd-1.

证明 （1）n个黑球分成k组，k组可以理解成k个黑色数字，由有序拆分可知k个黑色数字的线排列之和是Ck-1n-1，m个红球分成k组，k个红色数字的线排列之和是Ck-1m-1，红色数字的圆排列与黑色数字的圆排列相嵌，可转化成Ck-1n-1Ck-1m-1对线排列相嵌，每对线排列相嵌可得到两个新线排列，新线排列数是2Ck-1n-1Ck-1m-1，每个新线排列的数字有2k个，因此新圆排列的相对数之和是1kCk-1n-1Ck-1m-1，任意一个新圆排列的数字，用相应的小球取代，这两个圆排列的相对数是相等的.因此，n个黑球m个红球的圆排列，相对数之和也是1kCk-1n-1Ck-1m-1，即有符合条件的线排列数是n+mkCk-1n-1Ck-1m-1.

（2）令d是n，m，k的公约数，nd个黑球分成kd组，kd个黑色数字的线排列之和是Cnd-1，kd-1，md个红球分成kd组，kd个红色数字的线排列之和是Cmd-1，kd-1，黑色数字的线排列与红色数字的线排列相嵌，可得到2kd个数字的线排列2Cnd-1，kd-1Cmd-1，kd-1个.

令h是Dd的一个约数，函数MDdh表示2kd个数字，周期是2kdh的圆排列的个数，函数fDd表示2kd个数字的线排列之和，则有：

fDd=∑h|Dd2kdhMDdh

=2Cnd-1，kd-1Cmd-1，kd-1.①

令gDdh=2kdhMDdh，当h=1时，gDd=2kdMDd，由上面的题设可知MDd表示2kd个数字的整圆排的个数，由圆排列的性质可知MDd也可表示2k个数字周期是2kd的圆排列的数量，2k个数字的圆排列总数是∑d|DMDd，由①式可得

fDd=∑h|DdgDdh

gDd=∑h|Ddu(h)fDdh=2kdMDd

MDd=d2k∑h|Ddu(h)fDdh

∑d|DMDd=∑d|Dd2k∑h|Ddu(h)fDdh

=12k∑d|Dd∑h|Ddu(h)fDdh=12k∑d|D(d)fDd

=1k∑d|D(d)Cnd-1，kd-1•Cmd-1，kd-1.

因2k个数字的圆排列，与n个黑球m个红球的圆排列是一一对应的关系，因此上式也可以表示两种小球的圆排列数.

理解说明 命题2要求n≥m≥k≥1，k的所有可取的值是：1，2，…，m，因此∑mk=1n+mkCk-1n-1Ck-1m-1是n+m个小球的线全排列，∑mk=11k∑d|D(d)Cnd-1，kd-1Cmd-1，kd-1是n+m个小球的圆全排列，因而有下面两个等式.

圆全排列展开的线排列之和等于线全排列，是圆排列的理论基础，在本文所提到的论文中，也有一点论述；命题二的证明还是在这个基础上所进行的，每个无序折分都有一组圆全排列和一组线全排列，所有无序折分的圆全排列之和与线全排列之和，也符合理论基础的要求，推论中第二个等式的成立，验证了这个理论基础的正确性，同时也说明了对圆排列一些基本特性的认识，绝大多数是正确的，因此这个等式的出现是圆排列理论成熟的标志.

推论 （1）Cmn+m=(n+m)∑mk=11kCk-1n-1Ck-1m-1(n≥m).

（2）1n+m∑d|(n，m)(d)Cn+md，md=

∑mk=11k∑d|(n，m，k)(d)Cnd-1，kd-1•Cmd-1，kd-1(n≥m).

枚举步骤

（1）用黑色笔写出x1+x2+…+xk=n的无序拆分，每一个无序拆分就是k个黑色数字，并标出每个无序拆分的线排列数，只有当所有的线排列之和等于Ck-1n-1时，才说明无序拆分没有多写也没有少写.

（2）将线排列数相等的无序拆分归为一类，只要写出一个无序拆分的所有圆排列，这一类无序拆分的圆排列，都可以参照很容易写出，两个互为正反面的圆排列只需保留一个.

（3）同理，用红色笔写出y1+y2+…+yk=m的无序拆分，并写出每一个无序拆分的圆排列，两个互为正反面的圆排列只需保留一个.

（4）每个黑色数字的圆排列，与所有红色数字的圆排列相嵌，每对圆排列相嵌所产生新圆排列的个数由命题1确定.

①两个正反面不同的圆排列相嵌，正面与正面相嵌完成以后，再进行一轮正反面相嵌，所得到的每一个新圆排列都表示两个圆排列.②一个正反面不同的圆排列，与一个正反面相同的圆排列相嵌，只需正面与正面相嵌，所得到的每一个新圆排列都表示两个圆排列.③两个正反面相同的圆排列相嵌，只需正面与正面相嵌，所得到的每一个新圆排列，只表示一个圆排列，存在互为正反面的圆排列，有的也存在正反面相同的圆排列.

（5）黑色数字、红色数字的每一个圆排列，黑色数字是几就用几个黑球取代，红色数字是几就用几个红球取代，再利用引言中的方法操作，就可以得到相对应的组合.

注意事项 任意一个正反面不同的圆排列，一定存在一个圆排列是它的反面，这两个圆排列反面与反面合在一起，可以做到所有相同的元素所处的位置也相同.

若一个整圆排正反面是相同的，圆周上的元素以一条直径相对称，且对称位置的元素是相同的.如果把这个整圆排展开，任意取一个线排列复制k个，再组成一个分圆排，这个分圆排正反面也是相同的.在圆全排列中存在正反面相同的圆排列，最多只能有两种元素的个数是单数.

【参考文献】

［1］马光思.组合数学［M］.西安电子科技大学出版社，2002.

［2］卢开澄，卢华明.组合数学［M］.北京：清华大学出版社，2006.

［3］［美］格里马迪（Grimaldi，R）.林永钢译.离散数学与组合数学［M］.北京：清华大学出版社，2007.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

推荐访问:组合 枚举 排列 相嵌到