小朋友学奥数（21）：康托展开

一、康托展开运算

把一个整数X展开成如下形式： X = an * (n - 1)! + an-1 * (n - 2)! + … + ai * (i - 1)! + … + a2 * 1! + a1 * 0! 其中，ai为整数，并且0 <= ai < i，1 <= i <= n)。 ai表示原数的第i位在当前未出现的元素中是排在第几个。

康托展开的最基本应用就是求一个排列（按字典序）的序号（即第几个）。而其逆运算就是求序号对应的排列。

二、例子

例1：n = 3时，即三位数字的全排列，321的序号是多少？

方法一： 1 2 3这三个数按字典序来进行排列，得：

123
132
213
213
312
321

这里可以看出321是第6个数。

方法二： 321的第一位是3，则第一位小于3的数一定排在321的后面，这样的排列有22！个。 321的第二位是2，则第一位等于3第二位小于2的数一定排在321的后面，这样的排列有11!个。 321的第三位是1，则第一位为3第二位为2第3位小于1的数一定排在321的后面，这样的排列有0个。 所以排在321前面的数有2 * 2! + 1 * 1! = 5个。321是第5 + 1 = 6个数。

例2：对于n = 3的全排列，第6个数是多少？

分析： 现将序号减去1，为5。 5/2！=2余1，说明比第一位数小的数有2个，那么第一位肯定为3。 上一步的余数/1! = 1/1!=1余0，说明比第二位小的数有1个，那么第二位肯定是2。 第三为只能为1了。 所以第6个数是321。

例3：n = 4的全排列中，1324是第几个数？

1324的第一位是1，小于1的数有0个，所以总共有 0 * 3! = 0个。 1324的第二位是3，小于3的数有1和2，但1已经在第一位了，所以只有一个数2。再考虑第三位和第四位的排列数为2!，所以共有 12! = 2个。 1324的第三位是2，小于2的数是1，但1已经排在第一位了，所以有0个数 。 01! = 0。 所以比1324小的排列有0 * 3! + 1 * 2! + 0 * 1! = 2个。 综上，1324是的序号为2 + 1 = 3。

例4：对于n = 6的全排列，153426的序号是多少？再往后数200个，得到的数是多少？

① 153426的第一位数是1，比1小的数有0个，共有0 * 5！= 0个。 153426的第二位数是5，比5小的数有4个，但是1已经出现在首位了，所以只有2，3，4这三个。共有3 * 4！= 72个。 153426的第三位数是3，比3小的数有2个，但是1已经出现在首位了，所以只有2这1个。共有1 * 3！= 6个。 153426的第四位数是4，比4小的数有3个，但是1和3已经出现在首位和第三位了，所以只有2这1个。共有1 * 2！= 2个。 153426的第五位数是2，比2小的数有1个，但是1已经出现在首位了，所以共有0 * 1！= 0个。 153426的第六位数是6，比6小的数有5个，但是这5个数已经被前五位数占了，所以共有0 * 0！= 0个。 综上，153426排在第72 + 6 + 2 + 1 = 81个。

② 第81个再往后数200个，就是第281个。 首先将281减去1，即280。 第一位为280 / 5! = 2余40，说明比第一位数小的数有2个，则第一位数必为3 上一步的余数 / 4! = 40 / 4! = 1余16，说明比第二位数小的数有1个，第二位数必为2。 上一步的余数 / 3! = 16 / 3！= 2余4，说明比第三位数小的数有2个。在前两位数是3和2的前提下，第三位只能为5，这样比它小的两个数为1或4。 上一步的余数为 4/ 2! = 2余0 ，说明比第四位数小的数有2个。因为前三位数分别为3、2、5，则第四位数必为6。 上一步的余数为 0/1! = 0余0 ，说明比第五位数小的数有0个，则第五位数必为1。 剩下一位数为4。 综上，153426往后数的第200个数是325614。