[통계학] 2강. 경우의 수

1. 개요

   1번부터 5번까지 적혀있는 공이 들어있는 주머니에서 3개의 공을 추출하는 경우의 수를 생각해봅시다. 이 때 추출하는 방법에 따라 경우의 수가 달라지게 됩니다. 복원 추출 (with-replacement) 방법은 이미 추출한 공을 다시 주머니에 넣고 추출하는 방법이고, 비복원 추출 (without-replacement) 방법은 이미 추출한 공을 다시 넣지 않고 추출하는 방법입니다. 예를 들어 공을 한꺼번에 3개 뽑는다고 한다면, 비복원 추출 방법이 되겠지요.

   이제 주머니에서 뽑은 3개의 공을 나열하는 경우의 수를 생각해봅시다. 이 때 뽑힌 순서를 고려하여 나열하는 경우의 수와, 순서를 고려하지 않고 나열하는 경우의 수가 다르겠지요. 예를 들어 순서를 고려한다면 (1,3)과 (3,1)은 다른 경우의 수입니다. 반면 순서를 고려하지 않는다면 (1,3)과 (3,1)은 하나의 경우의 수로 처리됩니다.

   즉 추출 방법과 배열 순서에 따른 경우의 수는 아래 표와 같습니다.

Figure 1. 추출방법과 배열 순서에 따른 경우의 수

 

2. 순열 (permutation)

   Figure 1. 에서, 순서를 고려하면서 비복원 추출하는 경우의 수를 순열이라고 합니다. 반면 순서를 고려하면서 복원 추출하는 경우의 수는 중복순열 (permutation with repetition)이라고 합니다. 순열 중에서도 같은 것이 있는 순열을 동자순열 (permutation of multisets), 원탁에 둘러앉는 경우의 수를 원순열 (circular permutation)이라고 합니다.

 

3. 조합 (combination)

   Figure 1. 에서, 순서를 고려하지 않으면서 비복원 추출하는 경우의 수를 조합이라고 합니다. 조합의 가짓수를 이항 계수라고도 부르며, 다음과 같은 식으로 풀이 가능합니다.

이항계수의 정의. 단, k는 0 이상 n 이하의 자연수이다.

   이항계수의 값을 삼각형 모양으로 나열한 표를 파스칼의 삼각형이라고 합니다.

Figure 2. 이항계수와 파스칼의 삼각형

 

4. 중복조합 (combination with repetition)

   중복조합은 순서를 고려하지 않는 추출이라는 점에서 조합과 비슷하지만, 복원추출 방식입니다. 예를 들어 서로 다른 n종류의 상자 k개를 뽑는 경우를 생각해봅시다. 상자를 ㅁ 로 표현하고, k개의 그룹 간 구분 선을 ㅣ 로 표시한다면,

□ | □ | ··· | □ (단, ㅁ는 k개, l 는 n-1개)

로 표현하게 됩니다. 즉 위 문제는 n+k-1개의 자리에서 상자 (ㅁ)가 들어갈 자리 k개를 선택하는 경우의 수가 되겠지요. 따라서 아래 식이 성립합니다.

   이제 중복조합과 관련된 아래 공식들을 살펴봅시다.

공식 1.

공식 1의 증명은 다음과 같습니다. 아래 식 $$ (a+b)^{n} = {}_n C_{k} \times a_{k} \times b_{n-k} $$ 에 a = 1, b = 1을 대입하면 공식 1이 성립하게 됩니다.

 

공식 2.

공식 2를 더 확장하면 다음 식으로도 표현할 수 있습니다.

 

공식 3.

공식 3을 조합론적으로 해석하면 다음과 같습니다.

• 우변 : 2n개 중 n개를 뽑는 경우의 수
• 좌변 : n개 중 k개를 뽑고, 나머지 n개 중 n-k개를 뽑는 경우의 수

 

공식 4.

공식 4를 증명해봅시다. 먼저 대수적인 해석은 다음과 같습니다.

공식 4.를 조합론적으로 해석하면 다음과 같습니다.

• 좌변 : n개 중 k개를 뽑는 경우의 수
• 우변 : n개 중 특정 1개를 제외한 k개를 뽑거나, n개 중 특정 1개를 포함한 k개를 뽑는 경우의 수

 

공식 5.

공식 5를 대수적으로 해석하면 다음 식과 같습니다.

조합론적으로 해석하면 다음과 같습니다.

• 우변 : 1부터 n+m+1까지의 숫자 중 n+1개를 뽑는 조합의 수
• 좌변
  • \( {}_n C_{n} \) : 1부터 n+m+1까지의 숫자 중 n+1이 가장 큰 숫자가 되는 조합의 수
  • \( {}_{n+1} C_{n} \) : 1부터 n+m+1까지의 숫자 중 n+2가 가장 큰 숫자가 되는 조합의 수
  • \( {}_{n+k} C_{n} \) : 1부터 n+m+1까지의 숫자 중 n+k+1이 가장 큰 숫자가 되는 조합의 수

 

공식 6.

공식 6을 조합론적으로 해석하면 다음과 같습니다.

• 우변 : 앞면 또는 뒷면이 n+1번 나올때까지 동전을 던질 확률
• 좌변
  • \( {}_n C_{n} \times (\frac{1}{2})^{n+1} \times 2\) : 맨 마지막과 같은 면이 n번, 맨 마지막과 다른 면이 0번 나올 확률
  • \( {}_{n+1} C_{n} \times (\frac{1}{2})^{n+2} \times 2 \) : 맨 마지막과 같은 면이 n번, 맨 마지막과 다른 면이 1번 나올 확률
  • \( {}_2n C_{n} \times (\frac{1}{2})^{2n+1} \times 2 \) : 맨 마지막과 같은 면이 n번, 맨 마지막과 다른 면이 n번 나올 확률