경우의 수

Number of Cases, Counting Problem

개요

통계학, 확률론의 가장 기본적인 분야이자, 조합론의 한 분야. 의미는 글자 그대로, 어떤 사건에 대해 가능한 모든 경우의 수를 나타낸다. 한국에서 본격적으로 "경우의 수"라는 이름을 달고 나오는 건 중학교지만, 초등학교에서부터 직/간접적으로 계속 사용하는 개념이다.

구하는 방법

간단하다. 상정 가능한 모든 가짓수를 하나도 빠짐 없이, 그리고 중복되지 않게 모두 세면 된다. 여기서 "상정 가능한"은 조건에 맞는 것을 의미하는데, 주사위를 예로 들면 모든 가짓수는 6이지만 짝수라는 조건을 붙이면 세 가지로 줄어드는 것과 같은 의미이다. 중복 없이 하나도 빠짐없이 센다는게 말은 간단하지만, 실제로는 여러 가지 변수가 붙어서 정확하게 세는 것은 상당히 힘들다. 아래 두 법칙을 사용하면 아주 조금 간단해지므로 반드시 알아놓자.

• 합의 법칙

  두 사건이 서로 배반(disjoint)일 때, 두 사건 중 하나가 일어날 경우의 수는 두 사건이 각각 일어날 경우의 수를 합한 것과 같다.

  예를 들어, 사람들의 집합에서 17~19세인 사람들을 뽑고 싶다고 하자. 한 사람의 나이가 17, 18, 19세인 경우는 서로 배반사건이므로, 이 세 사건의 경우의 수를 전부 더해주면 된다.

• 곱의 법칙

  두 사건이 서로 독립(independent)일 때, 두 사건이 같이 일어날 경우의 수는 두 사건이 각각 일어날 경우의 수를 곱한 것과 같다.

  주사위와 동전을 던져서 각각 짝수와 앞면이 나오는 가짓수를 구하고 싶다 하자. 주사위를 던지는 것과 동전을 던지는 것은 서로 관계가 없는, 즉 독립적인 사건이기 때문에 각각의 경우의 수를 구해 곱해주면 된다.

예시는 매우 간단한 것을 들었지만, 실제 문제에서는 위 두 법칙을 복합적으로 사용해야 할 것이다. 어떤 복잡한 사건이라도 조건에 맞춰 가능한 경우의 수를 쪼개면 결국엔 합의 법칙과 곱의 법칙으로 귀결되기 때문. 다만, 쪼개지는 경우의 수가 너무 복잡하다면 그건 아마 문제를 잘못 풀고 있다는 것을 의미한다(...). 그럴 경우에는, 경우의 수를 세는 기준을 다른 방법으로 접근하여보자.

조합론적 증명

[math]\displaystyle{ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} }[/math]

위 등식을 증명하고 싶다고 하자. 처음 보는 사람들은 아마 우변을 전개하여 대수학적인 방법으로 풀텐데, 이러한 증명방법을 대수학적 증명이라고 부른다. 대수학적 증명은 보는 사람 입장에서 매우 직관적이라는 장점이 있지만, 식이 복잡해지면 이해하기도 어렵고 실수를 하게 될 가능성이 커진다는 문제점이 존재한다.

그럼 등식을 복잡한 수식 없이 증명하는 방법이 존재할까? 그 방법 중 하나가 조합론적 증명(Combinatorial proof)이며, 조합론적 증명의 골자는 한 사건을 두 가지 다른 방법으로 세어 각각의 결과가 같음을 보이는 방법이다. 조합론적 증명은 한 사건에 대한 경우의 수를 여러 가지 방법으로 접근할 수 있게 만들어주는 능력을 키우기도 하므로 알아둬서 나쁠 것은 없지만, 상당한 수학적 직관을 필요로하기 때문에 될 사람만 된다(...). 아래는 조합론적 증명의 대표적인 예시.

• [math]\displaystyle{ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} }[/math]

증명 좌변: n개중에 k개를 고르는 경우의 수. 우변: n개 중에 하나를 일단 따로 떼어놓자. 이제 k개를 고를 것인데, 따로 떼어놓은 하나를 포함시키는 경우와 포함시키지 않는 두 경우로 나눌 수 있다. 전자의 경우 나머지 n-1개 중에 k-1개를 고르면 되므로 [math]\displaystyle{ \binom{n-1}{k-1} }[/math]이고, 후자의 경우 n-1개 중에 k개를 고르면 되므로 [math]\displaystyle{ \binom{n-1}{k} }[/math]가 된다. 두 사건은 서로 배반이므로, 전체 가짓수는 [math]\displaystyle{ \binom{n-1}{k}+\binom{n-1}{k-1} }[/math]가 된다.

• [math]\displaystyle{ \sum_{k=0}^nk\binom{n}{k}=n2^{n-1} }[/math]

증명 우변: n명의 사람들 중에 리더를 한 명 고르고, 나머지 n-1의 사람들 중에 리더의 그룹에 포함될 사람들을 뽑는 가짓수와 동일하다. 좌변: 먼저 k명으로 된 그룹을 먼저 만들고, 그 중에서 리더를 한 명 뽑는 것과 같다. 가능한 그룹 인원수는 0부터 n까지 이므로 합의 법칙에 의해 다 더해줘야 한다.

• [math]\displaystyle{ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n} }[/math]

증명 우변: 2n개 중에 n개를 고른 경우의 수. 좌변: 2n을 임의로 n과 n으로 나누자. 처음 n개 중에서는 k개를 뽑고, 나머지 n개 중에서는 k개를 제외하면 총합 n개를 뽑게 된다. 이 경우의 수는 곱의 법칙에 의해 [math]\displaystyle{ \binom{n}{k}^2 }[/math]이고, 가능한 k는 0부터 n까지이므로 합의 법칙에 의해 다 더한 것이 된다.

참고로 이 식을 일반화 하면 [math]\displaystyle{ \sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r} }[/math]이 되고, 증명 방법은 동일하다 (방데르몽드 항등식이라 부른다).

경우의 수를 구하는데 같이 쓰이는 도구

• 순열
• 조합
• 구성
• 스털링 수
• 벨 수
• 분할 수
• 포함과 배제의 원리
• 생성함수