1. 개요
階 乘, factorial기호로 간단하게 [math(n!)]로 나타내며 [math(1)]부터 [math(n)]까지의 자연수를 모두 곱하는 것을 의미한다. 팩토리얼이라고도 불린다.
문화어로는 차례곱이라고 하는데 [math(1)]부터 차례대로 곱한다는 의미[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)]를 쓰는 것도 있고, 여러개의 항을 곱하는 것을 거의 다루지 않다 보니 곱의 기호 [math(\displaystyle \prod)]를 가르치지 않기 때문에 계승을 접하는 확률과 통계, 수학 과목에서는 [math(n!=1 \times 2 \times 3 \times \cdots \cdots \times (n-1) \times n)]으로 배운다.[2]
그러나 이중 계승([math(!!=!_2)])[3]이나 다중 계승([math(\overbrace{!!! \cdots\cdots !!}^k = !_k)])[4], 상승·하강 계승 등의 심화 개념을 이해하려면 식을 거꾸로 기억하는 것이 좋다. 이는 나중에 HAN 으로 넘어간다.
그러니까 [math(\displaystyle n! = \prod_{i=0}^{n-1} \left(n-i\right) = n \left( n-1 \right) \left( n-2 \right) \cdots\cdots 3 \cdot 2 \cdot 1)], 즉 [math(\boldsymbol n)]부터 [math(\boldsymbol 1)]씩 빼서 [math(\boldsymbol 1)]까지 곱하는 것으로 기억하자.
순열이나 조합 등 조합론의 여러 분야에서 빈번하게 쓰이는 기호이기 때문에 [math(n)]의 범위는 일반적으로 음이 아닌 정수로 확장, 즉 [math(n=0)]을 포함하는데, [math(0!)]은 특별히 [math(0!=1)]로 정의한다.
만약 [math(0! \ne 1)]이라면 순열 뿐만 아니라 조합론의 거의 모든 개념에서 일일이 경우를 나눠서 재정의 해야할 것이다. [math(n! = n \times \left( n-1 \right)!)] 등의 점화식 역시 [math(0!=1)]로 정의하면 자연수 범위에서 성립하는 걸로 만들 수 있다. 참고로 [math(1!=1)]이다.[5]
계승은 매우 빠른 속도로 증가한다. [math(n=12)]까지의 값은 다음과 같다.
| [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)] |
고작 10!까지만 해도 벌써 363만 정도이며 12!만 해도 4.8억 정도이다. 이 때문에 시간 복잡도에서 계승([math({\mathcal O}(n!))])이 튀어나오면 해당 알고리즘은 폐급 취급을 받는다.[6]
2. 하강 계승 / 상승 계승
하강 계승(falling factorial) [math(n^{\underline k})][7]은 계승의 정의 [math(\displaystyle n! = \prod_{i=0}^{n-1}(n-i) )]에서 [math(i=n-1)]까지가 아닌 [math(i=k-1)]까지의 곱으로 정의된다.| [math(\displaystyle 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)!})] |
이와 비슷하게 상승 계승(rising factorial) [math(n^{\overline k})][8]은 하강 계승의 부분곱 식에서 [math((n-i))]를 [math((n+i))]로 바꾼 식으로 정의된다.
| [math(\displaystyle 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)!})] |
하강 계승의 정의에서 [math(n)]에 [math(-n)]을 대입하면 다음과 같이 식이 바뀌면서 상승 계승에 대한 식으로 변한다.
| [math(\displaystyle (-n)^{\underline k} = \prod_{i=0}^{k-1} (-n-i) = (-1)^k \prod_{i=0}^{k-1} (n+i) = (-1)^k n^{\overline k})] |
[math((n)_k)], [math(n^{(k)})]는 레오 아우구스트 포흐하머가 고안한 기호이며, [math(n^{\underline{k}})], [math(n^{\overline{k}})]은 커누스 윗화살표 표기법로 유명한 도널드 커누스가 고안했다.
제1종 스털링 수, 제2종 스털링 수, 라흐 수, 베타 함수, 초기하함수를 정의할 때 쓰인다.
3. 정의역의 확장
계승은 자연수에서만 정의되지만 [math(\Gamma)]로 표기하는 감마 함수를 이용하면 정의역을 복소수로 확장할 수 있다.[9] 자세한 내용은 감마 함수 문서로. 그러니까 감마 함수를 이용하면 [math(1.5!)] 같은 것도 계산할 수 있다는 것. 예를 들어 [math(\left(-\dfrac{1}{2}\right)!=\Gamma\left(\dfrac{1}{2}\right)=\sqrt\pi)]이다. 그래서 이를 통해 순열이나 조합 같은 것도 실수, 복소수로 일반화가 가능하다!일반 공학용 계산기에 [math(1.5!)] 따위를 넣으면 못 구해주지만, 어째서인지 구글 계산기나 일부 계산기에선 잘 구해준다.[10][math(n! = \Gamma\left(n+1\right))]를 이용해, 정수가 아닌 수를 넣으면 감마 함수로 구하도록 프로그래밍했을 것으로 추정된다.
4. 알고리즘
계승 알고리즘은 컴퓨터에서 두 가지 형태로 구현할 수 있다.#!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))]이지만, 재귀 함수는 반복하여 호출할수록 메모리 공간을 더 차지하므로, 숫자가 커지면 반복문 알고리즘이 상대적으로 효율적이다.
그냥 노가다 해서 배열을 미리 만들어 두는 것이 좋다. 농담이 아닌 것이, 13!부터 어차피 int의 범위를 넘는다![11]
5. 기타
이것을 기반으로 한 공대개그가 존재한다. 예를 들어 [math(3!)]를 '삼!'이라고 강하게 읽으면 일반인, '삼 팩토리얼'이라고 읽으면 공대생, 애 똑이라고 읽으면 이론언어학 전공자라는 식. 3쾅이라고 읽으면 수학 귀신 애독자라고 한다. 다른 개그로 수학 문제를 잘못 계산한 척 해놓고 느낌표를 팩토리얼 기호로 해석하면 정답이 되는 식의 낚시( 예)가 있고,[12] 가수 룰라의 노래인 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라는 식으로 해석하는 식이다. 또는 이러한 유머도 있다.오랫동안 수학자들을 괴롭힌 P-NP 문제의 단골 소재 중 하나다.
숫자 뒤가 아닌 숫자 앞에 느낌표를 붙이거나, 뒤집어서 붙이게 되면([math(!n)] 또는 [math(n¡)]의 꼴, [math(n)]은 자연수) [math(n)]개의 원소에 대한 완전순열(derangement)의 수를 의미하게 되며, 이 때는 준계승(subfactorial)이라 부르게 된다. 완전순열은 섞인 모자들 속에서 사람들이 아무도 자기 모자를 집어가지 않는 경우의 수 등을 셀 때 쓰이며, [math(!n)]의 공식은 [math(n!)]보다 복잡하다. 자세한 내용은 완전순열 항목으로.
6. 관련 문서
[1]
후술하겠지만 [math(1)]씩 빼서 [math(1)]까지 차례로 곱한다는 뜻으로 외우는 것이 좋다.
[2]
곱의 기호 [math(\prod)]와, 중복 순열의 기호 [math(\Pi)]는 같은 문자를 써서 헷갈릴 수 있다.
[3]
[math(2)]씩 빼서 [math(2)]나 [math(1)]까지 차례로 곱하라는 기호.
[4]
[math(k)]씩 빼서 차례로 곱하라는 기호.
[5]
1부터 1까지 차례대로 곱하는 것은 결국 곱하나 마나이기 때문이다.
[6]
대개
전수조사의 시간 복잡도가 계승꼴이다. 즉 어떠한 알고리즘을 만들든 전수조사보다는 효율적이어야 한다는 의무를 함의한다.
[7]
[math((n)_k)]로도 표기된다.
[8]
[math(n^{(k)})]로도 표기된다.
[9]
다만 이 경우에도 허수부가 [math(0)]이라면 실수부는 [math(0)] 이하의 정수가 될 수 없다.
[10]
특히,
PC의
윈도우스
계산기.
[11]
[math(12! \fallingdotseq 479 \rm M)], [math(13! \fallingdotseq 6.23 \rm G)]로,
unsigned int의 범위인 42.95억을 넘어간다.
[12]
이를테면 6×4=24인데 4!라고 하면 4×3×2×1=24이므로, 느낌표를 문장 부호로 보면 틀리고, 팩토리얼로 보면 정답이 되는 방식이다.
[13]
문과생은 숫자 5를 말한 것으로 알아듣고 복잡한 수식에서는 곱셈과 나눗셈을 먼저 해야 하는데 그냥 순서대로 계산한 것으로 이해했고, 이과생은 [math(5!)], 즉 5팩토리얼이라고 말한 것으로 알아듣고 원래 정답인 120을 같은 값인 [math(5!)]로 바꿔 표현한 것으로 이해한 것이다.