주 메뉴 열기

수학에서, 계승진법(階乘進法, 영어: factorial number system, factoradic system)은 자연수계승들의 합으로 표기하는 표기법이다. 이를 통해 순열들의 집합 위의 전순서를 쉽게 매길 수 있다.

정의편집

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

 

여기서

 

이다. 특히, 마지막 자리  의 값은 항상 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년에 이미 자릿수마다 진법이 바뀌는 수 표기법에 대하여 연구하였다.[1] 1888년에 샤를앙주 레장(프랑스어: Charles-Ange Laisant IPA[ʃaʁl ɑ̃ʒ lɛzɑ̃], 1841〜1920)이 구체적으로 다루었으며, 순열과의 관계를 밝혔다.[2]

참고 문헌편집

  1. Cantor, Georg (1869). “Ueber die einfachen Zahlensysteme”. 《Zeitschrift für Mathematik und Physik》 (독일어) 14: 121–128. JFM 02.0085.01. 
  2. 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.