계승진법

3. 성질

계승진법은 혼합 진법 기수법의 일종으로, 각 자릿수의 가중치가 팩토리얼로 증가하는 특징을 가진다. 즉, 오른쪽에서 ''i''번째 자릿수는 밑(기수)이 ''i''가 되며, 해당 자릿수에 올 수 있는 수는 0부터 ''i''-1까지이다. 각 자릿수의 값은 (''i'' − 1)! (해당 자리 값)을 곱한 값이다.

가장 오른쪽 자릿수는 항상 0이고, 두 번째 자릿수는 0 또는 1, 세 번째 자릿수는 0, 1, 2 중 하나가 되는 식이다. 팩토리얼 진법은 0! 자리가 항상 0이기 때문에 이 자리를 생략하여 정의하기도 한다.

예를 들어, 3:4:1:0:1:0_!는 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463₁₀을 의미한다.

혼합 기수 숫자 시스템의 일반적인 속성은 팩토리얼 숫자 시스템에도 적용된다. 예를 들어, 십진수를 팩토리얼 표현으로 변환하거나, 그 반대로 변환하는 것이 가능하다.

3. 1. 계승진법으로의 변환

• $b\_0\; =\; a$
• $a\_i\; \backslash equiv\; b\_\{i-1\}\; \backslash pmod\; i$
• $b\_i\; =\; \backslash lfloor\; b\_\{i-1\}\; /\; i\; \backslash rfloor$

따라서 463 = 341010_!이다.

463₁₀을 계승진법으로 변환하는 과정은 다음과 같이 나타낼 수도 있다.

몫이 0이 될 때까지 나눗셈을 반복하고, 나머지를 역순으로 나열하면 341010_!를 얻는다.

십진법 428을 계승진법으로 변환하는 과정은 다음과 같다.

마찬가지로 나머지를 아래에서부터 읽으면 428₁₀=323100_!이 된다.

3. 2. 순열과의 관계

• 크기 $k$의 집합 $\backslash Sigma$의 $m\_k$번째 원소가 $\backslash sigma(\backslash mathtt\; x\_0)$이다.
• 크기 $k-1$의 집합 $\backslash Sigma\backslash setminus\backslash sigma\backslash \{\backslash mathtt\; x\_0\backslash \}$의 $m\_\{k-1\}$번째 원소가 $\backslash sigma(\backslash mathtt\; x\_1)$이다.
• 일반적으로, 크기 $k-p$의 집합 $\backslash Sigma\backslash setminus\backslash sigma\backslash \{\backslash mathtt\; x\_0,\backslash mathtt\; x\_1,\backslash dotsc,\backslash mathtt\; x\_\{p-1\}\backslash \}$의 $m\_\{k-p\}$번째 원소가 $\backslash sigma(\backslash mathtt\; x\_p)$이다.
• 크기 2의 집합 $\backslash Sigma\backslash setminus\backslash sigma\backslash \{\backslash mathtt\; x\_0,\backslash dotsc,\backslash mathtt\; x\_\{k-3\}\backslash \}$의 $m\_2$번째 원소가 $\backslash sigma(\backslash mathtt\; x\_\{k-2\})$이다.
• 크기 1의 집합 $\backslash Sigma\backslash setminus\backslash sigma\backslash \{\backslash mathtt\; x\_0,\backslash dotsc,\backslash mathtt\; x\_\{k-2\}\backslash \}$의 $m\_1=0$번째 원소가 $\backslash sigma(\backslash mathtt\; x\_\{k-1\})$이다.

레머 코드를 이용하면 순열의 사전식 순서를 쉽게 계산할 수 있다. $n=3$일 때의 레머 코드는 다음 표와 같다.

4. 소수 (Fractional values)

계승 진법은 유리수를 표현하기 위해 소수점 아래 자릿값을 사용할 수 있다. 소수점 아래 n번째 자릿값은 $\backslash frac\{1\}\{n!\}$ 형태이다. 예를 들어, $1/2\; =\; 0.0\backslash \; 1\_!$, $1/3\; =\; 0.0\backslash \; 0\backslash \; 2\_!$ 등과 같이 표현된다.

다음은 십진법으로 표현된 유리수와 계승 진법으로 표현된 유리수를 비교한 표이다.

모든 유리수는 유한한 계승 진법 소수로 표현 가능하다.

일부 무리수는 계승 진법으로 변환했을 때 특징적인 소수 표시를 가진다. 예를 들어 다음과 같다.

• $e\; =\; 1\backslash \; 0.0\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1\backslash \; 1...\_!$
• $e^\{-1\}\; =\; 0.0\backslash \; 0\backslash \; 2\backslash \; 0\backslash \; 4\backslash \; 0\backslash \; 6\backslash \; 0\backslash \; 8\backslash \; 0\backslash \; A\backslash \; 0\backslash \; C\backslash \; 0\backslash \; E...\_!$
• $\backslash sin(1)\; =\; 0.0\backslash \; 1\backslash \; 2\backslash \; 0\backslash \; 0\backslash \; 5\backslash \; 6\backslash \; 0\backslash \; 0\backslash \; 9\backslash \; A\backslash \; 0\backslash \; 0\backslash \; D\backslash \; E...\_!$
• $\backslash cos(1)\; =\; 0.0\backslash \; 1\backslash \; 0\backslash \; 0\backslash \; 4\backslash \; 5\backslash \; 0\backslash \; 0\backslash \; 8\backslash \; 9\backslash \; 0\backslash \; 0\backslash \; C\backslash \; D\backslash \; 0...\_!$
• $\backslash sinh(1)\; =\; 1.0\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0...\_!$
• $\backslash cosh(1)\; =\; 1.0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1\backslash \; 0\backslash \; 1...\_!$

5. 역사

게오르크 칸토어가 1869년에 이미 자릿수마다 진법이 바뀌는 수 표기법에 대하여 연구하였다.^[6] 1888년에 샤를앙주 레장(Charles-Ange Laisant|샤를 앙주 레장^프랑스어, 1841〜1920)이 구체적으로 다루었으며, 순열과의 관계를 밝혔다.^[7]

6. 활용

계승진법은 순열의 조합론적 성질을 연구하는 데 활용된다. 정수가 계승진법으로 표현되었을 때, 정수 0, ..., n!−1 (또는 계승진법으로 n자리 수)과 사전식 순서에서의 n개 요소의 순열 사이에는 자연스러운 사상이 있으며, 이 사상은 레머 부호라고 불린다.^[1] 예를 들어 n=3인 경우, 사상은 다음 표와 같다.

계승진법은 컴퓨터 과학에서 순열 생성 알고리즘 등에 응용될 수 있다.

7. 소수 계승 진법

소수 계승 진법은 계승 진법과 유사한 기수법으로, n번째 자릿수의 가중치를 $p\_\{n-1\}\backslash \#$로 하는 것이다.

이 기수법의 유일성은 다음 항등식에 의해 보장된다.

:$\backslash sum\_\{i=0\}^\{n\}\; (p\_\{i+1\}\; -\; 1)\; \backslash cdot\; p\_i\backslash \#\; =\; p\_\{n+1\}\backslash \#\; -\; 1$

단, $n\backslash \#$는 소수 계승을 나타낸다.

참조

_[1] 서적 The Art of Computer Programming Addison-Wesley
_[2] 간행물 Zeitschrift für Mathematik und Physik
_[3] 서적 The Art of Computer Programming Addison-Wesley
_[4] 간행물 Sur la numération factorielle, application aux permutations http://www.numdam.or[...]
_[5] 간행물 Using Permutations in .NET for Improved Systems Security http://msdn2.microso[...] Microsoft Developer Network
_[6] 저널
_[7] 저널