세는 법: 곱의 법칙에서 조합 C(n,k)와 이항정리까지

지난 글까지 두 편은 표본공간을 손으로 다 적을 수 있는 것만 다뤘습니다. 주사위 두 개는 서른여섯 칸이었고 동전 세 번은 여덟 갈래였습니다.

로또는 어떨까요. 45개의 공에서 6개를 고르는 방법을 하나하나 적으려면 평생이 모자랍니다. 그래도 1등이 될 확률은 구할 수 있어야 합니다. 확률은 "관심 있는 경우의 수 ÷ 전체 경우의 수"였으니, 적지 않고 세기만 할 수 있으면 됩니다.

적지 않고 세는 도구를 만드는 것이 이 글의 일입니다. 도구는 두 법칙에서 시작해 순열·조합·파스칼 삼각형·이항정리로 차례로 쌓이고, 마지막에 로또와 생일 문제를 손으로 셉니다.

합의 법칙과 곱의 법칙

두 기본 법칙

세는 일은 결국 두 법칙으로 갈립니다.

첫째, 겹치지 않는 두 방법 중 하나를 고르는 것이면 더합니다. 학교에 가는 길이 버스 3개 노선과 지하철 2개 노선이라면 $3+2=5$ 가지입니다. 이것을 합의 법칙이라고 합니다. 조건은 "겹치지 않는다"입니다. 버스이면서 지하철인 노선은 없으니 그냥 더해도 두 번 세는 것이 없습니다.

둘째, 두 가지를 잇달아 고르는 것이면 곱합니다. 셔츠 3장과 바지 4벌이 있으면 차림은 $3\times4=12$ 가지입니다. 이것을 곱의 법칙이라고 합니다. 셔츠를 하나 고를 때마다 바지 네 갈래가 새로 붙으므로, 네 개짜리 묶음이 셔츠 수만큼 세 번 생깁니다.

"또는"이면 더하고 "그리고"이면 곱한다고 외워 두면 웬만한 경우에 맞습니다.

지난 글들에서 이미 쓰고 있었습니다. 주사위 두 개의 표가 여섯 줄 여섯 칸이었던 것이 바로 곱의 법칙입니다 — 첫 주사위 6가지 각각에 둘째 주사위 6가지가 붙어 36칸입니다. 나무그림도 마찬가지여서, 동전을 던질 때마다 갈래가 2배씩 늘어 세 번이면 $2\times2\times2=8$ 이었습니다.

중복순열

같은 후보 중에서 여러 번 되풀이해 고르면 곱의 법칙이 거듭제곱이 됩니다. 숫자 네 자리로 만드는 비밀번호는 자리마다 0부터 9까지 10가지씩이고, 앞자리에 쓴 숫자를 뒷자리에 또 써도 됩니다.

$10\times10\times10\times10 = 10^4 = 10{,}000$

이처럼 $n$ 가지 후보에서 같은 것을 다시 골라도 되게 하면서 $r$ 자리를 차례로 채우는 방법을 중복순열이라고 하고, 그 수는 $n^r$ 입니다. 밑 $n$ 이 "자리마다 후보가 몇 개인가", 지수 $r$ 이 "자리가 몇 개인가"입니다. 둘을 헷갈리기 쉬우니 비밀번호로 확인합니다. 후보가 10개, 자리가 4개라서 $10^4$ 이지 $4^{10}$ 이 아닙니다.

동전을 세 번 던지는 것도 중복순열입니다. 후보는 앞·뒤 2개, 자리는 세 번이라 $2^3=8$ 입니다.

두 집합의 포함배제

합의 법칙에는 "겹치지 않으면"이라는 조건이 붙어 있었습니다. 겹치면 어떻게 될까요. 겹친 부분을 두 번 세게 됩니다. 지난 글들에서 확률로 본 그 관계가 개수 판으로도 그대로 성립합니다.

$\lvert A\cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A\cap B\rvert$

$\lvert A\rvert$ 는 집합 $A$ 에 든 원소의 개수입니다. 겹친 $A\cap B$ 는 $\lvert A\rvert$ 에서 한 번, $\lvert B\rvert$ 에서 한 번 세였으니 한 번을 빼서 바로잡습니다. 이렇게 더했다가 겹친 만큼 빼는 방식을 포함배제 원리라고 합니다. 합의 법칙은 겹친 것이 없어 뺄 것이 0인 특별한 경우입니다.

1부터 100까지의 수 중 3의 배수이거나 5의 배수인 것을 세어 봅니다. 100 이하의 3의 배수 개수는 100을 3으로 나눈 몫입니다.

• 3의 배수: $100 \div 3 = 33.3\ldots$ 이므로 33개
• 5의 배수: $100 \div 5 = 20$ 이므로 20개
• 둘 다인 것은 15의 배수: $100 \div 15 = 6.6\ldots$ 이므로 6개

$33 + 20 - 6 = 47$

47개입니다. 15, 30, 45, 60, 75, 90 여섯 개가 3의 배수에서도 5의 배수에서도 한 번씩 세였던 것을 한 번 뺀 것입니다.

세 집합의 포함배제

집합이 셋이면 한 번 더 바로잡아야 합니다. 1부터 100까지의 수 중 2·3·5 가운데 하나라도 그 배수인 것을 세어 봅니다.

먼저 셋을 각각 셉니다. 2의 배수 50개, 3의 배수 33개, 5의 배수 20개이고 더하면 $50+33+20=103$ 입니다. 100개 중에서 103개가 나왔으니 두 번 센 것이 있다는 것이 바로 보입니다.

둘씩 겹친 것을 셉니다. 2와 3의 배수는 6의 배수라 $100\div6=16.6\ldots$ 에서 16개, 2와 5는 10의 배수라 10개, 3과 5는 15의 배수라 6개입니다. 합이 $16+10+6=32$ 이고, 이것을 빼면 $103-32=71$ 입니다.

그런데 셋 다의 배수, 곧 30의 배수 30·60·90은 어떻게 되었을까요. 처음에 세 번 더해졌고, 둘씩 겹친 것 세 묶음에 모두 들어 있어 세 번 빠졌습니다. 더한 것도 셋, 뺀 것도 셋이라 지금 한 번도 안 세인 상태입니다. 그래서 $100\div30=3.3\ldots$ 의 3개를 다시 더합니다.

$50+33+20-16-10-6+3=74$

부호 규칙은 이렇게 적을 수 있습니다. 하나씩은 더하고, 둘씩 겹친 것은 빼고, 셋이 겹친 것은 다시 더합니다. 그림의 일곱 칸을 모두 더하면 $27+14+7+13+7+3+3=74$ 로 같은 답이 나옵니다. 검산을 하나 더 하면, 2·3·5 어느 것으로도 나누어떨어지지 않는 수가 1, 7, 11, 13, … 해서 26개이고 $100-26=74$ 입니다.

팩토리얼과 순열

팩토리얼

서로 다른 $n$ 개를 한 줄로 늘어놓는 방법은 몇 가지일까요. 첫 자리에 $n$ 가지, 그다음 자리에는 하나를 이미 썼으니 $n-1$ 가지, 그다음은 $n-2$ 가지입니다. 곱의 법칙으로 전부 곱합니다.

$n \times (n-1) \times \cdots \times 2 \times 1 = n!$

1부터 $n$ 까지를 모두 곱한 이 수를 $n$ 팩토리얼이라 읽고 $n!$ 로 적습니다. $3!=6$, $4!=24$, $5!=120$, $6!=720$ 이고, 하나 늘 때마다 그 수를 곱하므로 금세 커집니다. 약속으로 $0!=1$ 로 둡니다 — 아무것도 없는 것을 늘어놓는 방법은 "안 늘어놓는다" 하나뿐이기 때문입니다.

35번 글에서 $n!$ 을 계수의 분모로 만났습니다. 거기서는 미분을 되돌리는 수였고 여기서는 줄 세우는 방법의 수입니다 — 같은 수가 두 자리에서 다른 뜻으로 쓰입니다.

순열

$n$ 개 중에서 $k$ 개만 뽑아 줄을 세우는 방법을 순열이라 하고 $P(n,k)$ 로 적습니다. 자리가 $k$ 개뿐이니 곱을 $k$ 개에서 멈춥니다.

$P(n,k) = \underbrace{n\times(n-1)\times\cdots}_{k\text{개}}= \frac{n!}{(n-k)!}$

5명 중 2명을 뽑아 회장과 부회장을 정하는 방법이라면 회장 자리에 5명, 부회장 자리에 남은 4명입니다.

$P(5,2) = 5\times4 = 20$

분수 꼴이 왜 같은지도 확인해 둡니다. $\dfrac{5!}{3!} = \dfrac{120}{6} = 20$ 입니다 — 분자 $5\times4\times3\times2\times1$ 의 뒤쪽 $3\times2\times1$ 이 분모와 통째로 지워지기 때문입니다. 중복순열과 다른 점은 한 번 쓴 사람을 다시 못 쓴다는 것 하나이고, 그래서 곱하는 수가 하나씩 줄어듭니다.

같은 것이 있는 순열

늘어놓을 것 가운데 서로 구별이 안 되는 것이 섞여 있으면 어떻게 될까요. A, A, B 세 글자를 늘어놓아 봅니다. 두 A를 잠시 $A_1$, $A_2$ 로 구별하면 $3!=6$ 가지입니다.

• $A_1A_2B$ 와 $A_2A_1B$ 는 둘 다 AAB
• $A_1BA_2$ 와 $A_2BA_1$ 은 둘 다 ABA
• $BA_1A_2$ 와 $BA_2A_1$ 은 둘 다 BAA

이름표를 떼면 두 개씩 같은 줄이 됩니다. 두 A끼리 자리를 바꾸는 $2!=2$ 가지가 한 묶음이라 $6\div2=3$ 가지입니다.

이것을 같은 것이 있는 순열이라고 합니다. $n$ 개 중에 같은 것이 $p$ 개, 또 다른 같은 것이 $q$ 개 있으면

$\frac{n!}{p!\,q!}$

입니다. 같은 것끼리 자리를 바꾸는 $p!$ 가지와 $q!$ 가지가 전부 한 줄로 뭉치니 그만큼 나눕니다. BANANA 여섯 글자라면 A가 3개, N이 2개, B가 1개라서

$\frac{6!}{3!\times2!\times1!} = \frac{720}{6\times2\times1} = \frac{720}{12} = 60$

가지입니다.

원순열

이번에는 둥근 탁자에 둘러앉는 경우입니다. A, B, C, D 넷을 한 줄로 세우면 $4!=24$ 가지인데, 둥글게 앉으면 ABCD와 BCDA와 CDAB와 DABC가 모두 같은 자리 배치입니다. 탁자를 돌리기만 하면 서로 겹치기 때문입니다. 누구 오른쪽에 누가 앉았는지는 네 경우가 전부 같습니다.

돌려서 같아지는 4가지가 한 묶음이므로 $24\div4=6$ 가지입니다. 이렇게 원 둘레에 늘어놓는 방법을 원순열이라 하고, 서로 다른 $n$ 개라면

$\frac{n!}{n} = (n-1)!$

가지입니다. 다른 방법으로 보면, 한 사람을 먼저 앉혀 기준으로 삼고 나머지 $n-1$ 명을 그 사람 오른쪽부터 차례로 늘어놓는 것과 같습니다. 넷이면 $3!=6$ 으로 같은 답입니다.

여기까지 나온 세 가지 나눗셈은 모두 같은 생각입니다. 먼저 전부 구별해서 세고, 같은 것으로 쳐야 하는 경우가 몇 개씩 한 묶음인지 보고, 그 수로 나눕니다.

조합

순서 없는 선택

회장과 부회장이 아니라 그냥 대표 2명을 뽑는다면 어떨까요. A와 B를 뽑는 것과 B와 A를 뽑는 것이 같은 결과입니다.

그림에서 보듯 뽑은 $k$ 개를 줄 세우는 방법 $k!$ 가지가 전부 한 묶음이 됩니다. 그러니 순열을 $k!$ 로 나누면 됩니다. 방금 본 "묶음으로 나누기"와 같은 생각입니다.

$n$ 개 중에서 순서를 따지지 않고 $k$ 개를 고르는 방법의 수를 조합이라 하고 $C(n,k)$ 로 적습니다.

$C(n,k) = \frac{P(n,k)}{k!} = \frac{n!}{k!\,(n-k)!}$

$C(5,2) = \dfrac{20}{2} = 10$ 입니다. 실제로 5명에서 2명을 고르는 방법은 10가지입니다.

분모에 $k!$ 과 $(n-k)!$ 이 나란히 있는 모양에서 성질 하나가 곧바로 보입니다. 둘을 맞바꿔도 식이 그대로입니다.

$C(n,k) = C(n,\,n-k)$

$C(5,2)=C(5,3)=10$ 입니다. 말로 하면 당연합니다 — 5명 중 뽑을 2명을 고르는 것과 남길 3명을 고르는 것은 같은 일이니까요.

격자의 최단경로

가로로 3칸, 세로로 2칸인 바둑판 길이 있습니다. 왼쪽 아래 모퉁이에서 오른쪽 위 모퉁이까지 되돌아가지 않고 가는 길, 곧 최단경로는 몇 가지일까요. 되돌아가지 않으니 오른쪽으로 한 칸(→)이나 위로 한 칸(↑)만 움직일 수 있고, 어느 길이든 → 세 번과 ↑ 두 번을 합쳐 다섯 걸음입니다.

길 하나는 다섯 걸음의 순서 하나입니다. →→↑→↑ 처럼요. 그러니 길의 수는 → 3개와 ↑ 2개를 한 줄로 늘어놓는 방법의 수이고, 이것은 같은 것이 있는 순열입니다.

$\frac{5!}{3!\times2!} = \frac{120}{6\times2} = 10$

이 10은 앞에서 본 $C(5,2)=10$ 과 같은 수입니다. 우연이 아닙니다. 다섯 걸음 자리 가운데 어느 두 자리를 ↑로 할지 고르면 나머지 세 자리는 저절로 →가 됩니다. 길 하나가 "다섯 자리 중 ↑ 자리 두 개 고르기" 하나와 짝지어지므로 개수가 같습니다.

두 식의 일치

일반적으로 적어 봅니다. ○를 $k$ 개, ×를 $n-k$ 개 한 줄로 늘어놓는 방법은 같은 것이 있는 순열로

$\frac{n!}{k!\,(n-k)!}$

이고, 이것은 조합의 식과 글자 하나까지 같습니다. $n$ 자리 가운데 ○가 들어갈 $k$ 자리를 고르는 일이 곧 $n$ 개 중 $k$ 개를 고르는 일이기 때문입니다.

앞으로 조합이 나오면 둘 중 편한 쪽으로 생각하면 됩니다. "사람 다섯 중 둘 고르기"로 봐도 되고 "○○××× 늘어놓기"로 봐도 됩니다. 뒤에서 이항정리를 볼 때 두 번째 눈이 쓸모가 있습니다.

큰 수의 계산

$C(20,5)$ 를 식대로 $\dfrac{20!}{5!\,15!}$ 로 계산하려고 $20!$ 부터 곱하면 19자리 수가 나옵니다. 그럴 필요가 없습니다. 분자에서 $15!$ 은 분모와 지워지므로 분자는 20부터 5개만 곱하면 됩니다.

$C(20,5) = \frac{20\times19\times18\times17\times16}{5\times4\times3\times2\times1}$

이것도 분자를 다 곱한 뒤 나누면 수가 커집니다. 요령은 분자를 하나 곱할 때마다 분모도 하나씩 나누는 것입니다. 분모는 1, 2, 3, 4, 5의 차례로 씁니다.

• $20 \div 1 = 20$
• $20\times19 \div 2 = 380\div2 = 190$
• $190\times18\div3 = 3420\div3 = 1140$
• $1140\times17\div4 = 19380\div4 = 4845$
• $4845\times16\div5 = 77520\div5 = 15504$

$C(20,5)=15{,}504$ 입니다. 중간값 20, 190, 1140, 4845는 차례로 $C(20,1)$, $C(20,2)$, $C(20,3)$, $C(20,4)$ 이고, 조합의 값은 언제나 정수이므로 나눗셈이 매번 딱 떨어집니다. 나머지가 생기면 곱셈을 잘못한 것이니 그 자리에서 검산이 됩니다.

파스칼 삼각형과 이항정리

파스칼 항등식

조합에는 팩토리얼을 계산하지 않고도 값을 얻는 길이 있습니다.

$n$ 명 중 $k$ 명을 고를 때 특정한 한 사람을 기준으로 두 갈래로 가릅니다. 그 사람을 뽑는다면 나머지 $n-1$ 명 중 $k-1$ 명을 더 고르면 되고, 뽑지 않는다면 나머지 $n-1$ 명 중 $k$ 명을 골라야 합니다. 두 경우는 겹치지 않으므로 합의 법칙으로 더합니다.

$C(n,k) = C(n-1,\,k-1) + C(n-1,\,k)$

이것을 파스칼 항등식이라고 합니다. 이 규칙대로 조합의 값을 줄줄이 늘어놓은 것이 파스칼 삼각형입니다. 맨 위 꼭대기 줄을 $n=0$ 줄로 부르고, 한 줄의 왼쪽 끝부터 $C(n,0)$, $C(n,1)$, … 순서로 적습니다.

손으로 채우는 방법은 하나뿐입니다. 양 끝에 1을 적고, 안쪽은 바로 위의 두 수를 더합니다. 여덟 줄까지 채우면 $n=7$ 까지의 모든 조합값이 나옵니다.

$n$	그 줄의 수들
0	1
1	1 1
2	1 2 1
3	1 3 3 1
4	1 4 6 4 1
5	1 5 10 10 5 1
6	1 6 15 20 15 6 1
7	1 7 21 35 35 21 7 1

$n=5$ 줄의 셋째 수가 $C(5,2)=10$ 이고, 그 위 줄의 $4$ 와 $6$ 을 더한 값입니다. 줄마다 왼쪽과 오른쪽이 거울처럼 같은 것은 앞에서 본 $C(n,k)=C(n,n-k)$ 가 모양으로 드러난 것입니다.

이항정리

$(a+b)^5$ 를 전개하면 계수가 무엇이 될까요. 곱셈을 다 하지 않고도 알 수 있습니다.

$(a+b)^5 = (a+b)(a+b)(a+b)(a+b)(a+b)$

괄호 다섯 개에서 각각 $a$ 나 $b$ 를 하나씩 골라 곱한 것들을 모두 더한 것이 전개입니다. $b$ 를 정확히 2개 고르면 $a^3b^2$ 이 되는데, 다섯 괄호 중 어느 둘에서 $b$ 를 고르느냐가 $C(5,2)=10$ 가지입니다. 괄호 다섯 자리에 $b$ 둘과 $a$ 셋을 늘어놓는 것이니 ○× 늘어놓기와 같은 셈입니다. 그래서 $a^3b^2$ 의 계수가 10입니다.

$(a+b)^n = \sum_{k=0}^{n} C(n,k)\,a^{n-k}b^{k}$

이것을 이항정리라고 합니다. 항이 둘인 식의 거듭제곱을 푸는 정리라 붙은 이름이고, 그 계수로 쓰이는 $C(n,k)$ 를 이항계수라고도 부릅니다. 27번 글의 $\Sigma$ 로 적었을 뿐 하는 말은 "파스칼 삼각형의 $n$ 번째 줄이 곧 계수"라는 것입니다.

$a=1$, $b=x$ 로 두고 $n=5$ 줄을 그대로 옮겨 적어 봅니다.

$(1+x)^5 = 1 + 5x + 10x^2 + 10x^3 + 5x^4 + x^5$

손으로 곱해서 맞춰 보면 정말 이렇게 됩니다. 15번 글에서 $(a+b)^2=a^2+2ab+b^2$ 을 전개했던 것이 $n=2$ 줄의 $1\ 2\ 1$ 이었습니다.

한 줄의 합

파스칼 삼각형의 각 줄을 모두 더해 봅니다. $n=3$ 줄은 $1+3+3+1=8$, $n=4$ 줄은 $1+4+6+4+1=16$, $n=5$ 줄은 $1+5+10+10+5+1=32$ 입니다. 줄이 하나 내려갈 때마다 합이 두 배가 되어 $n$ 번째 줄의 합은 $2^n$ 입니다.

이항정리에 $a=1$, $b=1$ 을 넣으면 곧바로 나옵니다. $1$ 은 몇 번 곱해도 1이라 계수만 남습니다.

$(1+1)^n = C(n,0)+C(n,1)+\cdots+C(n,n) = 2^n$

세는 쪽에서 보면 더 또렷합니다. 원소가 셋인 집합 $\{A,B,C\}$ 의 부분집합을 원소 개수별로 모으면 0개짜리 1개, 1개짜리 3개, 2개짜리 3개, 3개짜리 1개입니다. 이 네 수가 바로 $n=3$ 줄이고, 부분집합 전체는 8개입니다. 한편 부분집합 하나를 만드는 일은 원소마다 "넣는다·뺀다"를 정하는 일이라 곱의 법칙으로 $2\times2\times2=8$ 입니다. 같은 것을 두 방법으로 세었으니 두 답이 같아야 합니다.

이번에는 $a=1$, $b=-1$ 을 넣어 봅니다. $(-1)^k$ 은 $k$ 가 짝수면 1, 홀수면 $-1$ 이라 부호가 번갈아 붙습니다.

$(1-1)^n = C(n,0)-C(n,1)+C(n,2)-\cdots = 0$

$n=4$ 줄로 확인하면 $1-4+6-4+1=0$ 이고 $n=5$ 줄은 $1-5+10-10+5-1=0$ 입니다. 짝수 번째 자리의 합과 홀수 번째 자리의 합이 똑같다는 뜻이고, $n=4$ 라면 $1+6+1=8$ 과 $4+4=8$ 로 둘 다 한 줄 합 16의 절반입니다.

한 줄의 모양

한 줄 안의 수를 왼쪽부터 읽으면 가운데로 갈수록 커졌다가 다시 줄어듭니다. $n=10$ 줄을 적어 봅니다.

$1\quad10\quad45\quad120\quad210\quad252\quad210\quad120\quad45\quad10\quad1$

이웃한 두 수의 비를 보면 왜 그런지 보입니다. 식을 나눠 정리하면 $\dfrac{C(n,k+1)}{C(n,k)} = \dfrac{n-k}{k+1}$ 이 되는데, $n=10$ 에서 $k=0$ 부터 차례로 넣으면 이렇습니다.

• $k=0$: $\dfrac{10}{1}=10$ 이라 1에서 10으로 열 배
• $k=1$: $\dfrac{9}{2}=4.5$ 라 10에서 45로
• $k=2$: $\dfrac{8}{3}\approx2.67$ 이라 45에서 120으로
• $k=3$: $\dfrac{7}{4}=1.75$ 라 120에서 210으로
• $k=4$: $\dfrac{6}{5}=1.2$ 라 210에서 252로
• $k=5$: $\dfrac{5}{6}\approx0.83$ 이라 252에서 210으로, 여기서부터 줄어듦

분자 $n-k$ 는 줄고 분모 $k+1$ 은 느니 비가 점점 작아지다가 1 밑으로 내려가는 자리에서 꼭대기를 지납니다. 끝 쪽에서는 비가 커서 급히 변하고 가운데에서는 1에 가까워 완만합니다. 그래서 값이 가운데에 몰립니다. 한 줄의 합이 $2^{10}=1024$ 인데 가운데 세 수 $210+252+210=672$ 가 그 가운데 약 65.6%를 차지합니다. 동전을 열 번 던져 앞면이 4·5·6번 나오는 경우가 흔하고 0번이나 10번은 드문 것이 이 모양 때문입니다.

세 가지 손계산

로또 1등

45개 중 6개를 순서 없이 고릅니다.

$C(45,6) = \frac{45\times44\times43\times42\times41\times40}{6\times5\times4\times3\times2\times1}$

앞에서 본 요령대로 분자를 하나 곱할 때마다 분모를 하나씩 나눕니다.

• $45\div1=45$
• $45\times44\div2=1980\div2=990$
• $990\times43\div3=42570\div3=14190$
• $14190\times42\div4=595980\div4=148995$
• $148995\times41\div5=6108795\div5=1221759$
• $1221759\times40\div6=48870360\div6=8145060$

분자를 다 곱한 $5{,}864{,}443{,}200$ 을 $6!=720$ 으로 한 번에 나눠도 같은 $8{,}145{,}060$ 이 나옵니다. 1등이 될 확률은 815만분의 1쯤입니다.

그럼 한 주에 서로 다른 번호로 두 장을 사면 확률이 두 배가 될까요. 두 장이 모두 1등인 일은 없습니다 — 당첨 번호 조합은 하나이고 두 장의 조합은 다르니까요. 두 사건이 배반이라 합의 법칙 그대로 더하면 되고, 정확히 $\dfrac{2}{8{,}145{,}060}$ 입니다. 두 배가 맞습니다. 같은 번호를 두 장 사면 사건이 완전히 겹쳐 확률은 그대로이고, 포함배제로 말하면 한 장의 확률을 $p$ 라 할 때 $p+p-p=p$ 입니다.

생일 문제

서른 명이 모인 방에서 생일이 같은 사람이 있을 확률은 얼마일까요. 날이 365일이나 되니 낮을 것 같습니다. 2월 29일은 빼고 모든 날이 똑같이 흔하다고 둡니다.

곧이곧대로 세면 어렵습니다 — 두 명이 겹칠 수도, 세 명이 겹칠 수도, 두 쌍이 따로 겹칠 수도 있으니까요. 여사건을 셉니다. 반대는 "서른 명의 생일이 모두 다르다"입니다.

첫 사람은 365일 중 아무 날이나 됩니다. 둘째 사람은 첫 사람과 달라야 하니 364일, 셋째는 363일입니다. 사람이 늘 때마다 쓸 수 있는 날이 하루씩 줄어듭니다. 서른째 사람은 $365-29=336$ 일 중에서 골라야 합니다. 분자는 순열 $P(365,30)$ 이고 분모는 중복순열 $365^{30}$ 입니다.

$P(\text{모두 다름}) = \frac{365}{365}\times\frac{364}{365}\times\cdots\times\frac{336}{365}$

곱하면 $0.2937$ 입니다.

$P(\text{겹침}) = 1 - 0.2937 = 0.7063$

70%가 넘습니다. 감으로 짐작한 것과 크게 다릅니다. 곡선을 보면 23명에서 이미 절반을 넘습니다.

짝의 수 어림

왜 이렇게 높을까요. 감이 틀리는 까닭은 사람 수를 떠올리기 때문입니다. 생일은 두 사람 사이에서 겹치므로, 셀 것은 사람이 아니라 짝입니다. 서른 명에서 두 명을 고르는 짝은

$C(30,2) = \frac{30\times29}{2} = 435$

쌍이나 됩니다. 한 쌍의 생일이 같을 확률은 $\dfrac{1}{365}$ 입니다. 둘째 사람의 생일이 첫째 사람의 생일과 같은 하루에 떨어져야 하기 때문입니다.

지난 글의 기댓값으로 보면, 겹치는 쌍의 수의 기댓값은 쌍마다 $\dfrac{1}{365}$ 씩 435번 더한 것입니다.

$435\times\frac{1}{365} = \frac{435}{365} \approx 1.19$

평균적으로 1.19쌍이 겹친다는 뜻입니다. 평균이 한 쌍을 넘는데 "한 쌍도 없을" 확률이 높을 수는 없습니다.

어림을 확률까지 끌고 가 봅니다. 쌍마다 "안 겹칠" 확률이 $\dfrac{364}{365}$ 이고, 쌍끼리 서로 독립이라고 치고 435번 곱하면 계산기로 $\left(\dfrac{364}{365}\right)^{435}\approx0.303$ 입니다. 그러면 겹칠 확률은 $1-0.303=0.697$ 입니다. 정확한 값 0.7063과 0.01쯤 차이 납니다. 차이가 나는 것은 쌍끼리 완전히 독립이 아니어서입니다 — A와 B가 같고 B와 C가 같으면 A와 C도 반드시 같습니다. 그래도 사람 수가 아니라 짝의 수가 확률을 끌어올린다는 설명으로는 충분히 가깝습니다.

반복 시행

주사위를 다섯 번 던져 6이 정확히 두 번 나올 확률을 구합니다.

어느 두 번에 나오느냐가 $C(5,2)=10$ 가지입니다. 다섯 번 가운데 6이 나올 두 자리를 고르는 것이니 ○× 늘어놓기와 같습니다. 각각의 경우에 6이 두 번·6이 아닌 것이 세 번이므로 확률이 $\left(\dfrac16\right)^2\left(\dfrac56\right)^3$ 입니다.

$C(5,2)\left(\frac16\right)^2\left(\frac56\right)^3 = 10 \times \frac{1}{36}\times\frac{125}{216} = \frac{1250}{7776} \approx 0.161$

일반적으로 적으면 이렇습니다. 한 번에 성공할 확률이 $p$ 인 일을 $n$ 번 되풀이할 때입니다.

$P(k\text{번 성공}) = C(n,k)\,p^{k}(1-p)^{n-k}$

검산은 전부 더해 보는 것입니다. 분모를 $6^5=7776$ 으로 통일해 $k=0$ 부터 적습니다. 분자는 $C(5,k)\times1^k\times5^{5-k}$ 입니다.

$k$	0	1	2	3	4	5
분자	3125	3125	1250	250	25	1

$3125+3125+1250+250+25+1 = 7776$

분모와 정확히 같습니다. 합이 1이니 빠뜨린 경우가 없습니다. 사실 이 합은 이항정리에 $a=5$, $b=1$ 을 넣은 $(5+1)^5=6^5$ 이라 같을 수밖에 없습니다. 이 식에 이름을 붙이고 기댓값·분산까지 다루는 것은 중급 20번 · 이항분포와 정규 근사의 몫이고, 여기서는 계산까지입니다.

연습 문제

연습 1 — 곱의 법칙과 순열

1. 티셔츠 5장, 바지 3벌, 모자 2개로 만들 수 있는 차림의 수

   셋을 잇달아 고르므로 곱합니다. $5\times3\times2=30$ 가지입니다.
2. 6명 중 회장과 부회장을 뽑는 방법의 수

   자리가 다르므로 순열입니다. $P(6,2)=6\times5=30$ 가지입니다.
3. A, B, C, D 네 글자를 한 줄로 늘어놓는 방법의 수

   $4! = 4\times3\times2\times1 = 24$ 가지입니다.
4. LEVEL 다섯 글자를 한 줄로 늘어놓는 방법의 수

   L이 2개, E가 2개, V가 1개입니다. $\dfrac{5!}{2!\times2!} = \dfrac{120}{4} = 30$ 가지입니다.
5. 숫자 1, 1, 2, 2, 2를 모두 써서 만드는 다섯 자리 수의 개수

   1이 2개, 2가 3개입니다. $\dfrac{5!}{2!\times3!} = \dfrac{120}{12} = 10$ 개입니다.
6. COFFEE 여섯 글자를 한 줄로 늘어놓는 방법의 수

   F가 2개, E가 2개, C와 O는 1개씩입니다. $\dfrac{6!}{2!\times2!} = \dfrac{720}{4} = 180$ 가지입니다.
7. 6명이 둥근 탁자에 둘러앉는 방법의 수

   돌려서 같아지는 6가지가 한 묶음이므로 $\dfrac{6!}{6} = 5! = 120$ 가지입니다.

연습 2 — 조합과 파스칼

1. $C(7,3)$

   $\dfrac{7\times6\times5}{3\times2\times1}=\dfrac{210}{6}=35$ 입니다. 파스칼 삼각형 표의 $n=7$ 줄 넷째 수와 같습니다.
2. $C(10,8)$

   $C(10,8)=C(10,2)=\dfrac{10\times9}{2}=45$ 입니다. 남길 2개를 고르는 편이 훨씬 짧습니다.
3. $C(6,2)$ 를 파스칼 항등식으로 쪼개 확인하기

   $C(6,2)=C(5,1)+C(5,2)=5+10=15$ 입니다. 직접 계산해도 $\dfrac{6\times5}{2}=15$ 입니다.
4. 가로 5칸, 세로 3칸인 바둑판 길에서 왼쪽 아래 모퉁이부터 오른쪽 위 모퉁이까지 가는 최단경로의 수

   → 5개와 ↑ 3개를 늘어놓는 방법입니다. $\dfrac{8!}{5!\times3!} = C(8,3) = \dfrac{8\times7\times6}{3\times2\times1} = \dfrac{336}{6} = 56$ 가지입니다.
5. 가로 3칸, 세로 3칸인 바둑판 길에서 왼쪽 아래 모퉁이 $(0,0)$ 부터 오른쪽 위 모퉁이 $(3,3)$ 까지 가되, 반드시 교차점 $(1,1)$ 을 지나는 최단경로의 수

   둘로 끊어 곱의 법칙을 씁니다. $(0,0)$ 에서 $(1,1)$ 까지는 → 1개와 ↑ 1개라 $C(2,1)=2$ 가지, $(1,1)$ 에서 $(3,3)$ 까지는 → 2개와 ↑ 2개라 $C(4,2)=6$ 가지입니다. $2\times6=12$ 가지입니다.

연습 3 — 이항정리와 확률

1. $(1+x)^6$ 의 전개

   파스칼 $n=6$ 줄이 $1\ 6\ 15\ 20\ 15\ 6\ 1$ 이므로 $1+6x+15x^2+20x^3+15x^4+6x^5+x^6$ 입니다.
2. 동전을 6번 던져 앞면이 정확히 4번 나올 확률

   전체는 $2^6=64$ 가지이고 앞면 4번인 경우는 $C(6,4)=15$ 가지이므로 $\dfrac{15}{64}\approx0.234$ 입니다.
3. 파스칼 삼각형 $n=8$ 줄의 수를 모두 더한 값

   $2^8=256$ 입니다. 줄을 직접 적어도 $1+8+28+56+70+56+28+8+1=256$ 입니다.
4. 피자 토핑 6가지 중 원하는 만큼 골라 올리는 방법의 수, 그리고 적어도 하나는 올리는 방법의 수

   토핑마다 올린다·안 올린다 두 갈래라 $2^6=64$ 가지입니다. 하나도 안 올리는 1가지를 빼면 $64-1=63$ 가지입니다.

연습 4 — 포함배제

1. 1부터 60까지의 수 중 4의 배수이거나 6의 배수인 것의 개수

   4의 배수 15개, 6의 배수 10개, 둘 다인 12의 배수 5개입니다. $15+10-5=20$ 개입니다.
2. 1부터 60까지의 수 중 2, 3, 5 가운데 적어도 하나의 배수인 것의 개수

   하나씩은 $30+20+12=62$, 둘씩 겹친 6·10·15의 배수는 $10+6+4=20$, 셋 다인 30의 배수는 2개입니다. $62-20+2=44$ 개입니다.
3. 40명인 반에서 수학을 좋아하는 학생 22명, 영어 18명, 과학 15명이고, 수학·영어를 둘 다 좋아하는 학생 8명, 수학·과학 6명, 영어·과학 5명, 셋 다 3명입니다. 셋 중 어느 것도 좋아하지 않는 학생 수

   하나라도 좋아하는 학생은 $22+18+15-8-6-5+3=39$ 명입니다. $40-39=1$ 명입니다.

정리

• "또는"이면 더하고(합의 법칙) "그리고"이면 곱합니다(곱의 법칙). 같은 후보를 되풀이해 고르는 중복순열은 $n^r$ 입니다.
• 겹치면 포함배제로 바로잡습니다. 둘이면 겹친 것을 한 번 빼고, 셋이면 하나씩 더하고 둘씩 빼고 셋을 다시 더합니다. 1부터 100까지 2·3·5 가운데 하나의 배수는 74개입니다.
• $n!$ 은 $n$ 개를 줄 세우는 방법의 수이고, $k$ 개만 뽑아 세우는 것이 순열 $P(n,k)=\dfrac{n!}{(n-k)!}$ 입니다.
• 같은 것이 있는 순열 $\dfrac{n!}{p!\,q!}$, 원순열 $(n-1)!$, 조합 $C(n,k)=\dfrac{n!}{k!\,(n-k)!}$ 은 모두 "구별해 세고, 같은 것으로 칠 묶음의 크기로 나눈다"입니다. 격자 최단경로 10가지가 $C(5,2)$ 와 같은 것도 그 때문입니다.
• 파스칼 항등식 $C(n,k)=C(n-1,k-1)+C(n-1,k)$ 을 줄줄이 늘어놓은 것이 파스칼 삼각형이고, $n$ 번째 줄이 그대로 $(a+b)^n$ 의 계수입니다(이항정리).
• 한 줄의 합은 $2^n$ 으로 부분집합의 개수이고, 부호를 번갈아 더하면 0입니다. 한 줄의 값은 가운데에 몰립니다.
• 로또 1등은 $C(45,6)=8{,}145{,}060$ 분의 1, 서른 명의 생일이 겹칠 확률은 여사건으로 세어 70.6%이고 435쌍이 그 까닭입니다. 반복 시행에서 $k$ 번 성공할 확률은 $C(n,k)p^{k}(1-p)^{n-k}$ 이고, 전부 더하면 정확히 1이 됩니다.

여기까지가 아직 일어나지 않은 일을 세는 도구였습니다. 다음 글은 이미 손에 든 숫자 뭉치를 요약하는 쪽으로 갑니다.

---

읽어주셔서 감사합니다. 😊