순열, 조합 : 똑똑하게 세는 방법

확률 계산의 본질:  경우의 수를 세다. 

기본적으로 확률은 '특정 사건이 발생할 수 있는 방법의 수'를 '가능한 모든 경우의 수'로 나누어 계산합니다.

그러나 문제가 복잡해질수록(예: 10번의 동전 던지기, 포커 패 등) 모든 경우를 일일이 나열하기 어려워집니다.

이때 조합론은 가능한 모든 경우의 수를 효율적으로 세는 방법을 제공합니다.

몇 가지 기본적인 계산 공식만 알아도 포커, 주사위 게임, 백개먼 등 다양한 게임의 확률을 쉽게 계산할 수 있습니다.

동전 던지기

첫 번째 예제로, 동전을 10번 던질 때 가능한 모든 고유한 순서의 수를 계산해 봅시다.

여기서 중요한 개념은 순서가 중요하다(order matters)는 것입니다.

즉, '앞면-뒷면'과 '뒷면-앞면'은 서로 다른 결과로 간주됩니다.

각 동전 던지기에는 2가지 가능한 결과(앞면 또는 뒷면)가 있으며, 던지기는 서로 독립적입니다. 따라서:

• 첫 번째 동전: 2가지 가능성
• 두 번째 동전: 2가지 가능성
• ...
• 열 번째 동전: 2가지 가능성

총 가능한 조합의 수 = 2^10 = 1,024가지

또한 동전 던지기는 복원 추출(with replacement)의 예입니다.

첫 번째 동전에서 앞면이 나와도 두 번째 동전에서 다시 앞면이 나올 수 있습니다.

포커 패 계산하기

다음 예제는 52장의 카드 덱에서 5장을 뽑는 경우의 수입니다. 여기서도 순서가 중요하다고 가정합니다.

이 경우, 카드를 한 번 뽑으면 덱에서 제거되므로 비복원 추출(without replacement)입니다

• 첫 번째 카드: 52가지 가능성
• 두 번째 카드: 51가지 가능성
• 세 번째 카드: 50가지 가능성
• 네 번째 카드: 49가지 가능성
• 다섯 번째 카드: 48가지 가능성

총 가능한 조합의 수 = 52 × 51 × 50 × 49 × 48

Factorial 표기법

확률 계산에서 매우 유용한 표기법이 factorial입니다. n!은 n × (n-1) × (n-2) × ... × 3 × 2 × 1로 정의됩니다.

위의 포커 패 예제는 다음과 같이 표현할 수 있습니다: 52! / 47!

포커 핸드

실제 포커 게임에서는 패의 순서가 중요하지 않습니다. 킹-퀸-7-3-2는 퀸-킹-3-7-2와 동일한 패입니다.

순서가 중요하지 않는 경우, 우리는 순서가 중요한 경우의 수를 r!(순열의 수)로 나누어야 합니다.

왜냐하면 r개의 요소를 재배열하는 방법은 r!가지이기 때문입니다.

따라서 52장의 카드에서 5장을 뽑는 가능한 포커 핸드의 수는: 52!/[47! × 5!] = (52 × 51 × 50 × 49 × 48)/120 = 2,598,960가지

일반화된 공식

이제 이러한 계산을 일반화된 공식으로 정리해 봅시다:

1. 순서가 중요한 경우(order matters)
   • 복원 추출(with replacement): n^r
     • n = 선택할 수 있는 가지 수
     • r = 시행 횟수
   • 비복원 추출(without replacement): n!/(n-r)!
2. 순서가 중요하지 않은 경우(order doesn't matter)
   • 비복원 추출(without replacement): n!/[(n-r)! × r!]