계승진법

수학에서 **계승진법**(階乘進法, factorial number system, factoradic system)은 자연수를 계승들의 합으로 표기하는 표기법이다. 이를 통해 순열들의 집합 위의 전순서를 쉽게 매길 수 있다. 학교 내신 문제에서 주로 나오는 사전식 배열 문제를 풀 때도 용이하다.
# 정의
**계승진법**에서, 자연수 a\in\mathbb N는 다음과 같은 꼴로 표현된다. :a = (\dotso a_4a_3a_2a_1)_! = \sum_{i=0}^\infty a_{i+1} i! 여기서 :a_i \in \\{0,1,\dotsc,i-1\\} 이다. 특히, 마지막 자리 a_1의 값은 항상 0이다. 예를 들어, :341010_! = 3 \times 5! + 4 \times 4! + 1 \times 3! + 0 \times 2! + 1\times1! + 0\times 0! = 463 이다.
# 성질

## 계승진법으로의 변환
자연수 a\in\mathbb N의 계승진법 표기 :(\dotso a_4a_3a_2a_1)_! 는 다음과 같은 재귀적 알고리즘으로 주어진다. :b_0 = a :a_i \equiv b_{i-1} \pmod i :b_i = \lfloor b_{i-1} / i \rfloor 예를 들어, 463의 계승진법 표현은 다음과 같다. {| |- ! *b**'i*−1 || = || *b**'i* || × || *i* || + || *a**i* |- | 463 || = || 463 || × || 1 || + || 0 |- | || ↙ |- | 463 || = || 231 || × || 2 || + || 1 |- | || ↙ |- | 231 || = || 77 || × || 3 || + || 0 |- | || ↙ |- | 77 || = || 19 || × || 4 || + || 1 |- | || ↙ |- | 19 || = || 3 || × || 5 || + || 4 |- | || ↙ |- | 3 || = || 0 || × || 6 || + || 3 |- | || ↙ |- | 0 || = || 0 || × || 7 || + || 0 |- | || ↙ |- | 0 || = || 0 || × || 8 || + || 0 |- |- | || ↙ |- | ⋮|| || ⋮ || || ⋮ || || ⋮ |} 즉, :463 = 341010! 이다.
## 순열과의 관계
계승진법을 사용하여, 크기 n의 알파벳 :\Sigma=\\{\mathtt x_0,\mathtt x_1,\dotsc,\mathtt x_{k-1}\\} 의 순열들의 집합(대칭군) :\operatorname{Sym}(\Sigma) 과 자연수 집합 :\\{0,1,\dotsc,k!-1\\} 사이의 표준적인 전단사 함수를 정의할 수 있다. 구체적으로, 자연수 0 \le m \le k! - 1를 k자릿수의 계승진법으로 표기하였을 때 :m=(m_km_{k-1}\dotsc m_2m_1)_! 라고 하자. 그렇다면, m에 대응하는 순열 :m \colon \Sigma \to \Sigma 은 다음과 같은 알고리즘에 의하여 주어진다. * 크기 k의 집합 \Sigma의 m_k번째 원소가 \sigma(\mathtt x_0)이다. * 크기 k-1의 집합 \Sigma\setminus\sigma\\{\mathtt x_0\\}의 m_{k-1}번째 원소가 \sigma(\mathtt x_1)이다. * ⋮ * 일반적으로, 크기 k-p의 집합 \Sigma\setminus\sigma\\{\mathtt x_0,\mathtt x_1,\dotsc,\mathtt x_{p-1}\\}의 m_{k-p}번째 원소가 \sigma(\mathtt x_p)이다. * ⋮ * 크기 2의 집합 \Sigma\setminus\sigma\\{\mathtt x_0,\dotsc,\mathtt x_{k-3}\\}의 m_2번째 원소가 \sigma(\mathtt x_{k-2})이다. * 크기 1의 집합 \Sigma\setminus\sigma\\{\mathtt x_0,\dotsc,\mathtt x_{k-2}\\}의 m_1=0번째 원소가 \sigma(\mathtt x_{k-1})이다. (\Sigma\setminus\sigma\\{\mathtt x_0,\dotsc,\mathtt x_{k-2}\\}에서 이미 원소가 하나 밖에 남지 않았으므로 이 단계는 자명하다.) 이 알고리즘에서, ‘집합의 〜번째 원소’란 0번째부터 센다. 예를 들어, n=3일 때, 수 {0,1,2,3,4,5}와 알파벳 \\{\mathtt x_0,\mathtt x_1,\mathtt x_2\\} 위의 순열 사이의 대응은 다음과 같다. {| class=wikitable ! 수 !! 멱승진법 !! 순열 |- | 0 || 000! || \begin{pmatrix} \mathtt x_0&\mathtt x_1&\mathtt x_2 \\\ \mathtt x_0&\mathtt x_1&\mathtt x_2 \\\ \end{pmatrix} |- | 1 || 010! || \begin{pmatrix} \mathtt x_0&\mathtt x_1&\mathtt x_2 \\\ \mathtt x_0&\mathtt x_2&\mathtt x_1 \\\ \end{pmatrix} |- | 2 || 100! || \begin{pmatrix} \mathtt x_0&\mathtt x_1&\mathtt x_2 \\\ \mathtt x_1&\mathtt x_0&\mathtt x_2 \\\ \end{pmatrix} |- | 3 || 110! || \begin{pmatrix} \mathtt x_0&\mathtt x_1&\mathtt x_2 \\\ \mathtt x_1&\mathtt x_2&\mathtt x_0 \\\ \end{pmatrix} |- | 4 || 200! || \begin{pmatrix} \mathtt x_0&\mathtt x_1&\mathtt x_2 \\\ \mathtt x_2&\mathtt x_0&\mathtt x_1 \end{pmatrix} |- | 5 || 210! || \begin{pmatrix} \mathtt x_0&\mathtt x_1&\mathtt x_2 \\\ \mathtt x_2&\mathtt x_1&\mathtt x_0 \end{pmatrix} |}
# 역사
게오르크 칸토어가 1869년에 이미 자릿수마다 진법이 바뀌는 수 표기법에 대하여 연구하였다.언어=de 1888년에 샤를앙주 레장(Charles-Ange Laisant ʃaʁl ɑ̃ʒ lɛzɑ̃, 1841〜1920)이 구체적으로 다루었으며, 순열과의 관계를 밝혔다.언어=fr Georg 칸토어 레장