[모듈식 확률과 통계] 1.경우의 수 (7)같은 것이 있는 순열

[확률과통계]-[1.경우의 수]-[(6)순열과 조합]-[(7)같은 것이 있는 순열]

같은 것이 있는 순열

아래 예시로 시작해봅시다. 

a,a,b

위의 세개 문자를 배열해봅시다. 

일단 같은 것이 없다고 생각하고 세개의 문자를 배열하는 경우의 수는 아래와 같습니다. 

3x2x1=6

여기서 겹치는 경우를 없애 보겠습니다. 편의상 a 두개를 a₁과 a₂로 나눠서 배열해보겠습니다. 

a₁ a₂ b

a₂ a₁ b

a₁ b a₂

a₂ b a₁

b a₁ a₂

b a₂ a₁

이렇게 여섯가지입니다. a₁과 a₂가 같은 문자이기 때문에, 아래 같은 색으로 칠한 경우들은 겹치는 경우입니다. 

a₁ a₂ b

a₂ a₁ b

a₁ b a₂

a₂ b a₁

b a₁ a₂

b a₂ a₁

따라서 결과를 2로 나눠주어야 합니다. 여기서 '2'라는 것은 '중복되는 문자의 개수'를 배열하는 수와 같습니다. 

중복되는 문자를 하나 늘려봅시다. 

a,a,a,b

같은 것이 없다고 생각하고 배열하면 4x3x2x1=24 가지 입니다. 여기서 겹치는 경우를 없애 보겠습니다. 편의상 a 세개를 a₁, a₂, a₃로 나눠서 배열해보겠습니다. 경우가 너무 많기 때문에 a가 연달아 나오고 마지막에 b가 오는 상황만을 고려해봅시다. 

a₁ a₂ a₃ b

a₁ a₃ a₂ b

a₂ a₁ a₃ b

a₂ a₃ a₁ b

a₃ a₁ a₂ b

a₃ a₂ a₁ b

위의 여섯가지 경우가 중복됩니다. 결과가 6배로 부풀려졌다는 의미입니다. 따라서 24를 6으로 나눠주어야 합니다. 여기서 '6'이라는 값이 어떻게 나온 것일까요? '중복되는 문자의 개수'를 배열하는 수와 같습니다. 중복되는 문자는 a 3개이므로, 3개를 배열하는 3x2x1=6 으로 나눠주는 것입니다. 

그런데, 만약 이렇게 중복된다면 어떻게 나눠줘야 할까요? 

a,a,b,b

중복되는 문자가 총 4개이므로 4x3x2x1로 나눠주어야 할까요? 두 문자를 따로 생각해주어야 합니다. 2로 두번 나눠주어야 하는 것입니다. a때문에 두배로 부풀려지고, b때문에 다시 두배로 부풀려졌기 때문입니다. 

일반화시켜봅시다. 

문자가 n개 있습니다. 그 중 서로 같은 문자가 p개, q개, ..., r개씩 있습니다. n개를 일렬로 배열하는 경우의 수는 아래와 같습니다.