계승진법

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

 정의 
계승진법에서, 자연수 는 다음과 같은 꼴로 표현된다.

여기서

이다. 특히, 마지막 자리 의 값은 항상 0이다.

예를 들어,

이다.

 성질 
 계승진법으로의 변환 
자연수 의 계승진법 표기

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

예를 들어, 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!
이다.

 순열과의 관계 
계승진법을 사용하여, 크기 의 알파벳

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

과 자연수 집합

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

구체적으로, 자연수 를 자릿수의 계승진법으로 표기하였을 때

라고 하자. 그렇다면, 에 대응하는 순열

은 다음과 같은 알고리즘에 의하여 주어진다.
 크기 의 집합 의 번째 원소가 이다.
 크기 의 집합 의 번째 원소가 이다.
 ⋮ 
 일반적으로, 크기 의 집합 의 번째 원소가 이다.
 ⋮ 
 크기 2의 집합 의 번째 원소가 이다.
 크기 1의 집합 의 번째 원소가 이다. (에서 이미 원소가 하나 밖에 남지 않았으므로 이 단계는 자명하다.)
이 알고리즘에서, ‘집합의 〜번째 원소’란 0번째부터 센다.

예를 들어, 일 때, 수 {0,1,2,3,4,5}와 알파벳  위의 순열 사이의 대응은 다음과 같다.
 수  멱승진법  순열 0  000!   1  010!   2  100!   3  110!   4  200!   5  210!  

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

 같이 보기 
 스테인하우스-존슨-트로터 알고리즘
 각주 

분류:조합론
분류:기수법