[기초 통계] 5. 순열: Permutation

  각각 1부터 8까지 숫자가 적혀 있는 여덟 개의 카드가 있다. 이 때 1부터 8까지 8장의 카드 중 3장을 뽑아 일렬로 나열하는 시행을 한다고 가정하자.

 

  맨 처음 카드를 뽑을 때는 전체 8장 중 8장을 뽑을 수 있다. 그러나 그 다음에는 이미 뽑힌 한 장을 제외한 나머지 7장에서 뽑아야 하고, 그 다음에는 앞서 뽑힌 두 장을 제외한 나머지 6장에서 뽑아야 한다.

 

  그럼 해당 시행에서 나올 수 있는 경우의 수는 처음의 8, 중간의 7, 마지막의 6을 서로 곱한 $$ 8 * 7 * 6 = 336 $$ 만큼 존재한다고 할 수 있다. 이 때 이 경우의 수들은 결과적으로 같은 카드들이 뽑혔더라도 각 카드들이 뽑힌 순서에 따라 서로 다른 경우의 수로 보게 된다. 예를 들어 8, 7, 6과 6, 7, 8의 경우의 수는 서로 다른 경우의 수로 본다.

 

  이처럼 서로 다른 n개의 원소에서 r개의 원소를 중복 없이(비복원추출), 순서에 상관 있게 추출하는 것을 순열(Permutation)이라고 부른다.

 

  n개에서 r개를 추출하는 순열의 기본적인 공식은 아래와 같다.

 

$$ _{n}P_{r} = \frac{n!}{(n-r)!} $$

 

  이 때 서로 다른 n개의 원소에서 r개의 원소를 중복을 허용하여(복원추출), 순서에 상관 있게 추출하는 경우도 생각해 볼 수 있다. 이런 경우는 중복 순열(Permutation with repetition)이라고 부른다.

 

  n개에서 r개를 추출하는 중복 순열의 공식은 아래와 같다.

 

$$ _{n}\Pi_{r} = n^{r} $$

 

  또 서로 동일한 원소 몇 개가 존재하는 경우의 순열을 동자 순열(Permutation of multisets)라고 한다. 예를 들어 'bamboo'라는 문자열을 재배열하려고 하는 경우, 'b'와 'o'가 각각 두 개씩 들어가 있는 경우를 생각해 볼 수 있다. 이 때 'b'와 'o'는 분명 여러 개지만, 서로 완전히 같은 원소로 취급하여 그 순서를 신경쓰지 않는다.

 

  그럼 이 6개의 문자를 겹치는 문자의 개수 2개를 고려하여 계산한 동자 순열의 개수는 아래와 같다.

 

$$ \frac{6!}{2!2!} $$

 

  즉, 전체 원소의 개수 n의 팩토리얼을 겹치는 원소의 개수 r의 팩토리얼로 나누는 것과 같다.

 

  서로 다른 원소를 원형의 형태로 나열하는 순열은 원순열(Circular permutation)이라고 한다. 예를 들어 a, b, c, d, e 다섯 개의 원소를 나열하는 경우, 단순히 5! = 120개의 경우의 수가 존재한다고 생각할 수 있으나 실제로는 원형으로 순열이 나열되기 때문에 원을 돌려버리면 서로 다른 줄 알았던 순열도 알고 보니 같은 순열이었다는 것을 알 수 있다. 일례로 'abcde'와 'bcdea'는 원순열의 경우 동일한 순열로 취급되는 것이다.

 

  n개의 원소를 나열하는 원순열의 공식은 아래와 같다.

 

$$ (n-1)! $$

 

  아래는 순열에 대한 간단한 예제이다.