[이산수학] 조합이론 - Part 1. 순열과 조합의 차이 (feat. 팩토리얼)

순열(Permutation)이란?

모든 순열의 수 :

• n개의 항목을 가지고 k개를 선택하면서 순서를 고려하는 경우의 수(= 순열의 수)는 n⋅(n−1)⋅(n−2)⋯(n−k+1)이다. 
  • 처음 상태: 총 n개의 항목이 있음.
  • 1번째 선택 후: 1개를 뽑았으므로 n−1개 남음.
  • 2번째 선택 후: 또 1개를 뽑았으므로 n−2개 남음.
  • 3번째 선택 후: n−3개 남음.
  •  ...
  • (k-1)번째 선택 후: k−1개를 이미 뽑았으므로 n−(k−1)개 남음.
  • 이제 k번째 선택을 해야 하는데, 이 때 남아 있는 항목의 수는 n−(k−1)개.
• "k번째 선택"은 총 k번 선택 중 마지막 번째를 의미함. 따라서 이미 k−1번을 선택한 후 남은 항목에서 하나를 더 고르는 상황.
• 남은 항목 수 = n−(k−1) = n-k+1

정리하면, 전체 순열의 수는 n⋅(n−1)⋅(n−2)⋯(n−k+1)

 

이를 계승(factorial)으로 표현하면:

이유: n!은 n까지의 모든 곱이지만, (n−k)!을 나누면 n−k 이하의 항목이 제거되어 n부터 n−k+1까지의 곱만 남음.

 

왜 계승(factorial)을 사용할까?

계승(n!)은 "n개의 항목을 모두 나열하는 방법의 수"를 타나낸다. 조합에서 계승을 쓰는 이유는 선택할 수 있는 모든 경우를 체계적으로 세기 위해서이다.

• n! = n⋅(n−1)⋅(n−2)⋯1
• 예: 3! = 3⋅2⋅1 = 6 (3명에게 1, 2, 3번 순서를 부여하는 경우의 수).

조합(Combination)이란?

• 순서에 상관없이 n개 중 k개를 고르는 방법의 수를 세는 것.

예: 3명의 친구(A, B, C) 중 2명을 고를 때, {A, B}와 {B, A}는 같은 경우로 본다. (순서 상관없음).

순열(Permutation)에서는 순서가 다르면 다른 경우로 보지만, 조합에서는 순서가 중요하지 않으므로, k!을 나누어 중복을 제거.

• k!은 "k개의 항목을 나열하는 모든 가능한 순서의 수"를 뜻한다. 조합에서 같은 k개를 선택하더라도 순서를 바꾸는 방법이 k!가지 존재한다. 이 순서에 따른 중복을 없애기 위해 k!을 나누는 것이다.

위 내용을 정리하면,