常進制數
在我們的學習、生活中常進制數的套用非常廣泛。例如:十進制數、二進制數等等。實際上他們是以一個固定的整數作為進位值的。一般的,r 進制數就是每個位置滿r 進一。設有r 進制數A n,A n-1,A n-2,...,A 1,其中0=< A i<= r-1, 1<= i<=n, i位置的權重P i=r^( i-1)。其對應的數值K 計算方法為:
K = ΣA i*P i= A n*P n+A n-1*P n-1+...+A 1*P 1
階乘數系
最特殊、最簡單的變進制數,就是取B i= i+1, i>=1,則P i=1 *2*...*(i-1)*i =i!,其權重恰好是整數的階乘,因而被稱為階乘數。階乘數第 i個位置最大數值是 i。
例,4位的最大階乘數是4321,為了區分其他進制,這裡用字母f作為下標:(4321)_f ,則:
(4321)_f = 4*4!+3*3!+2*2!+1*1! = 119 = 120-1 = 5!-1 =(10000)_f -1
上式在10進制中相當於:9999 = 9*10^3+9*10^2+9*10+9*1 = 10000-1
我在2006年探討全排列的排序問題時也獨立的發現變進制數和階乘數系,後來在一本數值計算的書上看到了這個概念,估計這個概念應該出現很久了,因為不常用而被忽視。
全排列和階乘數系關係
我們知道n個不同的元素有n!個排列,我們這裡考慮數字1,2,...,n的排列。現在我們要給他們一個排序方法,也即是找到他們和自然數列0,1, 2, ..., n!-1 的一個對應,習慣上的,我們按照排列逆序的程度來排序。我們來逐一考慮,n=1時,只有1中排列,n=2時,我們要把2和1排在一起,則2可以排在1的後面或前面,有兩種選擇,當n=3時,1和2兩個數字有三個空可以插入數字3,而3選定一個位置時,1和2又有2!種排列,我們可以這樣,數字3每變動一次(從後向前移),小於它的所有數就輪換了一個周期(全排列)。這6個排列順序如下:
(數字3在第3個位置)123, 213, (數字3在前移了1位)132, 231, (數字3又前移了1位)312, 321
數字3每前移一個位置,就經過了2!個排列。
一般的,按照這個方法,我們就可以把n!個排列排出來,在這種排列方法中,我們發現數字i 每前移一次,就經過了(i-1)! 個排列,也就是說“數字i 的位置的權重是(i-1)! ”,而i 移動的次數取決與在該排列中
數字i 右側小於i 的數字的個數(逆序)
例:有排列 35241 ,我們從數字2開始看,2右側有1個比它小的數字,數字3右側有2個,數字4右側有1個,數字5右側有3個,我們將這些逆序數倒著寫下來是:3,1,2,1,則該序列在我們這種排序方法中的位置序號是:
3*(5-1)!+1*(4-1)!+2*(3-1)!+1*(2-1)! = 3*4!+1*3!+2*2!+1*1! = 83 注意,排序是從0開始計數的。
我們就發現一個排列的逆序數組成的數列恰好是一個階乘數,此例中就是(3121)_f 。特殊的排列1234...n 對應的是(0, 0,..., 0)_f = 0 即是第一個,n(n-1)...21對應的是(n-1, n-2, ..., 2, 1)_f = n!-1,即是最後一個,完全符合我們的排序意圖。該階乘數各個位置數字的和就是原排列的總的逆序數。多提一點,鑒於這種逆序數列和階乘數的關係,我希望幾年後,組合數學書上的逆序數列可以修改成我這裡的定義方式:數字i 右側小於i 的數字的個數。而不是:i 左側大於i 的數字的個數。當然,大多數意義下兩者是等效的。
綜上所述: n個元素的全排列可以和n-1位的階乘數一一對應起來。
階乘數系的小數推廣和負數的階乘
進一步考慮,我們可以擴展出階乘數系的小數計數法。實際上我們的任務是去 劃分單位1,與整數計數法相似,可以定義一個大於等於2的整數列C 1,C 2,...,C n,...作為劃分的等分數,這裡就不做闡述了,我們這裡一種特殊的擴展方法: 對稱擴展法,即令C i=B i, i>=1。對比常進制數的小數計數法,小數實際上是每次把當前長度10等分,於是,在階乘數的計數法中C i=B i= i+1 , i>=1,我們最初我們將單位1進行2等分,再對每一份(長度是1/2)進行3等分(變成了1/6),如此下去,無窮的劃分。於是,第i 次劃分後,每一份的長度是1/(i+1)!, 這即是對稱擴展後小數點後第 i位置的權重, 第i個位小數的最大數值是i。小數點後第 i位置的權重P -i= 1/( i+1)! , i>=0。
例如:最大的4位小數是(0.1234)_f , (0.1234)_f = 1/2!+2/3!+3/4!+4/5! = 119/120 = 0.991666666.....
至此,階乘數的小數系統也構造完畢。並且,我們可以得出一個有趣的級數:
Σn/(n+1)! = 1 , 其中Σ是對n是從1到正無窮求和。 他的意義很明確,就是(0.123456......)_f = 1,正如十進制中的0.999999......=1一樣。
大膽的,鑒於上述小數和整數權重表示的統一,我們可以定義
負數的階乘
(-n)! = 1/(n+1)! , 其中n>=0。
這裡我們發現,0!是符合這個公式的:0!=1/1!=1。則階乘數系第i 位置的權重P i= i! , i是任意整數。對於整階乘數,實際上在最低位置右邊還有一個“隱藏位置”,該位置的數值只能是0,權重是0!=1,因而無計數意義,我們可以把它想像成小數點,小數點右邊就是小數系統,很完美的合在一起:
(n,n-1,...21.123456......)_f = (n+1)! , 對應十進制是9999.9999...=10000。
說明:這裡負數的階乘的定義是根據對稱擴展而來,能夠吻合0的階乘且能夠完善階乘數系的表示,暫時沒有發現它對其它組合公式有什麼擴展貢獻。