1. 개요
factorial / 階乘[math(n)]의 계승이란 [math(1)]부터 [math(n)]까지의 자연수를 모두 곱하는 것을 의미하며, 기호로 간단하게 [math(n!)]로 나타낸다. 팩토리얼이라고도 부른다.
문화어로는 차례곱이라고 하는데, [math(1)]부터 차례대로 곱한다는 의미다.
기호 파이(Π)를 사용해서 [math(\displaystyle n! = \prod_{k=1}^n k)]로 나타내기도 하는데, [math(k=1)]부터 [math(k=n)]까지의 합 연산을 의미하는 [math(\displaystyle \sum_{k=1}^n k)]처럼 [math(\displaystyle \prod)]는 곱연산을 의미한다.
고등학교 교육과정에서는 중복 순열 기호로 거듭제곱이 아니라 이미 [math(\Pi)]를 쓰고 있기도 하고[1], 또한 여러 개의 항을 곱하는 것을 거의 다루지 않다 보니 곱의 기호 [math(\displaystyle \prod)]를 가르치지 않는다. 계승을 접할 수 있는 확률과 통계와 공통수학 과목에서는 [math(n! = 1\times2\times3\times\cdots\times(n-1)\times n)]으로 배운다. 그러나 다음 문단들에서 소개할 다중 계승이나 상승·하강 계승 등의 심화 개념을 이해하려면 식을 거꾸로 기억하는 것이 좋다. 그러니까 [math(\displaystyle n! = \prod_{i=0}^{n-1} (n-i) = n(n-1)(n-2)\cdots3\cdot2\cdot1)], 즉 [math(\boldsymbol n)]부터 [math(\boldsymbol 1)]씩 빼서 [math(\boldsymbol 1)]까지 곱하는 것으로 기억하자.
한편, 계승은 순열이나 조합 등 조합론의 여러 분야에서 빈번하게 쓰이는 기호이기 때문에 [math(n)]의 범위는 일반적으로 음이 아닌 정수까지 확장된다. 즉, [math(n!)]의 정의역에 [math(n=0)]도 포함된다. [math(0!)]은 특별히 [math(0!=1)]로 정의한다. 예를 들자면, 서로 다른 [math(n)]개의 물건에서 [math(n)]개를 모두 뽑아 나열하는 경우의 수([math({}_n{\rm P}_n)])는 [math(n!)]인데, [math({}_n{\rm P}_r = \dfrac{n!}{(n-r)!})]이므로 [math({}_n{\rm P}_n = \dfrac{n!}{0!})]이며, 정의의 일관성을 유지하려면 [math(0! = 1)]이어야 한다. 만약 [math(0! \ne 1)]이라면 순열 뿐만 아니라 조합론의 거의 모든 개념에서 일일이 경우를 나눠서 재정의 해야할 것이다. [math(n! = n\times(n-1)!)] 등의 점화식 역시 자연수 범위에서 성립하는 식으로 만드려면 [math(0! = 1)]로 정의하면 된다. 또한 [math(0! = 1)]의 정의를 좀 더 직관적으로 이해해보자면 [math(1! = 1)], [math(2! = 2\times1)], [math(3! = 3\times2\times1)], [math(4! = 4\times3\times2\times1)]... 의 순서를 거꾸로 생각해보는 것이다. 즉, [math(4!)]을 [math(4)]로 나눠 [math(3!)], [math(3!)]을 [math(3)]으로 나눠 [math(2!)], [math(2!)]을 [math(2)]로 나눠 [math(1!)], 마지막으로 [math(1!)]을 [math(1)]로 나눠 [math(0!)]이므로, 따라서 [math(0! = \dfrac{1!}1 = 1)]이다.
| [math(n)] | [math(0)] | [math(1)] | [math(2)] | [math(3)] | [math(4)] | [math(5)] | [math(6)] | [math(7)] | [math(8)] | [math(9)] | [math(10)] | [math(11)] | [math(12)] |
| [math(n!)] | [math(1)] | [math(1)] | [math(2)] | [math(6)] | [math(24)] | [math(120)] | [math(720)] | [math(5{,}040)] | [math(40{,}320)] | [math(362{,}880)] | [math(3{,}628{,}800)] | [math(39{,}916{,}800)] | [math(479{,}001{,}600)] |
2. 다중 계승
전술하였듯이, 계승이란 [math(n)]부터 시작해서 [math(1)]씩 빼며 [math(1)]까지 곱하라는 것이다. 여기서 좀 더 나아가서, [math(n)]부터 시작해서 [math(2)]씩 빼며 [math(1)]이나 [math(2)]까지 곱하는 것을 생각해볼 수 있다. 이를 이중 계승(double factorial)이라고 하며, 기호로 [math(n!!)] 또는 [math(n!_2)]라고 표기한다. 그리고 계승에서 관계식 [math(n! = n\times(n-1)!)], 즉 [math((n-1)! = \dfrac{n!}n)]를 이용하여 [math(0! = \dfrac{1!}1 = 1)]임을 정의하였던 것처럼, 이중 계승도 관계식 [math(n!! = n\times(n-2)!!)], 즉 [math((n-2)!! = \dfrac{n!!}n)]를 이용하여 [math(0!! = \dfrac{2!!}2 = 1)]과 [math((-1)!! = \dfrac{1!!}1 = 1)]이라고 정의한다. 참고로 이중 계승을 사용할 때 주의해야 할 점은, 이중 계승은 팩토리얼을 두 번 적용하라는 뜻이 아니라는 점이다. 즉, [math(n!! \neq (n!)!)]이다.[2] 예를 들어서 [math(5!! = 5\times3\times1 = 15)]이지만 [math((5!)! = 120! \approx 6.6895\times10^{198})]이다.마찬가지로, [math(n)]부터 시작해서 [math(3)]씩 빼며 [math(1)]이나 [math(2)]나 [math(3)]까지 곱하는 것을 생각해볼 수 있는데, 이를 삼중 계승(triple factorial)이라고 하며, 기호로 [math(n!!!)] 또는 [math(n!_3)]라고 표기한다. 이것도 마찬가지로 팩토리얼을 세 번 적용하라는 뜻이 아니다. 즉, [math(n!!! \neq ((n!)!)!)]이다.[3] 그리고 삼중 계승도 이중 계승의 경우처럼 [math(n!!! = n\times(n-3)!!!)]임을 이용하여 [math(0!!!=(-1)!!!=(-2)!!!=1)]이라고 정의한다.
이를 확장해서 [math(k)]씩 빼며 곱하는 것을 생각해볼 수 있다. 이를 [math(k)]중 계승이라고 하고, 기호로 [math(n\overbrace{!!!\cdots\,!}^k)] 또는 [math(n!_k)]로 나타낸다. 그리고 이중 계승, 삼중 계승과 같은 논의를 따르면 [math(n!_k)]의 정의역은 [math(n\in\Z)], [math(n\ge1-k)]이다.
| [math(n!_k)] | [math(n)] | |||||||
| [math(1)] | [math(2)] | [math(3)] | [math(4)] | [math(5)] | [math(6)] | [math(7)] | ||
| [math(k)] | [math(1)] | [math(1!=1)] | [math(2!=2)] | [math(3!=6)] | [math(4!=24)] | [math(5!=120)] | [math(6!=720)] | [math(7!=5040)] |
| [math(2)] | [math(1!!=1)] | [math(2!!=2)] | [math(3!!=3\times1=3)] | [math(4!!=4\times2=8)] | [math(5!!=5\times3\times1=15)] | [math(6!!=6\times4\times2=48)] | [math(7!!=7\times5\times3\times1=105)] | |
| [math(3)] | [math(1!!!=1)] | [math(2!!!=2)] | [math(3!!!=3)] | [math(4!!!=4\times1)] | [math(5!!!=5\times2=10)] | [math(6!!!=6\times3=18)] | [math(7!!!=7\times4\times1=28)] | |
| [math(n!_k)] | [math(n)] | ||||
| [math(0)] | [math(-1)] | [math(-2)] | [math(-3)] | ||
| [math(k)] | [math(1)] | [math(0!=\dfrac{1!}1=1)] | - | ||
| [math(2)] | [math(0!!=\dfrac{2!!}2=1)] | [math((-1)!!=\dfrac{1!!}1=1)] | - | ||
| [math(3)] | [math(0!!!=\dfrac{3!!!}3=1)] | [math((-1)!!!=\dfrac{2!!!}2=1)] | [math((-2)!!!=\dfrac{1!!!}1=1)] | - | |
3. 하강 계승 / 상승 계승
하강 계승(下降階乘 / falling factorial) [math(n^{\underline k})]는 계승의 정의 [math(\displaystyle n! = \prod_{i=0}^{n-1}(n-i) )]에서 [math(i=n-1)]까지가 아닌 [math(i=k-1)]까지의 곱으로 정의된다. [math((n)_k)]로 표기하기도 한다. (단, [math(n\in\Z)]이고 [math(k\in\;)][math(Z^{0+})]이다.) [math(k=0)]일 때는 [math(\prod_{i=0}^{k-1})]이 공곱(empty product)이므로 [math(n^{\underline 0}=1)]로 정의된다.[math(\displaystyle \begin{aligned} n^{\underline k} &= \prod_{i=0}^{k-1} (n-i) \\ &= n(n-1)(n-2)\cdots(n-k+2)(n-k+1) \\ &= \frac{n!}{(n-k)!} \end{aligned} )] |
이와 비슷하게, 상승 계승(上昇階乘 / rising factorial) [math(n^{\overline k})]는 하강 계승의 부분곱 식에서 [math((n-i))]를 [math((n+i))]로 바꾼 식으로 정의된다. [math(n^{(k)})]로 표기하기도 한다. (단, [math(n\in\Z)]이고 [math(k\in\Z^{0+})]) [math(k=0)]일 때는 하강 계승의 경우처럼 [math(n^{\overline 0}=1)]로 정의된다.
[math(\displaystyle \begin{aligned} n^{\overline k} &= \prod_{i=0}^{k-1} (n+i) \\ &= n(n+1)(n+2)\cdots(n+k-2)(n+k-1) \\ &= \frac{(n+k-1)!}{(n-1)!} \end{aligned} )] |
하강 계승의 정의에서 [math(n)]에 [math(-n)]을 대입하면 다음과 같이 식이 바뀌면서 상승 계승에 대한 식으로 변한다.
[math(\displaystyle \begin{aligned} (-n)^{\underline k} &= \prod_{i=0}^{k-1} (-n-i) \\ &= (-1)^k \prod_{i=0}^{k-1} (n+i) \\ &= (-1)^k n^{\overline k} \end{aligned} )] |
[math((n)_k)], [math(n^{(k)})]는 레오 아우구스트 포흐하머가 고안한 기호이며, [math(n^{\underline{k}})], [math(n^{\overline{k}})]은 커누스 윗화살표 표기법으로 유명한 도널드 커누스가 고안했다.
제1종 스털링 수, 제2종 스털링 수, 라흐 수, 베타 함수, 초기하함수를 정의할 때 쓰인다.
4. 소수 계승
의 소수 계승 부분을
참고하십시오.[math(\displaystyle \begin{aligned}
n\# = e^{\vartheta(n)} = \prod_{p\leq n, \,p\,\in\,{\mathbb P}} p
\end{aligned} )]
자연수 [math(n)] 이하의 모든 소수를 곱하는 연산이다. 자세한 내용은 해당문서 참고.
5. 정의역의 확장
계승은 [math(0)] 이상의 정수에서만 정의되지만, 이 정의역을 복소수로 확장할 수 있다. 그렇게 확장해서 나온 함수가 바로 감마 함수 [math(Gamma(z))]이다.[4] 즉, 감마 함수를 이용하면 [math(1.5!)] 같은 것도 계산할 수 있다는 것. 예를 들어 [math(\!\left(-\dfrac12\right)! = \Gamma\!\left(\dfrac12\right) \!= \sqrt\pi)]이다. 그래서 이를 통해 순열이나 조합 같은 것도 실수, 복소수로 일반화가 가능하다.일반 공학용 계산기에 [math(1.5!)] 따위를 넣으면 못 구해주지만, 구글 계산기나 윈도우 계산기 등은 잘 구해준다. 사실, 계승에 음의 정수를 넣으면 값을 안 구해줘야[5] 정상이다. 그 이유는 계승의 정의역이 0 이상의 정수에서만 정의되기 때문이다. 다만, 값이 나오는 경우는 감마 함수의 함숫값을 편의상 계승을 사용하여 표현하기 때문이다. 그러는 편이 직관적으로 이해하기에 좋기 때문이기도 하다. 즉, [math(n! = \Gamma(n+1))]이므로, 정수가 아닌 수를 넣으면 감마 함수로 구하도록 프로그래밍했을 것으로 추정된다.
계승뿐만 아니라 상승 계승 [math(n^{\overline k})] 및 하강 계승 [math(n^{\underline k})]도 정의역을 확장할 수 있다. 우선 하강 계승 / 상승 계승 문단에서 서술된 각각의 정의를 보자. (단, [math(n\in\Z)]이고 [math(k\in\;)][math(Z^{0+})])
[math(\displaystyle \begin{aligned} n^{\overline k} &= \prod_{i=0}^{k-1} (n+i) = n(n+1)(n+2)\cdots(n+k-2)(n+k-1) \\ n^{\underline k} &= \prod_{i=0}^{k-1} (n-i) = n(n-1)(n-2)\cdots(n-k+2)(n-k+1) \end{aligned} )] |
[math(\displaystyle \begin{aligned} n^{\overline k} &= \prod_{i=0}^{k-1} (n+i) = n(n+1)(n+2)\cdots(n+k-2)(n+k-1) \\ n^{\underline k} &= \prod_{i=0}^{k-1} (n-i) = n(n-1)(n-2)\cdots(n-k+2)(n-k+1) \end{aligned} )] |
[math(\displaystyle \begin{aligned} z(z+1)\cdots(z+k-2)(z+k-1) &= \frac{\Gamma(z)\cdot z(z+1)\cdots(z+k-2)(z+k-1)}{\Gamma(z)} \\ &= \frac{\Gamma(z+k)}{\Gamma(z)} \\ z(z-1)\cdots(z-k+2)(z-k+1) &= \frac{z(z-1)\cdots(z-k+2)(z-k+1)\cdot\Gamma(z-k+1)}{\Gamma(z-k+1)} \\ &= \frac{\Gamma(z+1)}{\Gamma(z-k+1)} \end{aligned} )] |
[math(\displaystyle \begin{aligned} n^{\overline k} &= \frac{\Gamma(n+k)}{\Gamma(n)} &&(n\notin\Z^{0-}, n+k\notin\Z^{0-}) \\ n^{\underline k} &= \frac{\Gamma(n+1)}{\Gamma(n-k+1)} &&(n\notin\Z^-, n-k\notin\Z^-) \end{aligned} )] |
6. 알고리즘
계승 알고리즘은 컴퓨터에서 두 가지 형태로 구현할 수 있다.#!syntax cpp
unsigned int fact_iter (unsigned int n) { // 계승은 음이 아닌 정수에 대해서만 정의된다.
if (n <= 1) return 1; // 1! = 0! = 1이므로 1을 반환한다.
int result = n;
for (int i = n - 1; i > 1; i--) result *= i; // n부터 하나씩 값을 줄여가며 그 값을 결과값에 곱한다.
return result;
}
반복문(iteration, loop) 형태의 알고리즘
#!syntax cpp
unsigned int fact_rcsv (unsigned int n) {
if (n <= 1) return 1; // 1! = 0! = 1이므로 1을 반환한다.
return n * fact_rcsv(n - 1); // n! = n * (n - 1)!이므로, n - 1에 대한 함수를 한 번 더 호출한다.
}
재귀(recursion) 형태의 알고리즘
두 알고리즘은 모두 시간복잡도가 [math(O(n))]이지만, 재귀 함수는 반복하여 호출할수록 메모리 공간을 더 차지하므로, 숫자가 커지면 반복문 알고리즘이 상대적으로 효율적이다.
4바이트인 int 자료형으로 하면 13!부터 int의 범위를 넘는다.[6] 8바이트인 long으로 하거나, 더 큰 수가 필요한다면 큰 수를 다루는 별도 모듈을 사용해야 한다.[7]
7. 기타
이것을 기반으로 한 공대개그가 존재한다. 예를 들어 [math(3!)]를 '삼!'이라고 강하게 읽으면 문과, '삼 팩토리얼'이라고 읽으면 이과, 애똑이라고 읽으면 이론언어학 전공자, 3쾅이라고 읽으면 수학 귀신 독자라고 한다.[8] 다른 개그로 수학 문제를 잘못 계산한 척 해놓고 느낌표를 팩토리얼 기호로 해석하면 정답이 되는 식의 낚시(예)가 있고,[9] 가수 룰라의 노래인 3!4!를 3!×4!로 해석해서 3!=(3×2×1)=6, 4!=(4×3×2×1)=24이니까 (3×2×1)×(4×3×2×1)=6×24=144라는 식으로 해석하는 식이다. 또는 이러한 유머도 있다.[10]숫자 뒤가 아닌 숫자 앞에 느낌표를 붙이거나, 뒤집어서 붙이게 되면([math(!n)] 또는 [math(n¡)]의 꼴, [math(n)]은 자연수) [math(n)]개의 원소에 대한 완전순열(derangement)의 수를 의미하게 되며, 이 때는 준계승(subfactorial)이라 부르게 된다. 완전순열은 섞인 모자들 속에서 사람들이 아무도 자기 모자를 집어가지 않는 경우의 수 등을 셀 때 쓰이며, [math(!n)]의 공식은 [math(n!)]보다 복잡하다. 자세한 내용은 완전순열 항목으로.
계승은 매우 빠른 속도로 증가한다. [math((n/2)^n)]보다도 [math(n!)]이 점근적으로 빨리 증가한다. 스털링 근사에 따르면 대략 [math((n/e)^n)]의 속도로 증가한다. 문서 상단의 개요 문단에서 봤듯, 고작 [math(10!)]까지만 해도 벌써 363만 정도이며 [math(12!)]만 해도 4.8억 정도이다. 이 때문에 시간 복잡도에서 계승([math(O(n!))])이 튀어나오면 해당 알고리즘은 폐급 취급을 받는다. 브루트 포스의 시간 복잡도가 계승꼴이므로 어떤 알고리즘을 만들든 간에 전수조사보다는 효율적이어야 한다는 의무를 함의한다.
8. 관련 문서
[1] 세계적으로는 [math({}_n\Pi_{r})]을 안 쓰고 그냥 [math(n^r)]으로 나타낸다. 자세한 내용은 순열 문서의 중복 순열 문단 참고.[2] 우연히 값이 같아질 수는 있다. [math(n=0)], [math(1)], [math(2)]일 때가 바로 그 경우.[3] 우연히 값이 같아질 수는 있다. [math(n=0)], [math(1)], [math(2)]일 때가 바로 그 경우.[4] 다만, 이 경우에도 [math(z \notin \Z^{0-})]여야 한다.[5] 입력이 잘못됐다는 메시지를 내놓거나 등[6] [math(12! \fallingdotseq 479 \rm M)], [math(13! \fallingdotseq 6.23 \rm G)]로,
unsigned int의 범위인 42.95억을 넘어간다.[7] Python은 별도 모듈 없이도 큰 수 연산이 가능하여 매우 편리하고, Java에서는 BigInteger 모듈이 마련되어 있지만, C언어 계열에는 존재하지 않아 직접 만들어야 한다...[8] 수학 귀신이라는 책에서 계승과 관련된 내용이 나오는데, 수학 귀신이 이를 '쾅' 또는 '꽝'으로 읽는다.[9] 이를테면 6×4=24인데 4!라고 하면 4×3×2×1=24이므로, 느낌표를 문장 부호로 보면 틀리고, 팩토리얼로 보면 정답이 되는 방식이다.[10] 말로 대화하면 나올 수 없는 상황이므로 서로 채팅을 하거나 댓글을 달고 있는 상황이었을 것이다.[11] 문과생은 숫자 5를 강조하기 위해 느낌표를 문장 부호로 쓴 것으로 알아듣고, 복잡한 수식에서는 곱셈과 나눗셈을 먼저 해야 하는데 그냥 순서대로 계산한 것으로 생각했다. 하지만 이과생은 [math(5!)], 즉 5팩토리얼이라고 쓴 것으로 알아듣고 정답인 120을 같은 값인 [math(5!)]로 표현한 것으로 생각한 것이다. 40-32÷2를 4!, 1428-1416÷2를 6!이라고 대답하는 버전도 있으며 해석 역시 동일하다.