不妨把問(wèn)題用數(shù)列來(lái)敘述,即求滿足如下條件的數(shù)列的個(gè)數(shù).
① 數(shù)列各項(xiàng)為0~n-1的整數(shù),且各不相同.
② 除首項(xiàng)外,每一項(xiàng)均與前面某項(xiàng)相差±1.
③ 數(shù)列的首項(xiàng)不為0.
過(guò)程分三步.
首先,設(shè)滿足①,②且長(zhǎng)度為n的數(shù)列的個(gè)數(shù)為a[n].
對(duì)于長(zhǎng)為n的數(shù)列,考慮其前n-1項(xiàng),可不重不漏的分為兩種情況.
(1) 各項(xiàng)為0~n-2的整數(shù),且各不相同.
(2) 各項(xiàng)為1~n-1的整數(shù),且各不相同.
由a[n]的定義,滿足(1),②且長(zhǎng)度為n-1的數(shù)列的個(gè)數(shù)為a[n-1].
而滿足(2),②且長(zhǎng)度為n-1的數(shù)列的個(gè)數(shù)也為a[n-1].
易見(jiàn),這些長(zhǎng)為n-1的數(shù)列可以唯一的延長(zhǎng)為一個(gè)滿足①,②的長(zhǎng)度為n的數(shù)列.
不同的數(shù)列延長(zhǎng)后仍不同,且所有滿足①,②的長(zhǎng)度為n的數(shù)列都能這樣延長(zhǎng)得到.
于是a[n] = 2a[n-1].由a[2] = 2 (包括01和10),可得a[n] = 2^(n-1).
其次,考慮滿足①,②的長(zhǎng)度不限的數(shù)列的個(gè)數(shù).
其中長(zhǎng)度為k的數(shù)列可以分為n-k+1類.分別由0~k-1,k,k+1,...,n-k~n-1的整數(shù)組成.
每類有a[k] = 2^(k-1)個(gè)數(shù)列,總共有(n-k+1)·2^(k-1)個(gè).
總數(shù)為2^(n-1)+2·2^(n-2)+3·2^(n-3)+...+n·2^0 = (2^n-1)+(2^(n-1)-1)+...+(2^1-1) = 2^(n+1)-n-2.
最后,在上述數(shù)列中,首項(xiàng)為0的有n個(gè):0,01,012,...,012...(n-1).
于是滿足①,②,③的數(shù)列共有2^(n+1)-2n-2個(gè).
即滿足條件的n進(jìn)制整數(shù)有2^(n+1)-2n-2個(gè).