수학

MATH / 초급 39번

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

표본공간을 손으로 다 적을 수 없을 때 쓰는 도구를 만듭니다. 곱의 법칙에서 순열과 조합을 세우고, 파스칼 삼각형과 이항정리를 손으로 채운 뒤 로또와 생일 문제를 계산합니다.

PALDYN Team39 MIN READ

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

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

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

합의 법칙과 곱의 법칙

두 기본 법칙

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

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

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

셔츠 세 갈래 각각이 바지 네 갈래로 다시 갈리는 나무그림

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

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

중복순열

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

10×10×10×10=104=10,00010\times10\times10\times10 = 10^4 = 10{,}000

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

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

두 집합의 포함배제

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

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣\lvert A\cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A\cap B\rvert

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

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

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

33+20−6=4733 + 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=10350+33+20=103 입니다. 100개 중에서 103개가 나왔으니 두 번 센 것이 있다는 것이 바로 보입니다.

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

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

50+33+20−16−10−6+3=7450+33+20-16-10-6+3=74

2의 배수·3의 배수·5의 배수 세 원이 겹치고, 일곱 칸마다 개수를 적은 벤 다이어그램

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

팩토리얼과 순열

팩토리얼

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

n×(n−1)×⋯×2×1=n!n \times (n-1) \times \cdots \times 2 \times 1 = n!

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

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

순열

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

P(n,k)=n×(n−1)×⋯⏟k개=n!(n−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×4=20P(5,2) = 5\times4 = 20

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

같은 것이 있는 순열

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

  • A1A2BA_1A_2B 와 A2A1BA_2A_1B 는 둘 다 AAB
  • A1BA2A_1BA_2 와 A2BA1A_2BA_1 은 둘 다 ABA
  • BA1A2BA_1A_2 와 BA2A1BA_2A_1 은 둘 다 BAA

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

이것을 같은 것이 있는 순열이라고 합니다. nn 개 중에 같은 것이 pp 개, 또 다른 같은 것이 qq 개 있으면

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

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

6!3!×2!×1!=7206×2×1=72012=60\frac{6!}{3!\times2!\times1!} = \frac{720}{6\times2\times1} = \frac{720}{12} = 60

가지입니다.

원순열

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

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

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

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

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

조합

순서 없는 선택

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

세 사람 중 둘을 뽑는 순열 여섯 가지가 조합 세 가지로 묶이는 그림

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

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

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

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

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

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

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

격자의 최단경로

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

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

5!3!×2!=1206×2=10\frac{5!}{3!\times2!} = \frac{120}{6\times2} = 10

가로 3칸 세로 2칸 격자에서 왼쪽 아래부터 오른쪽 위까지 가는 최단경로 열 가지

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

두 식의 일치

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

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

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

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

큰 수의 계산

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

C(20,5)=20×19×18×17×165×4×3×2×1C(20,5) = \frac{20\times19\times18\times17\times16}{5\times4\times3\times2\times1}

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

  • 20÷1=2020 \div 1 = 20
  • 20×19÷2=380÷2=19020\times19 \div 2 = 380\div2 = 190
  • 190×18÷3=3420÷3=1140190\times18\div3 = 3420\div3 = 1140
  • 1140×17÷4=19380÷4=48451140\times17\div4 = 19380\div4 = 4845
  • 4845×16÷5=77520÷5=155044845\times16\div5 = 77520\div5 = 15504

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

파스칼 삼각형과 이항정리

파스칼 항등식

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

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

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

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

n이 0부터 7까지의 파스칼 삼각형과, 10이 4와 6의 합임을 표시한 그림

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

nn 그 줄의 수들
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=5n=5 줄의 셋째 수가 C(5,2)=10C(5,2)=10 이고, 그 위 줄의 44 와 66 을 더한 값입니다. 줄마다 왼쪽과 오른쪽이 거울처럼 같은 것은 앞에서 본 C(n,k)=C(n,n−k)C(n,k)=C(n,n-k) 가 모양으로 드러난 것입니다.

이항정리

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

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

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

(a+b)n=∑k=0nC(n,k) an−kbk(a+b)^n = \sum_{k=0}^{n} C(n,k)\,a^{n-k}b^{k}

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

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

(1+x)5=1+5x+10x2+10x3+5x4+x5(1+x)^5 = 1 + 5x + 10x^2 + 10x^3 + 5x^4 + x^5

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

한 줄의 합

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

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

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

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

원소 셋인 집합의 부분집합 여덟 개를 원소 개수 0·1·2·3으로 묶어 1·3·3·1개임을 보인 그림

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

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

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

한 줄의 모양

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

11045120210252210120451011\quad10\quad45\quad120\quad210\quad252\quad210\quad120\quad45\quad10\quad1

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

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

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

세 가지 손계산

로또 1등

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

C(45,6)=45×44×43×42×41×406×5×4×3×2×1C(45,6) = \frac{45\times44\times43\times42\times41\times40}{6\times5\times4\times3\times2\times1}

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

  • 45÷1=4545\div1=45
  • 45×44÷2=1980÷2=99045\times44\div2=1980\div2=990
  • 990×43÷3=42570÷3=14190990\times43\div3=42570\div3=14190
  • 14190×42÷4=595980÷4=14899514190\times42\div4=595980\div4=148995
  • 148995×41÷5=6108795÷5=1221759148995\times41\div5=6108795\div5=1221759
  • 1221759×40÷6=48870360÷6=81450601221759\times40\div6=48870360\div6=8145060

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

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

생일 문제

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

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

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

P(모두 다름)=365365×364365×⋯×336365P(\text{모두 다름}) = \frac{365}{365}\times\frac{364}{365}\times\cdots\times\frac{336}{365}

곱하면 0.29370.2937 입니다.

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

사람 수에 따라 생일이 겹칠 확률이 오르는 곡선

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

짝의 수 어림

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

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

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

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

435×1365=435365≈1.19435\times\frac{1}{365} = \frac{435}{365} \approx 1.19

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

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

반복 시행

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

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

C(5,2)(16)2(56)3=10×136×125216=12507776≈0.161C(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

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

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

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

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

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

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

연습 문제

연습 1 — 곱의 법칙과 순열

  1. 티셔츠 5장, 바지 3벌, 모자 2개로 만들 수 있는 차림의 수
    셋을 잇달아 고르므로 곱합니다. 5×3×2=305\times3\times2=30 가지입니다.
  2. 6명 중 회장과 부회장을 뽑는 방법의 수
    자리가 다르므로 순열입니다. P(6,2)=6×5=30P(6,2)=6\times5=30 가지입니다.
  3. A, B, C, D 네 글자를 한 줄로 늘어놓는 방법의 수
    4!=4×3×2×1=244! = 4\times3\times2\times1 = 24 가지입니다.
  4. LEVEL 다섯 글자를 한 줄로 늘어놓는 방법의 수
    L이 2개, E가 2개, V가 1개입니다. 5!2!×2!=1204=30\dfrac{5!}{2!\times2!} = \dfrac{120}{4} = 30 가지입니다.
  5. 숫자 1, 1, 2, 2, 2를 모두 써서 만드는 다섯 자리 수의 개수
    1이 2개, 2가 3개입니다. 5!2!×3!=12012=10\dfrac{5!}{2!\times3!} = \dfrac{120}{12} = 10 개입니다.
  6. COFFEE 여섯 글자를 한 줄로 늘어놓는 방법의 수
    F가 2개, E가 2개, C와 O는 1개씩입니다. 6!2!×2!=7204=180\dfrac{6!}{2!\times2!} = \dfrac{720}{4} = 180 가지입니다.
  7. 6명이 둥근 탁자에 둘러앉는 방법의 수
    돌려서 같아지는 6가지가 한 묶음이므로 6!6=5!=120\dfrac{6!}{6} = 5! = 120 가지입니다.

연습 2 — 조합과 파스칼

  1. C(7,3)C(7,3)
    7×6×53×2×1=2106=35\dfrac{7\times6\times5}{3\times2\times1}=\dfrac{210}{6}=35 입니다. 파스칼 삼각형 표의 n=7n=7 줄 넷째 수와 같습니다.
  2. C(10,8)C(10,8)
    C(10,8)=C(10,2)=10×92=45C(10,8)=C(10,2)=\dfrac{10\times9}{2}=45 입니다. 남길 2개를 고르는 편이 훨씬 짧습니다.
  3. C(6,2)C(6,2) 를 파스칼 항등식으로 쪼개 확인하기
    C(6,2)=C(5,1)+C(5,2)=5+10=15C(6,2)=C(5,1)+C(5,2)=5+10=15 입니다. 직접 계산해도 6×52=15\dfrac{6\times5}{2}=15 입니다.
  4. 가로 5칸, 세로 3칸인 바둑판 길에서 왼쪽 아래 모퉁이부터 오른쪽 위 모퉁이까지 가는 최단경로의 수
    → 5개와 ↑ 3개를 늘어놓는 방법입니다. 8!5!×3!=C(8,3)=8×7×63×2×1=3366=56\dfrac{8!}{5!\times3!} = C(8,3) = \dfrac{8\times7\times6}{3\times2\times1} = \dfrac{336}{6} = 56 가지입니다.
  5. 가로 3칸, 세로 3칸인 바둑판 길에서 왼쪽 아래 모퉁이 (0,0)(0,0) 부터 오른쪽 위 모퉁이 (3,3)(3,3) 까지 가되, 반드시 교차점 (1,1)(1,1) 을 지나는 최단경로의 수
    둘로 끊어 곱의 법칙을 씁니다. (0,0)(0,0) 에서 (1,1)(1,1) 까지는 → 1개와 ↑ 1개라 C(2,1)=2C(2,1)=2 가지, (1,1)(1,1) 에서 (3,3)(3,3) 까지는 → 2개와 ↑ 2개라 C(4,2)=6C(4,2)=6 가지입니다. 2×6=122\times6=12 가지입니다.

연습 3 — 이항정리와 확률

  1. (1+x)6(1+x)^6 의 전개
    파스칼 n=6n=6 줄이 1 6 15 20 15 6 11\ 6\ 15\ 20\ 15\ 6\ 1 이므로 1+6x+15x2+20x3+15x4+6x5+x61+6x+15x^2+20x^3+15x^4+6x^5+x^6 입니다.
  2. 동전을 6번 던져 앞면이 정확히 4번 나올 확률
    전체는 26=642^6=64 가지이고 앞면 4번인 경우는 C(6,4)=15C(6,4)=15 가지이므로 1564≈0.234\dfrac{15}{64}\approx0.234 입니다.
  3. 파스칼 삼각형 n=8n=8 줄의 수를 모두 더한 값
    28=2562^8=256 입니다. 줄을 직접 적어도 1+8+28+56+70+56+28+8+1=2561+8+28+56+70+56+28+8+1=256 입니다.
  4. 피자 토핑 6가지 중 원하는 만큼 골라 올리는 방법의 수, 그리고 적어도 하나는 올리는 방법의 수
    토핑마다 올린다·안 올린다 두 갈래라 26=642^6=64 가지입니다. 하나도 안 올리는 1가지를 빼면 64−1=6364-1=63 가지입니다.

연습 4 — 포함배제

  1. 1부터 60까지의 수 중 4의 배수이거나 6의 배수인 것의 개수
    4의 배수 15개, 6의 배수 10개, 둘 다인 12의 배수 5개입니다. 15+10−5=2015+10-5=20 개입니다.
  2. 1부터 60까지의 수 중 2, 3, 5 가운데 적어도 하나의 배수인 것의 개수
    하나씩은 30+20+12=6230+20+12=62, 둘씩 겹친 6·10·15의 배수는 10+6+4=2010+6+4=20, 셋 다인 30의 배수는 2개입니다. 62−20+2=4462-20+2=44 개입니다.
  3. 40명인 반에서 수학을 좋아하는 학생 22명, 영어 18명, 과학 15명이고, 수학·영어를 둘 다 좋아하는 학생 8명, 수학·과학 6명, 영어·과학 5명, 셋 다 3명입니다. 셋 중 어느 것도 좋아하지 않는 학생 수
    하나라도 좋아하는 학생은 22+18+15−8−6−5+3=3922+18+15-8-6-5+3=39 명입니다. 40−39=140-39=1 명입니다.

정리

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

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


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

LATEST

수학의 최신 글

수학2026.11.17

다양체 위의 최적화: 직교 제약과 Muon의 직교화가 하는 일

차트·접공간·리만 계량·측지선·후퇴로 다양체를 세우고, 스티펠·그라스만·양정치 행렬·확률 단체의 접공간과 사영을 계산한 뒤, 리만 그래디언트가 유클리드 그래디언트의 접공간 사영임을 증명하고 극분해 후퇴와 뉴턴–슐츠 반복의 수렴 조건을 다룹니다.

고급46 MIN
수학2026.11.17

프리컨디셔닝의 이론: Adam에서 K-FAC·Shampoo·Muon까지 한 줄로

갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.

고급41 MIN
수학2026.11.17

확률적 근사와 SGD의 연속 극한: 수렴한다는 말의 정확한 뜻

로빈스–먼로 조건과 마팅게일 잡음으로 SGD의 수렴을 정확히 정의하고, 볼록·강볼록·PL·비볼록에서의 수렴률과 오라클 하한을 계산한 뒤, SGD를 확률미분방정식으로 읽어 학습률/배치가 온도가 되는 관점과 안정성의 가장자리를 다룹니다.

고급48 MIN