Permutation
1 개요
서로 다른 [math]n[/math]개의 원소에서 [math]r[/math]개를 중복없이 골라 순서에 상관있게 나열하는 것을 [math]n[/math]개에서 [math]r[/math]개를 택하는 순열이라고 한다
기호로는 [math]_nP_r, P\left(n,r\right)[/math]등 여러가지가 있지만 자주 쓰이는 것은 [math]_nP_r[/math]이다.
뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념중 하나다[1]. 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 수식으로 나타내면 [math]_nP_r=n\times\left(n-1\right)\times\left(n-2\right)\times\cdots\times\left(n-r+1\right)[/math][2]. 이를 팩토리얼을 사용하여 좀더 간략화 하면 [math]_nP_r=n!/\left(n-r\right)![/math]이다.
다만, 위 정의에서 몇가지 문제가 발생하는데 그 중 하나가 바로 0!이다. 상식적으로 생각해 봤을 때, n개중에 n개를 중복없이, 순서에 맞게 고르는 방법은 n!이다. 다만 이를 수식으로 나타내면 [math]_nP_n=n!/\left(n-n\right)!=n!/0![/math]이 되고, 답과 대응시키기 위해서는 [math]0!=1[/math]라 정의되어야 한다. 이에 대한 자세한 내용은 팩토리얼 참조. 다른 하나는 [math]_nP_0[/math]. 역시 상식적으로 생각했을 때, n개중에 0개를 고르는 방법은 딱 한가지 뿐이지만, 수식으로 나타낼 수는 없다 (n부터 시작해서 하나씩 작은수를 0개 곱한다는 것이 상상이 되는가?). 따라서 [math]_nP_0=1[/math]로 정의한다.
2 중복순열
순열과 마찬가지로 n개 중에 r개를 순서에 상관있이 뽑는데, 중복을 허락하여 뽑는 것을 말한다. 역시 거창한 설명이지만 초등학교 때부터 써온 수학적 개념. 계산하는 방법 역시 초등학교에서 해왔던 방법과 동일하다. 지수를 사용해 경우의 수를 나타내면 [math]n^r[/math]이 된다. 고등학교 확률과 통계 교과서에서는 [math]_n\Pi_r[/math]이라는 표현을 쓰는데, 이는 한국에서만 쓰이는 출처 불명의 기호로, 세계적으로는 그냥 [math]n^r[/math]라 나타낸다.
3 같은 것이 있는 경우의 순열
n개 중에 r개를 중복없이 순서에 맞게 뽑는데, n개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 개의 문자 [math]a, a, b[/math]를 일렬로 늘어놓는 순열의 수를 찾아보자. 직접 찾아보면 [math]aab, aba, baa[/math]의 3가지 경우 밖에 없다. 여기서 좀더 관찰 해보면 3개를 일렬로 늘어놓는 순열의 수는 [math]_3P_3=3!=6[/math], 중복되는 문자는 2개이고, [math]3=6/2[/math]이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수, 즉 이 예시에서는 2!이 된다.
중복되는 것이 다른 종류로 여러가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
[math](a_1, a_1, \cdots, a_1), (a_2, a_2, \cdots, a_2), \cdots, (a_n, a_n, \cdots, a_n)[/math]일 때, 즉 [math]a_1[/math]이 [math]p_1[/math]개, [math]a_2[/math]가 [math]p_2[/math]개, [math]\cdots[/math], [math]a_n[/math]이 [math]p_n[/math]개일 때의 순열의 수 [math]=\frac{(p_1+p_2+\cdots+p_n)!}{p_1!\times p_2!\times \cdots\times p_n!}[/math]
4 원순열
n개를 나열하는데, 원형으로 나열하는 경우의 수를 말한다. 예를들어 a, b, c, d를 원형으로 나열하는 가짓 수를 찾는다 하자. 얼핏 생각하면 [math]4!=24[/math]이라 말하기 쉽지만 처음 놓는 문자의 위치는 어디든지 다 똑같다. 원을 돌려버리면 그만이기 때문. 하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 [math]\left(4-1\right)!=6[/math]이 된다. 이를 일반적으로 나타내면 아래와 같다.
[math]n[/math]개의 물체를 원형으로 나열하는 수 [math]=\left(n-1\right)![/math]
5 뒤집어 놓을 수 있는 원순열의 수
염주순열, 목걸이순열이라고도 불린다[3]. n개를 나열하는데, 회전할 수도 있고(원), 정면과 후면에서 바라 볼 수도 있을 때의(마치 목걸이를 뒤집듯이) 경우의 수를 말한다. 좌우 대칭을 했을 때 겹칠 수 있다면 한가지로 취급하므로 일반적인 경우의 수는 [math]\frac{\left(n-1\right)!}{2}[/math]이다. 단, [math]n\lt3[/math]일 때는 왼쪽의 식이 성립하지 않으므로 1로 취급한다.
6 완전순열
교란순열이라고도 불린다. 완전순열은 n명의 사람이 각각 자신의 모자를 벗어두었다가, 다시 쓰는데 모든 사람이 자기 것이 아닌 모자를 쓰는 방법의 수라고 할 수 있다. [math] D_n [/math] 또는 [math] !n [/math] (subfactorial)로 나타낸다.
보통 [math] D_4 [/math]정도는 고등학교 과정에서도 물어보는 경우가 있는데 수형도를 그려서 경우의 수를 구하면 [math] D_4=9 [/math]이다. 하지만 [math] D_5 [/math]이상은 수형도를 그리기가 매우 힘들어지므로 다음과 같은 점화식을 이용한다. [math] D_n=(n-1)(D_{n-1}+D_{n-2}) [/math]
이 점화식을 유도하는 방법은 이렇다. 1부터 n까지의 자연수를 한 줄 써 놓고, 아랫줄에도 한 줄 더 쓴다. 윗줄의 숫자들이 아랫줄의 숫자들로 하나하나씩 대응시킬 때 자기 자신을 제외한 다른 숫자로 대응을 시키면 된다. 이렇게 대응시키는 방법의 수를 센 것이 [math] D_n [/math]이다.
이러한 모든 대응들을 두가지 부류로 나눌 수 있다. (1) 1이 k로 갔고, k는 1로 갔다. (2) 1이 k로 갔고, k는 1로 가지 않았다. (단, k는 2이상 n이하의 어떤 자연수) (1)의 경우, 1,k는 대응이 되었고, 나머지를 대응시키면 되는데 그 경우의 수는 [math] D_{n-2} [/math]임을 알 수 있다. (2)의 경우, 1은 대응됐고, 나머지를 대응시키면 되는데 그 경우의 수는, k가 1로 가면 안 되기 때문에 결국 n-1가지를 교란시키는 경우의 수와 같으므로, [math] D_{n-1} [/math]이다. 그리고 k로 가능한 수는 n-1가지가 있으므로 전체 경우의 수는 [math] D_n=(n-1)(D_{n-1}+D_{n-2}) [/math]
점화식을 얻으면 일반항에 한걸음 다가간 것이다. 매우 교묘하게도, 위 점화식은 다음과 같이 변형될 수 있다. [math] D_n - nD_{n-1}=-(D_{n-1} - (n-1)D_{n-2}) [/math] 여기서 좌변을 [math] a_n [/math]으로 정의하면, 우변은 [math] -a_{n-1} [/math]이 되므로 수열 [math] a_n [/math]은 등비수열이다. [math] a_3=D_3-3D_2=-1 [/math]이므로 [math] a_n=(-1)^n [/math]이다. 따라서 [math] D_n-nD_{n-1}=(-1)^n [/math] 이 된다.
여기서, 양변을 n!로 나눈다. 그러면 [math]\displaystyle\ {D_n\over n! }-{D_{n-1}\over (n-1)!}={(-1)^n\over n!} [/math] 이를 이항해서 정리하면 [math]\displaystyle\ {D_n\over n! }={D_{n-1}\over (n-1)!}+{(-1)^n\over n!} [/math] 이 되므로 전형적인 점화식 꼴이 된다. 하나씩 대입하면서 더해나가면 일반항은 다음과 같다. [math]\displaystyle\ D_n= n!({1\over 2!} - {1\over 3!} + ... +{(-1)^n\over n!})[/math] 이것을 퍼뮤테이션으로 나타내면 [math]\displaystyle\ D_n = \sum_{r=2}^{n}{_nP_{n-r}}(-1)^r = \sum_{r=0}^{n}{_nP_{n-r}}(-1)^r [/math]
7 예시
순열
10명중 3명을 뽑아 일렬로 세우는 경우의 수: [math]_{10}P_3=10!/\left(10-3\right)!=10!/7!=720[/math]
중복순열
네 개의 숫자 0, 1, 2, 3를 써서 세 자리 자연수를 만드는 가짓수(중복을 허락): 첫 자리에 올 수 있는 가짓수 = 3, 나머지 자릿수에 올 수 있는 가짓수 = [math]4^2[/math]. 곱의 법칙에 의해 [math]3\times4^2=48[/math]
같은 것이 있는 경우의 순열
wiki의 네 문자를 일렬로 나열할 때의 가짓수: [math]\frac{4!}{2!}=12[/math]
원순열
서로 다른 5개의 구슬을 원형으로 나열하는 가짓수: [math]\left(5-1\right)!=4!=24[/math]
목걸이 순열
서로 다른 5개의 구슬로 목걸이를 만드는 방법의 가짓수: [math]\frac{1}{2}\left(5-1\right)!=12[/math]
완전순열(교란순열)
5명의 사람이 시험을 보고 시험지를 채점하는데 자기 게 아닌 시험지를 채점하게 하는 방법의 가짓수: [math] D_5={_5P_3}-_5P_2+_5P_1-_5P_0=44 [/math]