或稱康托展開
X=a[n-1]*(n-1)!+...+a[2]*2!+a[1]*1!
其中，a為整數，並且0<=a<i,i=1,2,..,n
它構成一個全排列到一個整數的雙射。
例：
{1,2,3,4,...,n}表示1,2,3,...,n的排列如
{1,2,3}
按從小到大排列一共6個
123
132
213
231
312
321
代表的數字
1
2
3
4
5
6
也就是把10進制數與一個排列對應起來。他們間的對應關係可由康托展開來找到。
如我想知道321是{1,2,3}中第幾個大的數可以這樣考慮
第一位是3，當第一位的數小於3時，那排列數小於321
如
123
213
小於3的數有1，2
所以有2*2!個
再看小於第二位2的
小於2的數只有一個就是1
所以有1*1!=1
所以小於321的{1,2,3}排列數有2*2!+1*1!=5個所以321是第6個大的數。
2*2!+1*1!是康托展開
再舉個例子
1324是{1,2,3,4}排列數中第幾個大的數
第一位是1小於1的數沒有，是0個
0*3!
第二位是3小於3的數有1，2但1已經在第一位了所以只有一個數2
1*2!
第三位是2小於2的數是1，但1在第一位所以有0個數
0*1!
所以比1324小的排列有0*3!+1*2!+0*1!=2個
1324是第三個大數。
英文介紹：
Every nonnegative integer less than n! has a unique Cantor expansion
all! + a22! + ... + an-1(n - 1)!
where ai is a nonnegative integer not exceeding i, for i = 1, 2, . . . , n 1. The integers al, a2, . . . , an-1 are called the Cantor digits of this integer.
Given a permutation of {l, 2, ... , n}, let ak-1, k = 2, 3, . . . , n, be the number of integers less than k that follow k in the permutation. For instance, in the permutation 43215, al is the number of integers less than 2 that follow 2, so that al = 1. Similarly, for this example a2 = 2, a3 = 3, and a4 = 0. The number associated with this permutation will thus be: 1x1! + 2x2! + 3x3! = 23. Consider the function from the set of permutations {l, 2, 3, ... , n} to the set of nonnegative integers less than n! that sends a permutation to the integer that has al, a2, ... , an-1, defined in this way, as its Cantor digits.
This is actually a bijection f: P¬n {0, …, n! – 1}.
To find the permutation P8 such that f() = 2001 we proceed as follows:
a. Find the Cantor digits of : 2001 = 2*6! + 4*5! + 3*4! + 1*3! + 1*2! + 1*1!
b. Construct the permutation by inserting 8, then 7 and so on.
= 8}
7 * * 8} (a6 = 2, two numbers < 7 come after 7)
6 * * 7 * * 8} (a5 = 4, four numbers < 6 come after 6)
6 5 * 7 * * 8} (a4 = 3, three numbers < 5 come after 5)
6 5 * 7 4 * 8} (a3 = 1, one number < 4 comes after 4)
6 5 3 7 4 * 8} (a2 = 1, one number < 3 comes after 3)
2 6 5 3 7 4 * 8} (a1 = 1, one number < 2 comes after 2)
= {2 6 5 3 7 4 1 8}
Comment: The algorithm for finding the Cantor digits of an integer n is a “Greedy” algorithm.
