계승진법

수학에서 계승진법(階乘進法, 영어: factorial number system, factoradic system)은 자연수를 계승들의 합으로 표기하는 표기법이다. 이를 통해 순열들의 집합 위의 전순서를 쉽게 매길 수 있다. 학교 내신 문제에서 주로 나오는 사전식 배열 문제를 풀 때도 용이하다.

정의

계승진법에서, 자연수 ${\displaystyle a\in \mathbb {N} }$는 다음과 같은 꼴로 표현된다.

${\displaystyle a=(\dotso a_{4}a_{3}a_{2}a_{1})_{!}=\sum _{i=0}^{\infty }a_{i+1}i!}$

여기서

${\displaystyle a_{i}\in \{0,1,\dotsc ,i-1\}}$

이다. 특히, 마지막 자리 ${\displaystyle a_{1}}$의 값은 항상 0이다.

예를 들어,

${\displaystyle 341010_{!}=3\times 5!+4\times 4!+1\times 3!+0\times 2!+1\times 1!+0\times 0!=463}$

이다.

성질

계승진법으로의 변환

자연수 ${\displaystyle a\in \mathbb {N} }$의 계승진법 표기

${\displaystyle (\dotso a_{4}a_{3}a_{2}a_{1})_{!}}$

는 다음과 같은 재귀적 알고리즘으로 주어진다.

${\displaystyle b_{0}=a}$

${\displaystyle a_{i}\equiv b_{i-1}{\pmod {i}}}$

${\displaystyle b_{i}=\lfloor b_{i-1}/i\rfloor }$

예를 들어, 463의 계승진법 표현은 다음과 같다.

bi−1	=	bi	×	i	+	ai
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_!

이다.

순열과의 관계

계승진법을 사용하여, 크기 ${\displaystyle n}$의 알파벳

${\displaystyle \Sigma =\{{\mathtt {x}}_{0},{\mathtt {x}}_{1},\dotsc ,{\mathtt {x}}_{k-1}\}}$

의 순열들의 집합(대칭군)

${\displaystyle \operatorname {Sym} (\Sigma )}$

과 자연수 집합

${\displaystyle \{0,1,\dotsc ,k!-1\}}$

사이의 표준적인 전단사 함수를 정의할 수 있다.

구체적으로, 자연수 ${\displaystyle 0\leq m\leq k!-1}$를 ${\displaystyle k}$자릿수의 계승진법으로 표기하였을 때

${\displaystyle m=(m_{k}m_{k-1}\dotsc m_{2}m_{1})_{!}}$

라고 하자. 그렇다면, ${\displaystyle m}$에 대응하는 순열

${\displaystyle m\colon \Sigma \to \Sigma }$

은 다음과 같은 알고리즘에 의하여 주어진다.

• 크기 ${\displaystyle k}$의 집합 ${\displaystyle \Sigma }$의 ${\displaystyle m_{k}}$번째 원소가 ${\displaystyle \sigma ({\mathtt {x}}_{0})}$이다.
• 크기 ${\displaystyle k-1}$의 집합 ${\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0}\}}$의 ${\displaystyle m_{k-1}}$번째 원소가 ${\displaystyle \sigma ({\mathtt {x}}_{1})}$이다.
• ⋮
• 일반적으로, 크기 ${\displaystyle k-p}$의 집합 ${\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},{\mathtt {x}}_{1},\dotsc ,{\mathtt {x}}_{p-1}\}}$의 ${\displaystyle m_{k-p}}$번째 원소가 ${\displaystyle \sigma ({\mathtt {x}}_{p})}$이다.
• ⋮
• 크기 2의 집합 ${\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},\dotsc ,{\mathtt {x}}_{k-3}\}}$의 ${\displaystyle m_{2}}$번째 원소가 ${\displaystyle \sigma ({\mathtt {x}}_{k-2})}$이다.
• 크기 1의 집합 ${\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},\dotsc ,{\mathtt {x}}_{k-2}\}}$의 ${\displaystyle m_{1}=0}$번째 원소가 ${\displaystyle \sigma ({\mathtt {x}}_{k-1})}$이다. (${\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},\dotsc ,{\mathtt {x}}_{k-2}\}}$에서 이미 원소가 하나 밖에 남지 않았으므로 이 단계는 자명하다.)

이 알고리즘에서, ‘집합의 〜번째 원소’란 0번째부터 센다.

예를 들어, ${\displaystyle n=3}$일 때, 수 {0,1,2,3,4,5}와 알파벳 ${\displaystyle \{{\mathtt {x}}_{0},{\mathtt {x}}_{1},{\mathtt {x}}_{2}\}}$ 위의 순열 사이의 대응은 다음과 같다.

수	멱승진법	순열
0	000!	${\displaystyle {\begin{pmatrix}{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\\end{pmatrix}}}$
1	010!	${\displaystyle {\begin{pmatrix}{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\{\mathtt {x}}_{0}&{\mathtt {x}}_{2}&{\mathtt {x}}_{1}\\\end{pmatrix}}}$
2	100!	${\displaystyle {\begin{pmatrix}{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\{\mathtt {x}}_{1}&{\mathtt {x}}_{0}&{\mathtt {x}}_{2}\\\end{pmatrix}}}$
3	110!	${\displaystyle {\begin{pmatrix}{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\{\mathtt {x}}_{1}&{\mathtt {x}}_{2}&{\mathtt {x}}_{0}\\\end{pmatrix}}}$
4	200!	${\displaystyle {\begin{pmatrix}{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\{\mathtt {x}}_{2}&{\mathtt {x}}_{0}&{\mathtt {x}}_{1}\end{pmatrix}}}$
5	210!	${\displaystyle {\begin{pmatrix}{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\{\mathtt {x}}_{2}&{\mathtt {x}}_{1}&{\mathtt {x}}_{0}\end{pmatrix}}}$

역사

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

• 
  게오르크 칸토어
• 
  샤를앙주 레장

같이 보기

• 스테인하우스-존슨-트로터 알고리즘