📊 순열 (Permutation)

1. 순서대로 뽑고 나열하기 - 구슬 꺼내기

---

 예를 들어, 서로 다른 색의 구슬 7개가 담긴 주머니가 있다고 가정합시다. 여기서 순서대로 하나씩 뽑아 나열한다고 했을 때, 첫번째 뽑을 경우의 수는 '7'입니다. 주머니에는 6개의 구슬만 남아있겠죠? 두번째에 뽑을 경우의 수는 '6'이 됩니다. 세번째도 마찬가지로 구슬 5개 중 하나를 뽑게되므로 '5'가 되겠죠. 이 세가지의 뽑아 나열하는 경우의 수는 '곱의 법칙'을 이용하게 됩니다. 정리해봅시다.

• 첫 번째 뽑을 경우의 수 = 7
• 두 번째 뽑을 경우의 수 = 6
• 세 번째 뽑을 경우의 수 = 5
  
  
• 3개를 순서대로 뽑아 나열하는 경우의 수
  : 7 x 6 x 5 = 210가지 (비복원추출)

이것을 순열(permutation)이라고 합니다.

2. 순열 (permutation)

---

 다음은 순열에 대한 수학적 정의를 내린 것입니다.

이와 같이 순열은 비복원추출을 바탕으로 서로 다른 값을 순서대로 뽑고 나열하는 경우의 수를 의미합니다.

순열(permutation) : 비복원추출을 바탕으로, 서로 다른 값을 순서대로 뽑고 나열하는 경우의 수

 위 '구슬 꺼내기' 예시는 구슬을 꺼낸 뒤, 구슬을 다시 주머니로 넣지 않습니다. 이것을 '비복원추출'이라고 합니다.
만약 구슬을 꺼낸 뒤 다시 그 구슬을 넣으면, 이것을 '복원추출'이라고 합니다.

 복원추출을 바탕으로 하는 구슬 꺼내기 실습을 통해 알아봅시다. 동일한 확률 상황(구슬 3개를 순서대로 꺼내어 나열하기)을 바탕으로, 뽑을 때마다 다시 구슬을 넣는다는 조건을 두고 순열을 구하게 된다면 다음과 같습니다.

• 첫 번째 뽑을 경우의 수 = 7 (다시 복원)
• 두 번째 뽑을 경우의 수 = 7 (다시 복원)
• 세 번째 뽑을 경우의 수 = 7 (다시 복원)
  
  
• 3개를 순서대로 뽑아 나열하는 경우의 수
  = 7 x 7 x 7 = 343가지 (복원추출)

 위와 같은 순열을 '중복 순열'이라고 합니다. 순열을 구할 때, 과거 경우의 수를 현재 경우의 수에서도 중복해서 뽑을 수 있기 때문이죠.

3. 중복 순열

---

 중복 순열의 정의는 다음과 같습니다.

서로 다른 원소 중 복원 추출을 바탕으로 몇 개의 원소를 순서대로 뽑고 나열하는 경우의 수

 다음은 중복 순열의 수학적 정의입니다.

4. 팩토리얼 (Factorial, 계승)

---

 앞서 말씀드렸던 순열의 수학적 정의를 다른 방식으로 표현하는 방법이 있습니다. 바로 '팩토리얼(Factorial)'이라고 합니다. 정의는 다음과 같습니다.

팩토리얼 : 자연수 n에 대하여, n~1까지의 모든 수를 곱한 것

 다음은 팩토리얼의 수학적 정의입니다.

 그러면 위의 '구슬 꺼내기' 예시의 순열 공식에 적용해봅시다. 일반 순열 공식에 팩토리얼을 적용했을 때, 아래와 같습니다.

7개의 구슬 중 3개를 뽑아 일렬로 나열하는 경우의 수는

5. 동자순열 (같은 것이 있는 순열)

---

 만약 색깔이 있는 구슬 7개에 대해, 3개는 빨강, 2개는 초록, 2개는 파랑 색깔을 가졌다고 가정해봅시다. 여기서 각 색깔마다 구슬을 나열할 경우의 수는 다음과 같습니다.

• 빨강(3개) : 3! = 3x2x1 = 6
• 초록(2개) : 2! = 2x1 = 2
• 파랑(2개) : 2! = 2x1 = 2

 우선 빨간색만 나열할 경우의 수는 6개로 아래 그림과 같습니다. 이 경우, 어쨋든 나오는 순서는 '빨-빨-빨-초-초-파-파'로 순서는 변하지 않습니다. 즉, 알파벳을 제거하고 볼 때 아래 그림에서는 중복이 발생하는 것입니다.

 여기서 초록색과 파란색을 나열하는 경우의 수는 각각 '2!', '2!'이며, 이는 모두 각 색깔을 나열할 때 발생하는 중복 경우의 수입니다. 이를 모두 곱할 경우, 구슬 전체를 나열할 때 발생할 수 있는 중복 경우의 수가 되겠죠.

 그러면 전체 구슬을 나열하는 경우의 수에서 중복 경우의 수를 빼줘야겠죠? 아닙니다. 여기서 핵심은 전체 경우의 수에서 중복 경우의 수를 나눠주는 것입니다. 아래는 간단한 예시입니다.

 위와 같이 각 그룹(패턴)마다 중복 경우의 수가 동일한 개수로 나타납니다. 즉, 전체 경우의 수에서 전체 중복 경우의 수를 나눠야 각 그룹의 중복 경우의 수를 없앨 수 있습니다. 이를 '동자순열'이라고 합니다.

 다음은 동자순열에 대한 수식입니다.

 다시 돌아와서, 구슬 7개 중 빨강 3개, 초록 2개, 파랑 2개의 구슬을 일렬로 나열하는 경우의 수는 다음과 같습니다.

6. 원순열 (Circular Permutation)

---

 아래와 같이 5명의 인원이 책상에 둘러 앉아있다고 가정해봅시다.

 이때, 옆자리로 한 칸 씩 이동하게 된다면 다음 그림과 같을 것입니다.

 자리를 한 칸 씩 옮겨도 인원의 순서는 동일합니다. 즉, 여기서도 중복 경우의 수가 존재한다는 것인데요. 이같은 경우에, 전체 중복 경우의 수는 원소 개수와 같습니다. 동자순열과 동일하게 전체 경우의 수를 전체 중복 경우의 수로 나누어 줘야 하는데요. 이를 '원순열'이라고 합니다.

 다음은 원순열에 대한 수식입니다.

💡 정리

---

1. 서로 다른 원소 중 몇 개의 원소를 순서대로 뽑아 나열하는 경우의 수를 '순열'이라고 한다.
   
   
2. 기본 순열에 복원 추출을 바탕으로 구하는 경우의 수를 '중복 순열'이라고 한다.
   
   
3. 자연수 n에 대하여, n~1까지의 모든 수를 곱한 것을 팩토리얼이라고 한다. 팩토리얼을 이용해 순열에 대한 수식을 나타낼 수 있다.
   
   
4. 동자 순열은 전체 원소를 나열할 때 발생하는 경우의 수를 전체 중복 경우의 수(서로 다른 그룹 원소에서의 경우의 수)로 나눈 값이다.
   
   
5. 원순열은 전체 원소를 나열할 때 발생하는 경우의 수를 전체 중복 경우의 수(원소 개수)로 나눈 값이다.

참고 자료

• [확률과 통계] 4. 순열(1), Permutation
• [확률과 통계] 5. 순열(2), Permutation