순열

원문 보기: https://dawoum.duckdns.org/wiki/순열

Main article: Permutation

중학교에서 배운 합의 법칙, 곱의 법칙 이후에, 순열과 조합을 배웁니다. 같은 문맥에서, 예를 들어, 서로 다른 4개에서 2개를 줄 세우는 순열, 서로 다른 4개에서 2개를 고르는 조합을 비교해 보면, 조합의 개수가 작습니다. 보통은 작은 개념을 이해하고 큰 개념으로 나아가는 것이 일반적이지만, 어쨌든, 순열을 조합보다 먼저 배우는 이유는 순열은 이전 과정에서 배웠던 곱의 법칙에서 식을 유도 가능하지만, 조합은 순열로부터 식을 유도 가능하기 때문입니다.

게다가, 순열, 조합을 포함한 경우의 수는, 규칙이 전혀 없어 수형도를 그려야 하는 경우를 제외하고, 풀이 과정이 거의 필요가 없습니다. 따라서, 처음 배우는 과정에서는, 순열과 조합 중에 어느 것에 해당하는지 파악하는 것이 중요합니다. 그리고, 이 과정을 다 배운 후에는, 조합이 개수가 적기 때문에, 조합으로 사고하는 것이 좀 더 편할 수 있습니다.

순열의 뜻

순열은 근본적으로 곱의 법칙의 특별한 경우를 기호로 나타내는 것입니다. 예를 들어, 서로 다른 4명이 줄 서는 경우는 다음과 같습니다.

\(\quad\)\(4\times 3 \times 2 \times 1 \)

이것은 정의역과 공역이 각각 4개의 원소로 이루어진 일-대-일 함수의 개수를 구하는 방법의 수와 같습니다.

일반적으로 순열은 전체를 줄 세우는 경우를 지칭합니다. 만약 전체 중에서 일부를 줄 세울 때에는 n 중의 k-순열이라고 지칭합니다. 예를 들어, 서로 다른 4명 중에 2명을 줄 세우는 경우의 수는 다음과 같습니다.

\(\quad\)\(4\times 3 \)

이를 일반화해서,

서로 다른 \(n\)개에서 \(k\)개 (\(0 \le k \le n\))를 택하여 일렬로 배열하는 것을
\(\quad\)\(n\)개에서 \(k\)개를 줄 세우는 순열
이라 하고, 기호로 \(P(n,k)\) 또는 \(_nP_k\)로 나타냅니다.

여기서 \(k=0\)이면, 줄을 세우지 않는 경우이지만, 조합에서의 경우와 맞추기 위해서 \(P(n,0)=1\)로 정의해야 합니다. 일부를 줄 세우는 순열을 곱의 법칙을 사용해서 나타내면 다음과 같습니다.

\(\quad\)\(P(n,k) = \underbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}_{k\ \mathrm{factors}}\)

팩토리얼

일반적인 순열, 즉 서로 다른 \(n\)개에서 \(n\)개를 모두 줄 세우는 순열은 위의 식에서 \(n=k\)인 경우이므로

\(\quad\)\(P(n,n)= n (n-1)(n-2) \cdots (2)(1)\)

으로 나타낼 수 있습니다. 이것을 다른 기호로 나타낸 것이 팩토리얼입니다. 즉, \(P(n,n)=n!\)입니다.

한편, 위의 경우, \(n\)개 중에서 \(k\)개를 줄 세우는 것을 팩토리얼을 사용해서 나타내면 아래와 같습니다:

\(\quad\)\(\begin{align}
P(n,k) & =n\cdot (n-1) \cdot (n-2)\cdots (n-k+1) \\
& = \frac{n\cdot (n-1) \cdot (n-2)\cdots (n-k+1)\cdot (n-k) \cdots 2 \cdot 1}{(n-k)\cdots 2 \cdot 1} \\
& =\frac{n!}{(n-k)!} 
\end{align}\)

위 식에서 \(n=k\)일 때에도 식이 성립하려면, \(0!=1\)로 설정해야 합니다.

영 팩토리얼

위에서 언급된 것처럼 \(0\)의 팩토리얼은 \(1\)로 설정할 필요가 있고, 기호에서, \(0!=1\)입니다.

사실, 영 팩토리얼은 그 의미를 되새겨 보면, "아무것도 줄을 세우지 않음"을 의미하는 것으로 볼 수 있습니다. 수학에서, 아무 것도 없음은, 집합의 원소의 개수의 측면에서는 0이지만, 집합 자체의 개수를 셀 때에는 빈 집합도 하나로 셉니다. 이것은 수학적 상황에 따라 "없다"라는 의미가 다르게 사용될 수 있음을 의미합니다.

여기에서도 이 표기법과 그 값에 대한 여러 동기가 있습니다:

• \(n=0\)에 대해, 곱으로 \(n!\)의 정의는 전혀 숫자-없는 곱과 관련되고, 인수가 없는 곱, 빈 곱(empty product)이 곱셈 항등원과 같다는 더 넓은 관례의 예제이기도 합니다.
• 영 대상의 정확하게 하나의 순열이 있습니다: 줄 세우려는 것이 없으면, 유일한 재-배열은 아무것도 하지 않는 것, 1개입니다.
• 이 관례는 조합론(combinatorics)에서 많은 항등식을 그것들의 매개변수의 모든 유효한 선택에 대해 유효하게 만듭니다. 예를 들어, \(n\) 집합에서 모든 \(n\) 원소를 선택하는 방법의 숫자는 \(\tbinom{n}{n} = \tfrac{n!}{n!0!} = 1\)이며, \(0!=1\)일 때만 유효한 이항 계수(binomial coefficient) 항등식입니다.
• \(0!=1\)과 함께, 팩토리얼에 대해 재귀 관계는 \(n=1\)에서 유효하게 남습니다. 그러므로, 이 관례와 함께, 팩토리얼의 재귀(recursive) 계산은 기본 경우(base case)로 영에 대해 값만 가질 필요가 있으며, 계산을 단순화하고 추가적인 특수 경우에 대한 필요성을 피합니다.
• \(0!=1\)를 설정하는 것은 지수 함수(exponential function)를 거듭제곱 급수(power series)와 같은 많은 공식의 간결한 표현을 허용합니다: \(e^x = \sum_{n = 0}^\infty \frac{x^n}{n!}.\)
• 이 선택은 감마 함수(gamma function) \(0! = \Gamma(0+1) = 1\)를 조화롭게 하고, 감마 함수는 이 값을 연속 함수(continuous function)로 가져야 합니다.