Permutation
개요
“ 서로 다른 [math]\displaystyle{ n }[/math]개의 원소에서 [math]\displaystyle{ r }[/math]개를 중복없이 골라 순서에 상관있게 나열하는 것을 [math]\displaystyle{ n }[/math]개에서 [math]\displaystyle{ r }[/math]개를 택하는 순열이라고 한다. “
기호로는 [math]\displaystyle{ _nP_r, P\left(n,r\right) }[/math]등 여러가지가 있지만 자주 쓰이는 것은 [math]\displaystyle{ _nP_r }[/math]이다.
뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념중 하나다.[1] 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 수식으로 나타내면 [math]\displaystyle{ _nP_r=n\times\left(n-1\right)\times\left(n-2\right)\times\cdots\times\left(n-r+1\right) }[/math]이다.[2] 이를 팩토리얼을 사용하여 좀더 간략화 하면 [math]\displaystyle{ _nP_r=n!/\left(n-r\right)! }[/math]이다.
다만, 위 정의에서 몇 가지 문제가 발생하는데 그 중 하나가 바로 0!이다. 상식적으로 생각해 봤을 때, n개중에 n개를 중복없이, 순서에 맞게 고르는 방법은 n!이다. 다만 이를 수식으로 나타내면 [math]\displaystyle{ _nP_n=n!/\left(n-n\right)!=n!/0! }[/math]이 되고, 답과 대응시키기 위해서는 [math]\displaystyle{ 0!=1 }[/math]라 정의되어야 한다. 이에 대한 자세한 내용은 팩토리얼 참조. 다른 하나는 [math]\displaystyle{ _nP_0 }[/math]. 역시 상식적으로 생각했을 때, n개중에 0개를 고르는 방법은 딱 한가지 뿐이지만, 수식으로 나타낼 수는 없다 (n부터 시작해서 하나씩 작은수를 0개 곱한다는 것이 상상이 되는가?). 따라서 [math]\displaystyle{ _nP_0=1 }[/math]로 정의한다.
중복순열
순열과 마찬가지로 n개 중에 r개를 순서에 상관있이 뽑는데, 중복을 허락하여뽑는 것을 말한다. 역시 거창한 설명이지만 초등학교 때부터 써온 수학적 개념. 계산하는 방법 역시 초등학교에서 해왔던 방법과 동일하다. 지수를 사용해 경우의 수를 나타내면 [math]\displaystyle{ n^r }[/math]이 된다.[3]
같은 것이 있는 경우의 순열
n개 중에 r개를 중복없이 순서에 맞게 뽑는데, n개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 개의 문자 [math]\displaystyle{ a, a, b }[/math]를 일렬로 늘어놓는 순열의 수를 찾아보자. 직접 찾아보면 [math]\displaystyle{ aab, aba, baa }[/math]의 3가지 경우 밖에 없다. 여기서 좀더 관찰 해보면 3개를 일렬로 늘어놓는 순열의 수는 [math]\displaystyle{ _3P_3=3!=6 }[/math], 중복되는 문자는 2개이고, [math]\displaystyle{ 3=6/2 }[/math]이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수, 즉 이 예시에서는 2!이 된다.
중복되는 것이 다른 종류로 여러가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
[math]\displaystyle{ a, a, a, \cdots, a, b, b, b, \cdots, b, c, d }[/math](a가 p개, b가 q개, 전체 n개)의 순열의 수 [math]\displaystyle{ =\frac{n!}{p!\times q!} }[/math]
원순열
n개를 나열하는데, 원형으로 나열하는 경우의 수를 말한다. 예를들어 a, b, c, d를 원형으로 나열하는 가짓 수를 찾는다 하자. 얼핏 생각하면 [math]\displaystyle{ 4!=24 }[/math]이라 말하기 쉽지만 처음 놓는 문자의 위치는 어디든지 다 똑같다. 원을 돌려버리면 그만이기 때문. 하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 [math]\displaystyle{ \left(4-1\right)!=6 }[/math]이 된다. 이를 일반적으로 나타내면 아래와 같다.
[math]\displaystyle{ n }[/math]개의 물체를 원형으로 나열하는 수 [math]\displaystyle{ =\left(n-1\right)! }[/math]
뒤집어 놓을 수 있는 원순열의 수
염주순열, 혹은 목걸이순열이라고도 불린다.[4] n개를 나열하는데, 회전할 수도 있고(원), 정면과 후면에서 바라 볼 수도 있을 때의(마치 목걸이를 뒤집듯이) 경우의 수를 말한다. 좌우 대칭을 했을 때 겹칠 수 있다면 한가지로 취급하므로 일반적인 경우의 수는 [math]\displaystyle{ \frac{\left(n-1\right)!}{2} }[/math]이다.
예시
순열
10명중 3명을 뽑아 일렬로 세우는 경우의 수: [math]\displaystyle{ _{10}P_3=10!/\left(10-3\right)!=10!/7!=720 }[/math]
중복순열
네 개의 숫자 0, 1, 2, 3을 써서 (중복 허락) 세 자리 자연수를 만드는 가짓수: 첫 자리에 올 수 있는 가짓수 = 3, 나머지 자리에 올 수 있는 가짓수 [math]\displaystyle{ =4^2 }[/math]. 곱의 법칙에 의해 [math]\displaystyle{ 3\times4^2=48 }[/math].
같은 것이 있는 경우의 순열
wiki의 네 문자를 일렬로 나열할 때의 가짓수: [math]\displaystyle{ \frac{4!}{2!}=12 }[/math]
원순열
서로 다른 5개의 구슬을 원형으로 나열하는 가짓수: [math]\displaystyle{ \left(5-1\right)!=4!=24 }[/math]
목걸이 순열
서로 다른 5개의 구슬로 목걸이를 만드는 방법의 가짓수: [math]\displaystyle{ \frac{1}{2}\left(5-1\right)!=12 }[/math]