수학 에서 계승진법 (階乘進法, 영어 : factorial number system , factoradic system )은 자연수 를 계승 들의 합으로 표기하는 표기법이다. 이를 통해 순열 들의 집합 위의 전순서를 쉽게 매길 수 있다. 학교 내신 문제에서 주로 나오는 사전식 배열 문제를 풀 때도 용이하다.
계승진법 에서, 자연수
a
∈
N
{\displaystyle a\in \mathbb {N} }
a
=
(
…
a
4
a
3
a
2
a
1
)
!
=
∑
i
=
0
∞
a
i
+
1
i
!
{\displaystyle a=(\dotso a_{4}a_{3}a_{2}a_{1})_{!}=\sum _{i=0}^{\infty }a_{i+1}i!}
여기서
a
i
∈
{
0
,
1
,
…
,
i
−
1
}
{\displaystyle a_{i}\in \{0,1,\dotsc ,i-1\}}
이다. 특히, 마지막 자리
a
1
{\displaystyle a_{1}}
예를 들어,
341010
!
=
3
×
5
!
+
4
×
4
!
+
1
×
3
!
+
0
×
2
!
+
1
×
1
!
+
0
×
0
!
=
463
{\displaystyle 341010_{!}=3\times 5!+4\times 4!+1\times 3!+0\times 2!+1\times 1!+0\times 0!=463}
이다.
계승진법으로의 변환
편집
자연수
a
∈
N
{\displaystyle a\in \mathbb {N} }
(
…
a
4
a
3
a
2
a
1
)
!
{\displaystyle (\dotso a_{4}a_{3}a_{2}a_{1})_{!}}
는 다음과 같은 재귀적 알고리즘으로 주어진다.
b
0
=
a
{\displaystyle b_{0}=a}
a
i
≡
b
i
−
1
(
mod
i
)
{\displaystyle a_{i}\equiv b_{i-1}{\pmod {i}}}
b
i
=
⌊
b
i
−
1
/
i
⌋
{\displaystyle b_{i}=\lfloor b_{i-1}/i\rfloor }
예를 들어, 463의 계승진법 표현은 다음과 같다.
b i −1=
b i ×
i +
a i
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! 이다.
순열과의 관계
편집
계승진법을 사용하여, 크기
n
{\displaystyle n}
Σ
=
{
x
0
,
x
1
,
…
,
x
k
−
1
}
{\displaystyle \Sigma =\{{\mathtt {x}}_{0},{\mathtt {x}}_{1},\dotsc ,{\mathtt {x}}_{k-1}\}}
의 순열 들의 집합(대칭군 )
Sym
(
Σ
)
{\displaystyle \operatorname {Sym} (\Sigma )}
과 자연수 집합
{
0
,
1
,
…
,
k
!
−
1
}
{\displaystyle \{0,1,\dotsc ,k!-1\}}
사이의 표준적인 전단사 함수 를 정의할 수 있다.
구체적으로, 자연수
0
≤
m
≤
k
!
−
1
{\displaystyle 0\leq m\leq k!-1}
k
{\displaystyle k}
m
=
(
m
k
m
k
−
1
…
m
2
m
1
)
!
{\displaystyle m=(m_{k}m_{k-1}\dotsc m_{2}m_{1})_{!}}
라고 하자. 그렇다면,
m
{\displaystyle m}
m
:
Σ
→
Σ
{\displaystyle m\colon \Sigma \to \Sigma }
은 다음과 같은 알고리즘에 의하여 주어진다.
크기
k
{\displaystyle k}
Σ
{\displaystyle \Sigma }
m
k
{\displaystyle m_{k}}
σ
(
x
0
)
{\displaystyle \sigma ({\mathtt {x}}_{0})}
크기
k
−
1
{\displaystyle k-1}
Σ
∖
σ
{
x
0
}
{\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0}\}}
m
k
−
1
{\displaystyle m_{k-1}}
σ
(
x
1
)
{\displaystyle \sigma ({\mathtt {x}}_{1})}
⋮
일반적으로, 크기
k
−
p
{\displaystyle k-p}
Σ
∖
σ
{
x
0
,
x
1
,
…
,
x
p
−
1
}
{\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},{\mathtt {x}}_{1},\dotsc ,{\mathtt {x}}_{p-1}\}}
m
k
−
p
{\displaystyle m_{k-p}}
σ
(
x
p
)
{\displaystyle \sigma ({\mathtt {x}}_{p})}
⋮
크기 2의 집합
Σ
∖
σ
{
x
0
,
…
,
x
k
−
3
}
{\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},\dotsc ,{\mathtt {x}}_{k-3}\}}
m
2
{\displaystyle m_{2}}
σ
(
x
k
−
2
)
{\displaystyle \sigma ({\mathtt {x}}_{k-2})}
크기 1의 집합
Σ
∖
σ
{
x
0
,
…
,
x
k
−
2
}
{\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},\dotsc ,{\mathtt {x}}_{k-2}\}}
m
1
=
0
{\displaystyle m_{1}=0}
σ
(
x
k
−
1
)
{\displaystyle \sigma ({\mathtt {x}}_{k-1})}
Σ
∖
σ
{
x
0
,
…
,
x
k
−
2
}
{\displaystyle \Sigma \setminus \sigma \{{\mathtt {x}}_{0},\dotsc ,{\mathtt {x}}_{k-2}\}}
이 알고리즘에서, ‘집합의 〜번째 원소’란 0번째부터 센다.
예를 들어,
n
=
3
{\displaystyle n=3}
{
x
0
,
x
1
,
x
2
}
{\displaystyle \{{\mathtt {x}}_{0},{\mathtt {x}}_{1},{\mathtt {x}}_{2}\}}
순열 사이의 대응은 다음과 같다.
수
멱승진법
순열
0
000!
(
x
0
x
1
x
2
x
0
x
1
x
2
)
{\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!
(
x
0
x
1
x
2
x
0
x
2
x
1
)
{\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!
(
x
0
x
1
x
2
x
1
x
0
x
2
)
{\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!
(
x
0
x
1
x
2
x
1
x
2
x
0
)
{\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!
(
x
0
x
1
x
2
x
2
x
0
x
1
)
{\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!
(
x
0
x
1
x
2
x
2
x
1
x
0
)
{\displaystyle {\begin{pmatrix}{\mathtt {x}}_{0}&{\mathtt {x}}_{1}&{\mathtt {x}}_{2}\\{\mathtt {x}}_{2}&{\mathtt {x}}_{1}&{\mathtt {x}}_{0}\end{pmatrix}}}
참고 문헌
편집
↑ 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 .
샤를앙주 레장
