一个空间的排列组合题.docVIP

解一道空间的排列组合题 （计算鲁班柱） 一个偶然的机会，看到一篇文章，内容是国外有人对中国传统智力玩具鲁班锁的计算机研究结果。其中有一条是：组成鲁班锁的元件——鲁班柱有837种柱形。即：在如下图的木条上有编号1——12的小方块，（图中黄色部分，9#，10#在2#，3#下方）在保证木条是一个整体的条件下，可以挖去任意数量和位置的小方块。挖去若干小方块后的木条就称为鲁班柱。由于挖去小方块数量与位置的不同，鲁班柱的形状也就不同。这样的形状共有837种。 我也查了不少有关鲁班锁的文章，无一人对此结果表示质疑，也无人进行过验证。一致表示认可。 我以为：中国传统的鲁班锁的计算研究，中国人有责任去进行计算研究和验证。 这就是一道排列组合题。不过它的领域扩展到了空间。 这也是一道全等形的问题，同样它的领域也扩展到了空间。 经过一段时间对此问题的研究和准备，我决定计算这个问题。 问题：在上图的木条中有12个编号为1——12的小立方体。在保证木条是一个整体的条件下，可以挖去任意数量和位置的小立方体。问：余下的部分共有多少种形状。 我的解题步骤是： 按一般排列组合的方法写出它的全组合。共2的12次方，为4095个不同数组。（空集不计） 排除断柱的的情况。如挖去（2，6，9，11）四块木条断成两段，称为断柱，应该排除。 合并等柱数组，只保留一个。即：虽然挖去小立方体的编号不同，但是留下的木条经旋转后形状相同的数组只保留一个。如：挖去（1，2）号小立方体的木条与挖去（7，8）号小立方体的木条，虽然数组不同，但是留下的两根木条经旋转后形状相同。所以只保留（1，2）号数组。 这三步计算完毕后，如果计算无误，即可得到结果。 为了计算与核对方便，将全部组合按挖去小立方体数量的多少分成12个组（0——11）计算。 解题前的准备工作。 排除断柱是解决这个问题的关键。 为了排除断柱，研究了出现断柱的情况。要出现断柱，至少要挖去4个小立方体。这样的数组有30个。我将它称为基本断柱组。这30个数组如下： （1，5，9，11）（1，6，9，11）（2，5，9，11）（2，6，9，11）（2，6，10，11）（2，6，10，12）（2，6，9，12）（2，7，9，11）（2，7，9，12）（2，7，10，12）（2，7，10，11）（3，6，9，11）（3，7，10，12）（3，7，9，11）（3，6，10，11）（3，6，9，12）（3。6。10。12）（3，7，9，12）（3，7，10，11）（3，8，10，12）（4，7，10，12）（4，8，10，12）（2，5，10，11） （4，7，10，11）（3，8，9，12）（1，6，9，12） （1，3，6，9）（2。4。7。10）（2，5，7，11）（3，6，8，12） 这30组基本断柱中，前26组挖去后，木条断成两段。后4组比较特殊，木条还是整的，但是，有一个小立方体会自动脱落。所以也归入基本断柱组。如：挖去（1，3，6，9）四个小立方体。2#小立方体就会脱落。对此4组基本断柱要特别小心处理。它们分别可使2#，3#，6#，7#小立方体脱落。 基本断柱组的用处：在基本断柱的基础上再挖去任意一个小立方体还是断柱。利用这个办法，很容易排除6块柱组和7块柱组（挖去5块）的大部分断柱。 一个小技巧；为了减小数字处理量，使每一个数组中的数字最少。将12组分成两类。第一类：1块组到5块组，用保留的小立方体的编号表示。第二类：6块组到12块组，用切去的小立方体的编号表示。这样处理，可使每一组数字的个数不会大于6。否则会出现最多一组有11或12个数字的现象。 为了快速的分开断柱，引入基本柱的概念。基本柱用保留的小立方体的编号表示。它定义为：在一个整柱数组中，只要再切去一个任意一个小立方体，整柱就会变成断柱。基础柱有很多。有了以下几组就够用了。它们是：（9，10）（11，12）（1，2，3，4）（5，6，7，8）（1，2，3，10）（2，3，4，9）（5，6，7，12）（6，7，8，11）（1，2，3，7，8）（2，3，4，5，6）（1，2，6，7，8）（3，4，5，6，7）（1，2，3，7，12）（2，3，4，6，11）（3，5，6，7，10）（2，6，7，8，11）。 基本柱的用途：在基本柱的基础上再添加小立方体依然是整柱。但必须考虑2#，3#，6#，7#小立方体添加不上的情况。如（9，10）组上添加1#，2#，3#，4#，5#，8#，11#，12#均可，6#，7#就不行。 4.为了合并等柱，编制了一份鲁班柱在各种旋转的情况下，各个小立方体编号变化对照表。 原编号 前翻90°后的编号 翻180°后的编号 后翻90°后的编号 旋转180°后的编号 旋转180°后再前翻90°的编号 旋转180°后再翻