계승(수학)

階乘, Factorial
수학 용어. 영단어 factorial [fækˈtɔ:riəl]을 소리나는 대로 쓴 '팩토리얼'[1]이라고 표기하기도 한다. 기억이 안 나면 느낌표라고 표현하기도 한다. 문화어로는 차례곱이라고 하는데 $1$부터 차례대로 곱한다는 의미[2]이다. 자연수 $n$을 이용하여 기호로는 간단하게 $n!$로 나타내며 $1$부터 $n$까지의 자연수를 모두 곱하는 것을 의미한다.

$\displaystyle n! = \prod_{k=1}^n k$로 나타내기도 하는데, $k=1$부터 $k=n$까지 합 연산을 의미하는 $\displaystyle \sum_{k=1}^n$처럼 $\displaystyle \prod$는 곱연산을 의미한다.

고등학교 교육과정에서는 중복 순열 기호로 왜 써야 하는지도 의문인 $\Pi$를 쓰는 것도 있고, 여러개의 항을 곱하는 것을 거의 다루지 않다 보니 곱의 기호 $\displaystyle \prod$를 가르치지 않기 때문에 계승을 접하는 확률과 통계, 수학 과목에서는 $n!=1 \times 2 \times 3 \times \cdots \cdots \times (n-1) \times n$으로 배운다.
그러나 이중 계승($!!=!_2$)[3]이나 다중 계승($\overbrace{!!! \cdots\cdots !!}^k = !_k$)[4], 상승·하강 계승 등의 심화 개념을 이해하려면 식을 거꾸로 기억하는 것이 좋다.

그러니까 $\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$, 즉 $\boldsymbol n$부터 $\boldsymbol 1$씩 빼서 $\boldsymbol 1$까지 곱하는 것으로 기억하자.

순열이나 조합 등 조합론의 여러 분야에서 빈번하게 쓰이는 기호이기 때문에 $n$의 범위는 일반적으로 음이 아닌 정수로 확장, 즉 $n=0$을 포함하는데, $0!$은 특별히 $0!=1$로 정의한다. 예를 들자면 서로 다른 $n$개의 물건에서 $n$개를 모두 뽑아 나열하는 경우의 수(${}_n\mathrm P_n$)는 $n!$인데, ${}_n\mathrm P_r = \dfrac{n!}{\left( n-r \right)!}$이므로 ${}_n\mathrm P_n = \dfrac{n!}{0!}$이며, 정의의 일관성을 유지하려면 $0!=1$이어야 한다.
만약 $0! \ne 1$이라면 순열 뿐만 아니라 조합론의 거의 모든 개념에서 일일이 경우를 나눠서 재정의 해야할 것이다. $n! = n \times \left( n-1 \right)!$ 등의 점화식 역시 $0!=1$로 정의하면 자연수 범위에서 성립하는 걸로 만들 수 있다. 참고로 $1!=1$이다.[5]

계승은 매우 빠른 속도로 증가한다. $n=10$까지의 값은 다음과 같다.

고작 10까지만 해도 벌써 백만 자리를 넘어간다.

하강 계승(Falling Factorial) $n^{\underline{k}}$은 계승의 정의 $\displaystyle n! = \prod_{i=0}^{n-1}\left(n-i\right)$에서 $i=n-1$까지가 아닌 $i=k-1$까지의 곱으로 정의된다. 즉,

과 같다. 그런데 $\dfrac{n!}{(n-k)!} = {}_n\mathrm P_k$이므로 하강 계승은 곧 순열 ${}_n\mathrm P_k$와 동치임을 알 수 있다. 조합 기호 $\dbinom nk = \dfrac{{}_n\mathrm P_k}{k!}$을 이용하면 $n^{\underline{k}} = k!\dbinom nk$로도 나타낼 수 있다.

이와 비슷하게 상승 계승(Rising Factorial) $n^{\overline{k}}$은 하강 계승의 부분곱 식에서 $(n-i)$를 $(n+i)$로 바꾼 식으로 정의된다.

조합과 비슷하게 위 식은 중복 조합 $\left(\!\!\dbinom nk \!\!\right) = \dfrac{(n+k-1)!}{(n-1)!\cdot k!}$에서 등장하므로 $n^{\overline{k}} = k! \left(\!\!\dbinom nk \!\!\right)$로도 나타낼 수 있다.

하강 계승의 정의에서 $n$에 $-n$을 대입하면 다음과 같이 식이 바뀌면서 상승 계승에 대한 식으로 변한다.

즉 $n^{\overline{k}} = \left(-1\right)^k\left(-n\right)^{\underline{k}}$임을 알 수 있고, 반대로 $n^{\underline{k}} = \left(-1\right)^k\left(-n\right)^{\overline{k}}$도 성립한다. 상술한 바와 같이 하강 계승은 조합의 정의에서, 상승 계승은 중복 조합의 정의에서 등장하므로 위와 같은 관계는 조합과 중복 조합이 사실상 하나의 식으로 표현될 수 있음을 의미한다. 즉, $\left(\!\!\dbinom nk \!\!\right) = \left(-1\right)^k \dbinom{-n}k$의 관계에 있다.

제1종 스털링 수, 제2종 스털링 수, 라흐 수를 정의할 때 쓰인다.

계승은 자연수에서만 정의되지만 $\Gamma$로 표기하는 감마 함수를 이용하면 정의역을 복소수로 확장할 수 있다.[6] 자세한 내용은 감마 함수 문서 참조. 그러니까 감마 함수를 이용하면 $1.5!$같은 것도 계산할 수 있다는 것. 예를 들어 $\left(-\dfrac{1}{2}\right)!=\Gamma\left(\dfrac{1}{2}\right)=\sqrt\pi$이다. 그래서 이를 통해 순열이나 조합 같은 것도 실수, 복소수로 일반화가 가능하다!

일반 공학용 계산기에 $1.5!$따위를 넣으면 못 구해주지만, 어째서인지 구글 계산기나 일부 계산기에선 잘 구해준다. $n! = \Gamma\left(n+1\right)$를 이용해, 정수가 아닌 수를 넣으면 감마 함수로 구하도록 프로그래밍 되었을 것으로 추정된다.

계승 알고리즘은 컴퓨터에서 두 가지 형태로 구현할 수 있다.

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) 형태의 알고리즘

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) 형태의 알고리즘

두 알고리즘은 모두 시간복잡도가 $O(n)$이지만, 재귀 함수는 반복하여 호출할수록 메모리 공간을 더 차지하므로, 숫자가 커지면 반복문 알고리즘이 상대적으로 효율적이다.

이것을 기반으로 한 공대개그가 존재한다. 예를 들어 $3!$를 '삼!'이라고 강하게 읽으면 일반인, '삼 팩토리얼'이라고 읽으면 공대생, 애똑이라고 읽으면 이론언어학 전공자라는 식. 3쾅이라고 읽으면 수학 귀신 애독자

오랫동안 수학자들을 괴롭힌 P-NP 문제의 단골 소재 중 하나다.


숫자 뒤가 아닌 숫자 앞에 느낌표를 붙이게 되면($!n$의 꼴, $n$은 자연수) $n$개의 원소에 대한 완전순열(Derangement)의 수를 의미하게 되며, 이 때는 준계승(Subfactorial)이라 부르게 된다. 완전순열은 섞인 모자들 속에서 사람들이 아무도 자기 모자를 집어가지 않는 경우 등을 셀 때 쓰이며, $!n$의 공식은 $n!$보다 복잡하다. 자세한 내용은 완전순열 참고.