계승진법 문서 원본 보기

{{위키데이터 속성 추적}}
[[수학]]에서 '''계승진법'''(階乘進法, {{llang|en|factorial number system}}, {{lang|en|factoradic system}})은 [[자연수]]를 [[계승 (수학)|계승]]들의 합으로 표기하는 표기법이다. 이를 통해 [[순열]]들의 집합 위의 전순서를 쉽게 매길 수 있다. 학교 내신 문제에서 주로 나오는 사전식 배열 문제를 풀 때도 용이하다.

== 정의 ==
'''계승진법'''에서, [[자연수]] <math>a\in\mathbb N</math>는 다음과 같은 꼴로 표현된다.
:<math>a = (\dotso a_4a_3a_2a_1)_! = \sum_{i=0}^\infty a_{i+1} i!</math>
여기서
:<math>a_i \in \{0,1,\dotsc,i-1\}</math>
이다. 특히, 마지막 자리 <math>a_1</math>의 값은 항상 0이다.

예를 들어,
:<math>341010_! = 3 \times 5! + 4 \times 4! + 1 \times 3! + 0 \times 2! + 1\times1! + 0\times 0! = 463</math>
이다.

== 성질 ==
=== 계승진법으로의 변환 ===
자연수 <math>a\in\mathbb N</math>의 계승진법 표기
:<math>(\dotso a_4a_3a_2a_1)_!</math>
는 다음과 같은 재귀적 알고리즘으로 주어진다.
:<math>b_0 = a</math>
:<math>a_i \equiv b_{i-1} \pmod i</math>
:<math>b_i = \lfloor b_{i-1} / i \rfloor</math>

예를 들어, 463의 계승진법 표현은 다음과 같다.
{| style="text-align: center"
|-
! ''b''<sub>''i''−1</sub> || = || ''b''<sub>''i''</sub> || × || ''i'' || + || ''a''<sub>''i''</sub>
|-
| 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<sub>!</sub>
이다.

=== 순열과의 관계 ===
계승진법을 사용하여, 크기 <math>n</math>의 알파벳
:<math>\Sigma=\{\mathtt x_0,\mathtt x_1,\dotsc,\mathtt x_{k-1}\}</math>
의 [[순열]]들의 집합([[대칭군 (군론)|대칭군]])
:<math>\operatorname{Sym}(\Sigma)</math>
과 자연수 집합
:<math>\{0,1,\dotsc,k!-1\}</math>
사이의 표준적인 [[전단사 함수]]를 정의할 수 있다.

구체적으로, 자연수 <math>0 \le m \le k! - 1</math>를 <math>k</math>자릿수의 계승진법으로 표기하였을 때
:<math>m=(m_km_{k-1}\dotsc m_2m_1)_!</math>
라고 하자. 그렇다면, <math>m</math>에 대응하는 순열
:<math>m \colon \Sigma \to \Sigma</math>
은 다음과 같은 알고리즘에 의하여 주어진다.
* 크기 <math>k</math>의 집합 <math>\Sigma</math>의 <math>m_k</math>번째 원소가 <math>\sigma(\mathtt x_0)</math>이다.
* 크기 <math>k-1</math>의 집합 <math>\Sigma\setminus\sigma\{\mathtt x_0\}</math>의 <math>m_{k-1}</math>번째 원소가 <math>\sigma(\mathtt x_1)</math>이다.
* ⋮ 
* 일반적으로, 크기 <math>k-p</math>의 집합 <math>\Sigma\setminus\sigma\{\mathtt x_0,\mathtt x_1,\dotsc,\mathtt x_{p-1}\}</math>의 <math>m_{k-p}</math>번째 원소가 <math>\sigma(\mathtt x_p)</math>이다.
* ⋮ 
* 크기 2의 집합 <math>\Sigma\setminus\sigma\{\mathtt x_0,\dotsc,\mathtt x_{k-3}\}</math>의 <math>m_2</math>번째 원소가 <math>\sigma(\mathtt x_{k-2})</math>이다.
* 크기 1의 집합 <math>\Sigma\setminus\sigma\{\mathtt x_0,\dotsc,\mathtt x_{k-2}\}</math>의 <math>m_1=0</math>번째 원소가 <Math>\sigma(\mathtt x_{k-1})</math>이다. (<math>\Sigma\setminus\sigma\{\mathtt x_0,\dotsc,\mathtt x_{k-2}\}</math>에서 이미 원소가 하나 밖에 남지 않았으므로 이 단계는 자명하다.)
이 알고리즘에서, ‘집합의 〜번째 원소’란 0번째부터 센다.

예를 들어, <math>n=3</math>일 때, 수 {0,1,2,3,4,5}와 알파벳 <math>\{\mathtt x_0,\mathtt x_1,\mathtt x_2\}</math> 위의 [[순열]] 사이의 대응은 다음과 같다.
{| class=wikitable
! 수 !! 멱승진법 !! 순열
|-
| 0 || 000<sub>!</sub> || <math>\begin{pmatrix}
\mathtt x_0&\mathtt x_1&\mathtt x_2 \\
\mathtt x_0&\mathtt x_1&\mathtt x_2 \\
\end{pmatrix}</math>
|-
| 1 || 010<sub>!</sub> || <math>\begin{pmatrix}
\mathtt x_0&\mathtt x_1&\mathtt x_2 \\
\mathtt x_0&\mathtt x_2&\mathtt x_1 \\
\end{pmatrix}</math>
|-
| 2 || 100<sub>!</sub> || <math>\begin{pmatrix}
\mathtt x_0&\mathtt x_1&\mathtt x_2 \\
\mathtt x_1&\mathtt x_0&\mathtt x_2 \\
\end{pmatrix}</math>
|-
| 3 || 110<sub>!</sub> || <math>\begin{pmatrix}
\mathtt x_0&\mathtt x_1&\mathtt x_2 \\
\mathtt x_1&\mathtt x_2&\mathtt x_0 \\
\end{pmatrix}</math>
|-
| 4 || 200<sub>!</sub> || <math>\begin{pmatrix}
\mathtt x_0&\mathtt x_1&\mathtt x_2 \\
\mathtt x_2&\mathtt x_0&\mathtt x_1
\end{pmatrix}</math>
|-
| 5 || 210<sub>!</sub> || <math>\begin{pmatrix}
\mathtt x_0&\mathtt x_1&\mathtt x_2 \\
\mathtt x_2&\mathtt x_1&\mathtt x_0
\end{pmatrix}</math>
|}

== 역사 ==
[[게오르크 칸토어]]가 1869년에 이미 자릿수마다 진법이 바뀌는 수 표기법에 대하여 연구하였다.<ref>{{저널 인용|성=Cantor|이름=Georg|저자링크=게오르크 칸토어|날짜=1869|저널= Zeitschrift für Mathematik und Physik|권=14|제목=Ueber die einfachen Zahlensysteme|jfm=02.0085.01|쪽=121–128|언어=de}}</ref> 1888년에 샤를앙주 레장({{llang|fr|Charles-Ange Laisant}} {{IPA2|ʃaʁl ɑ̃ʒ lɛzɑ̃}}, 1841〜1920)이 구체적으로 다루었으며, [[순열]]과의 관계를 밝혔다.<ref>{{저널 인용|성=Laisant|이름=Charles-Ange|doi=10.24033/bsmf.378|제목=Sur la numération factorielle, application aux permutations | 저널=Bulletin de la Société Mathématique de France|권=16|날짜=1888|쪽=176–183 | 언어=fr}}</ref>
<gallery>
Georg Cantor2.jpg|[[게오르크 칸토어]]
Laisant.jpg|샤를앙주 레장
</gallery>

== 같이 보기 ==
* [[스테인하우스-존슨-트로터 알고리즘]]
== 각주 ==
{{각주}}

{{전거 통제}}

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