수학에서 계승진법(階乘進法, 영어: factorial number system, factoradic system)은 자연수를 계승들의 합으로 표기하는 표기법이다. 이를 통해 순열들의 집합 위의 전순서를 쉽게 매길 수 있다. 학교 내신 문제에서 주로 나오는 사전식 배열 문제를 풀 때도 용이하다.
계승진법에서, 자연수
는 다음과 같은 꼴로 표현된다.
![{\displaystyle a=(\dotso a_{4}a_{3}a_{2}a_{1})_{!}=\sum _{i=0}^{\infty }a_{i+1}i!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b86d1bba2a08a87ccbf4d6327b38264b059bcfd1)
여기서
![{\displaystyle a_{i}\in \{0,1,\dotsc ,i-1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d6f28d4e0def2e1485f46e0f1b3c17fae0c7fc2)
이다. 특히, 마지막 자리
의 값은 항상 0이다.
예를 들어,
![{\displaystyle 341010_{!}=3\times 5!+4\times 4!+1\times 3!+0\times 2!+1\times 1!+0\times 0!=463}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d178f2549fe65a8780a3b5cb8ebf74d4ae519e3f)
이다.
자연수
의 계승진법 표기
![{\displaystyle (\dotso a_{4}a_{3}a_{2}a_{1})_{!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e1b771fc3cf4f0e4b4b7b19d609607381a53749)
는 다음과 같은 재귀적 알고리즘으로 주어진다.
![{\displaystyle b_{0}=a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0597148319ae3a9039a62bc3b9c6ed6b2cf11222)
![{\displaystyle a_{i}\equiv b_{i-1}{\pmod {i}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21c75fa1d684049d75114aa1ef4873b7dfa7810d)
![{\displaystyle b_{i}=\lfloor b_{i-1}/i\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/31b21e0d7ef568cce877b4027f0279f56cedfcdd)
예를 들어, 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 \Sigma =\{{\mathtt {x}}_{0},{\mathtt {x}}_{1},\dotsc ,{\mathtt {x}}_{k-1}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0510dcc8fd5a416b9bc07c78f96b61a68e44e218)
의 순열들의 집합(대칭군)
![{\displaystyle \operatorname {Sym} (\Sigma )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8db92647fc40500f49eb96b710a77bbbea9ea7a0)
과 자연수 집합
![{\displaystyle \{0,1,\dotsc ,k!-1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53d3c81ee93b02d183a3a6c53af6d33c12976157)
사이의 표준적인 전단사 함수를 정의할 수 있다.
구체적으로, 자연수
를
자릿수의 계승진법으로 표기하였을 때
![{\displaystyle m=(m_{k}m_{k-1}\dotsc m_{2}m_{1})_{!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ab951bfa5496392174d8f2a9265245c2cdb01a7)
라고 하자. 그렇다면,
에 대응하는 순열
![{\displaystyle m\colon \Sigma \to \Sigma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb1624db55edb259f181d09949391d0a5e279ff9)
은 다음과 같은 알고리즘에 의하여 주어진다.
- 크기
의 집합
의
번째 원소가
이다.
- 크기
의 집합
의
번째 원소가
이다.
- ⋮
- 일반적으로, 크기
의 집합
의
번째 원소가
이다.
- ⋮
- 크기 2의 집합
의
번째 원소가
이다.
- 크기 1의 집합
의
번째 원소가
이다. (
에서 이미 원소가 하나 밖에 남지 않았으므로 이 단계는 자명하다.)
이 알고리즘에서, ‘집합의 〜번째 원소’란 0번째부터 센다.
예를 들어,
일 때, 수 {0,1,2,3,4,5}와 알파벳
위의 순열 사이의 대응은 다음과 같다.
수 |
멱승진법 |
순열
|
0 |
000! |
|
1 |
010! |
|
2 |
100! |
|
3 |
110! |
|
4 |
200! |
|
5 |
210! |
|
게오르크 칸토어가 1869년에 이미 자릿수마다 진법이 바뀌는 수 표기법에 대하여 연구하였다.[1] 1888년에 샤를앙주 레장(프랑스어: Charles-Ange Laisant IPA: [ʃaʁl ɑ̃ʒ lɛzɑ̃], 1841〜1920)이 구체적으로 다루었으며, 순열과의 관계를 밝혔다.[2]
- ↑ Cantor, Georg (1869). “Ueber die einfachen Zahlensysteme”. 《Zeitschrift für Mathematik und Physik》 (독일어) 14: 121–128. JFM 02.0085.01.
- ↑ Laisant, Charles-Ange (1888). “Sur la numération factorielle, application aux permutations”. 《Bulletin de la Société Mathématique de France》 (프랑스어) 16: 176–183. doi:10.24033/bsmf.378.