경우의 수 (2) - 순열

1. Permutation(순열)의 정의

1) 순열이란?

• Permutation의 정의는 주어진 원소들로 만들 수 있는 배열(Arrangement, Array)의 수이다.
• 잘 알다시피 배열에는 순서가 "반드시"존재하며 지켜져야한다. (때문에 이름이 "순"열이다)
• e.g. 3개의 원소가 있을 때, Permutation은 6이다 = 3 x 2 x 1 
• 왜냐면 처음에 3개를 뽑고나면 원소 하나가 사라져서 두번째 자리에선 2개, 마지막엔 1개밖에 못뽑는다.
• 처음에 A, B, C가 올 수 있고 여기에서 첫번째 자리에 원소를 뽑을 수 있는 경우의 수는 3이다. 그리고
• 두번째 자리엔 2개, 마지막 자리엔 1개의 경우의 수가 존재하고, 이들은 곱의법칙에 의해 곱해진다.
• (곱의 법칙을 쓰는 이유는 이전글 참조 : "~을 하거나"가 아니라 각 자리 원소를 뽑는게 연속적이기 때문)

 

2) 일반화 예시

• e.g. n개의 원소가 있을 때, Permutation은 = n!이다 = n x (n-1) x (n-2) x ... x 1
• e.g. 5개의 원소가 있을 때, 3개의 원소로 만들 수 있는 Permutation = 5 x 4 x 3이다.
• 공식은 $nPr = n \times (n-1) \times ... (n-r+1)$인데, 그냥 n부터 1씩 빼면서 r개 곱하면 된다.

 

3) 중복순열은?

• 중복순열은 중복을 허용하고 뽑는 것인데 이 경우엔, 복원추출이기 때문에, $n∏r = n^r$이다.
• 생각해보자. 3개의 원소가 있는데 중복해서 뽑아도 된다면, 처음에 3개 두번째 3개 마지막 3개
• 이렇게 3 x 3 x 3의 경우의 수가 존재하기 때문에 그냥 3을 세제곱 한 것과 동일하다.

 

2. Permutation with Repetition (동일원소가 있는 Permutation)

1) 중복되는 원소가 있는 경우에 순열 계산하기 (후에 조합으로 이어진다)

• 같은 원소가 있는 경우의 순열은 어떻게 계산할까? (공식 보지말고 머리로 생각해보자!)
• 만약 [P,E,P,P,E,R]을 배열한다고 가정해보자. 이 때, P1, P3, P4는 모두 같고, E2, E5도 같다
• 그러면 일단 모든것이 다른 원소라고 생각하고 배열하면, 곱의 법칙에 의해 6!이 나온다.
• 우선 6!은 (X, X, X, X, E2, E5)와 (X, X, X, X, E5, E2)를 다른 경우라고 생각하고 계산한 결과이다.
• 그러나 E2=E5이기 때문에 사실 두 경우는 같은 경우였고 다른 경우들이 영향받아서 2가 곱해져있다.
• -> (E2, E5, X, ... X) 와 (E5, E2, X ... X)도 같은 경우인데 다른 경우로 취급 됨 -> 때문에 2!로 나눠준다
• 또 (P1, P3, P4), (P1, P4, P3) ... (P4, P3, P1) = 3 * 2 * 1의 경우 6가지 경우에 의해 다른 모든 경우에
• 6이 곱해져있으므로 6으로 나눈다. 즉, 6! / 2! * 3!이 되고, 답은 6 * 5 * 2 = 60이 된다.

 

2) 일반화와 예시

• Generalize : n개의 원소가 있는데 r개의 원소가 겹치면 Permutation = N! / R!이다.
• e.g. 마라톤에 미국인 4명 중국인3명 영국인2명이 참가했는데 순위에 단순히 나라만
• 기록한다면(같은 국적은 같은 원소로 취급), 경우의 수는 = 9! / 4! * 3! * 2!

 

3. Reference