1회 · 확률이란 무엇인가 · 노트

1 도박장에서 태어난 확률

확률의 첫 계산은 모두 같은 모양이었다. 주사위나 카드에서 일어날 수 있는 경우를 빠짐없이 세고, 그 가운데 원하는 경우의 비율을 구한다. 그러려면 먼저 잘 세는 법이 필요하다. 이 절은 셈의 원리를 증명하고, 그것으로 17세기의 세 문제(Galileo의 주사위, de Méré의 내기, 점수 분배)를 푼다.

1.1 점수 분배 문제와 Pacioli의 답

역사 Luca Pacioli는 1494년 Summa de arithmetica에서 멈춘 내기의 판돈을 이긴 판 수에 비례해 나누라고 했다. 1556년 Tartaglia는 이 규칙이 이상한 답을 낸다고 지적했다. 먼저 6판을 이기는 내기에서 1:0으로 멈추면 Pacioli의 규칙은 판돈 전부를 A에게 준다. 겨우 한 판을 앞섰을 뿐인데도 그렇다. Tartaglia와 Cardano도 다른 규칙을 내놓았지만 맞는 답은 아니었다.

문제를 정확히 쓰자. A와 B가 여러 판을 하고, 먼저 정해진 수의 판을 이기는 쪽이 판돈을 모두 갖는다. 판마다 A가 이길 확률은 $p$, B가 이길 확률은 $q=1-p$이고 판들의 결과는 서로 영향을 주지 않는다. 내기가 멈춘 순간 A가 이기려면 $a$판, B가 이기려면 $b$판을 더 이겨야 한다. 이 상태를 $(a,b)$로 쓴다.

Pascal과 Fermat가 받아들인 공평함의 기준은 다음과 같다. 판돈을 계속했다면 각자가 이겼을 확률에 비례해 나눈다. 여는 질문의 상태는 $(a,b)=(1,3)$이다. Pacioli의 답 $5:3$이 이 기준과 어떻게 다른지는 1.4절에서 본다.

1.2 셈의 원리

정리 1.1 (곱의 법칙) $k$단계로 이루어진 선택에서 1단계의 방법이 $n_1$가지이고, 앞 단계에서 무엇을 골랐든 $j$단계의 방법이 $n_j$가지이면, 전체 선택의 방법은 $n_1n_2\cdots n_k$가지다.

증명 $k$에 대한 귀납법. $k=1$이면 자명하다. $k-1$단계까지의 선택이 $n_1\cdots n_{k-1}$가지라고 하자. 그 각각에 $k$단계의 $n_k$가지가 이어 붙으므로, 전체는 $n_k$개씩 묶인 $n_1\cdots n_{k-1}$개의 묶음이고 원소 수는 $n_1\cdots n_{k-1}\cdot n_k$다.

정리 1.2 (순열) 서로 다른 $n$개에서 $k$개를 골라 한 줄로 늘어놓는 방법의 수는

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

이다. 특히 $n$개 전부를 늘어놓는 방법은 $n!$가지다($0!=1$로 둔다).

증명 첫 자리에 $n$가지, 둘째 자리에는 남은 $n-1$가지, …, $k$째 자리에는 $n-k+1$가지가 있다. 정리 1.1로 곱한다.

정의 1.3 (조합) 서로 다른 $n$개에서 순서를 생각하지 않고 $k$개를 고르는 방법의 수, 곧 $n$개짜리 집합의 $k$개짜리 부분집합의 수를 $\tbinom nk$로 쓴다. $k<0$이거나 $k>n$이면 $\tbinom nk=0$으로 둔다.

정리 1.4 (조합의 수) $0\le k\le n$이면

$$\binom nk=\frac{n!}{k!\,(n-k)!} .$$

증명 $k$개를 골라 늘어놓는 방법(정리 1.2)을 두 단계로 센다. 먼저 $k$개짜리 부분집합을 고르고($\tbinom nk$가지), 고른 $k$개를 늘어놓는다($k!$가지). 곱의 법칙으로 $\tbinom nk\,k!=\tfrac{n!}{(n-k)!}$이다.

정리 1.5 (Pascal의 항등식) $n\ge1$이면

$$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k} .$$

증명 전략 $\{1,\dots,n\}$의 $k$개짜리 부분집합을 원소 $n$을 포함하는 것과 포함하지 않는 것으로 나눠 센다. 단계별 증명은 연습 1.8(유도형)에서 직접 쓴다. 완성된 증명은 그 연습의 풀이에 있다.

정리 1.6 (이항정리) $n\ge0$이고 $x,y$가 실수이면

$$(x+y)^n=\sum_{k=0}^n\binom nk x^ky^{n-k} .$$

증명 전략 $n$에 대한 귀납법 [T3]. $(x+y)^{n+1}=(x+y)(x+y)^n$을 전개하고, 같은 거듭제곱의 계수를 Pascal의 항등식(정리 1.5)으로 합친다. 단계별 증명은 연습 1.9(유도형)에서 직접 쓴다. 완성된 증명은 그 연습의 풀이에 있다.

따름정리 1.7 (이항계수의 합) 모든 $n\ge0$에서 첫 식이, $n\ge1$이면 둘째 식이 성립한다.

$$\sum_{k=0}^n\binom nk=2^n,\qquad \sum_{k=0}^n(-1)^k\binom nk=0 .$$

증명 정리 1.6에 $x=y=1$, 그리고 $x=-1,\ y=1$을 넣는다.

예제 1.8 (Galileo의 세 주사위 (1620년 무렵)) 도박꾼들은 세 주사위의 합이 9가 되는 경우와 10이 되는 경우가 모두 여섯 가지라고 셌다.

$$\begin{gather*} 9:\quad \{1,2,6\},\ \{1,3,5\},\ \{1,4,4\},\ \{2,2,5\},\ \{2,3,4\},\ \{3,3,3\},\\ 10:\quad \{1,3,6\},\ \{1,4,5\},\ \{2,2,6\},\ \{2,3,5\},\ \{2,4,4\},\ \{3,3,4\}. \end{gather*}$$

그런데 경험상 10이 더 자주 나왔다. Galileo의 설명은 이렇다. 같은 확률로 일어나는 것은 이런 조합이 아니라 순서까지 구별한 $6^3=216$가지 결과다(주사위에 빨강·파랑·초록 색을 칠했다고 생각하면 된다). $\{1,2,6\}$처럼 세 수가 다르면 순서가 $3!=6$가지, $\{1,4,4\}$처럼 둘이 같으면 $3$가지, $\{3,3,3\}$은 $1$가지다. 따라서

$$\#\{\text{합}=9\}=6+6+3+3+6+1=25,\qquad \#\{\text{합}=10\}=6+6+3+6+3+3=27,$$

이고 확률은 $\tfrac{25}{216}\approx0.116$과 $\tfrac{27}{216}=0.125$다.

그림 1.1 세 주사위의 합. 216가지 순서쌍 가운데 합이 9인 것(파랑)은 25가지, 10인 것(빨강)은 27가지다.

교훈 확률을 “유리한 경우 ÷ 전체 경우”로 계산하려면 같은 확률로 일어나는 경우를 세야 한다. 무엇이 같은 확률인지는 수학이 정해 주지 않는다. 4.6절에서 이것을 “균등 확률공간”이라는 가정으로 명시하고, 3절에서 이 가정이 무너지는 경우를 본다.

1.3 de Méré의 두 내기

역사 파리의 사교계 인사 Chevalier de Méré(본명 Antoine Gombaud)는 1654년 Pascal에게 두 문제를 냈다. 하나는 점수 분배 문제였고, 다른 하나는 아래의 주사위 내기였다. de Méré는 두 내기가 같은 정도로 유리하다고 믿었는데 경험은 그렇지 않았다.

예제 1.9 (주사위 4번 vs 주사위 두 개 24번) 내기 1: 주사위 하나를 4번 던져 6이 적어도 한 번 나오면 이긴다. 내기 2: 주사위 두 개를 24번 던져 (6,6)이 적어도 한 번 나오면 이긴다.

de Méré의 추론은 비례였다. 주사위 하나는 6가지, 두 개는 36가지이므로, 4번이 하나짜리에 맞다면 두 개짜리에는 $4\times6=24$번이 맞다. 그러나 정확한 값은 “한 번도 나오지 않는다”의 확률을 빼서 얻는다.

$$P(\text{내기 1})=1-\Bigl(\frac56\Bigr)^4=\frac{671}{1296}\approx0.5177,\qquad P(\text{내기 2})=1-\Bigl(\frac{35}{36}\Bigr)^{24}\approx0.4914 .$$

내기 1은 유리하고 내기 2는 불리하다. 여기서 쓴 두 가지, 곧 “적어도 한 번”의 확률이 $1-P(\text{한 번도 없음})$라는 것(정리 4.3(c))과 던질 때마다 확률을 곱해도 된다는 것(독립, 5.4절)은 4·5절에서 증명한다.

그림 1.2 왼쪽: 던지는 횟수에 따른 두 내기의 승률. 두 개짜리는 25번부터 $\tfrac12$을 넘는다. 오른쪽: 각 내기를 2만 번 시뮬레이션한 누적 승률과 $p\pm2\sqrt{p(1-p)/n}$ 띠(8.1절).

비례 추론은 왜 거의 맞았나 한 번에 성공할 확률이 $p$일 때 $n$번 안에 한 번이라도 성공할 확률이 $\tfrac12$을 넘는 최소의 $n$은 $n\ge\log2/(-\log(1-p))$이다. $p$가 작으면 $-\log(1-p)\approx p$이므로 $n\approx0.693/p$, 곧 $n$은 $1/p$에 비례한다. 이것이 de Méré의 비례 규칙이다. $p=\tfrac1{36}$이면 근사 $24.95$, 정확한 값 $24.6$이라 규칙이 거의 맞지만, $p=\tfrac16$이면 근사 $4.16$, 정확한 값 $3.80$이라 어긋난다. 두 내기의 기준을 같은 비례로 정한 것이 문제였다.

1.4 Pascal과 Fermat의 해 (1654)

역사 1654년 여름 Pascal과 Fermat는 편지로 점수 분배 문제를 풀었다. 7월 29일 Pascal의 편지에는 판돈이 한 사람당 32피스톨(합 64)인 예가 있다. 먼저 세 판을 이기는 내기에서 2:1이면 앞선 사람이 48, 2:0이면 56, 1:0이면 44를 가져야 한다. Fermat는 경우를 모두 세는 방법으로, Pascal은 한 판씩 거꾸로 따라가는 방법으로 같은 답에 이르렀다.

정리 1.10 (점수 분배 — Fermat의 공식) 상태 $(a,b)$에서 A가 결국 이길 확률은

$$f(a,b)=\sum_{k=a}^{a+b-1}\binom{a+b-1}{k}\,p^k\,q^{\,a+b-1-k}.$$

증명 

1단계: 가상의 연장. $m=a+b-1$로 둔다. 승부가 이미 났더라도 정확히 $m$판을 끝까지 한다고 상상한다. 이렇게 해도 승자는 바뀌지 않는다. $m$판 가운데 A가 이긴 판 수를 $K$라 하면 B는 $m-K$판을 이긴다. $K\ge a$이면 $m-K\le b-1$이므로 A가 B보다 먼저 $a$승에 이른다. $K\le a-1$이면 $m-K\ge b$이므로 B가 먼저 $b$승에 이른다. 실제 승부는 $m$판 안에 반드시 끝나고, 그 뒤의 판은 결과를 바꾸지 않는다. 따라서 “A가 이긴다”는 “$K\ge a$”와 같다.

2단계: 수열을 센다. $m$판의 결과를 A/B로 쓴 길이 $m$의 수열 가운데 A가 정확히 $k$번 나오는 것은 $\tbinom mk$개다(A가 나올 자리를 고른다). 판들이 서로 영향을 주지 않으므로 그런 수열 하나의 확률은 $p^kq^{m-k}$다(이 곱셈은 5.4절의 독립으로 정당화된다).

3단계: 더한다. $K\ge a$인 경우를 모두 더하면 결론이 나온다.

그림 1.3 $p=\tfrac12$일 때 상태 $(a,b)$에서 A가 이길 확률. 칸마다 바로 위 칸과 바로 왼쪽 칸의 평균이다(Pascal의 재귀, 정리 5.13).

예제 1.11 (Pacioli와 Pascal의 차이) 여는 질문에서 A는 1판, B는 3판이 더 필요하다($p=\tfrac12$). B가 이기려면 남은 판을 세 번 내리 이겨야 하므로

$$f(1,3)=1-\Bigl(\frac12\Bigr)^3=\frac78 .$$

판돈은 Pacioli의 $5:3$이 아니라 $7:1$로 나눠야 한다. Pascal의 편지의 수도 같은 식으로 나온다. 2:1이면 $(a,b)=(1,2)$이고 $64\cdot\tfrac34=48$, 2:0이면 $(1,3)$이고 $64\cdot\tfrac78=56$, 1:0이면 $(2,3)$이고 $64\cdot\tfrac{11}{16}=44$다.

그림 1.4 먼저 6판을 이기는 내기의 모든 중간 점수 $(i,j)$에서 Pacioli의 몫 $i/(i+j)$와 공평한 몫. 점선 위의 점은 Pacioli가 앞선 쪽을 과소평가한 경우다.

Pascal은 경우를 세지 않고 한 판씩 거꾸로 따라갔다. 다음 판에서 A가 이기면 상태는 $(a-1,b)$, 지면 $(a,b-1)$이 된다. 그러므로

$$f(a,b)=p\,f(a-1,b)+q\,f(a,b-1),\qquad f(0,b)=1,\quad f(a,0)=0 .$$

그림 1.3의 칸들이 이 재귀로 채워진다. 이 식은 5.5절에서 전확률 공식의 한 예로 증명되고, Fermat의 공식과 같은 답을 준다는 것은 연습 1.6에서 보인다.

1.5 Huygens (1657): 기대 몫

역사 1655년 파리를 방문한 네덜란드의 Christiaan Huygens는 Pascal–Fermat의 해법을 전해 듣고, 1657년 De ratiociniis in ludo aleae(주사위 놀이의 계산에 대하여)를 냈다. 처음으로 인쇄된 확률 교과서다. 첫 명제는 이렇다. “$a$를 얻을 기회가 $p$번, $b$를 얻을 기회가 $q$번이고 모두 같은 정도로 일어날 수 있다면, 그 내기의 값어치는 $\tfrac{pa+qb}{p+q}$이다.”

점수 분배의 공평한 몫은 Huygens의 언어로 “판돈 × 이길 확률”, 곧 내기의 기대 몫이다. 이 생각을 확률변수로 일반화한 것이 기댓값이고, 2회의 첫 주제다.

연습문제

연습 1.1 (포커의 풀하우스 ★) 52장에서 5장을 뽑는 방법은 $\tbinom{52}5=2{,}598{,}960$가지다. 풀하우스(같은 숫자 3장 + 다른 같은 숫자 2장)의 확률을 구하라.

풀이

같은 숫자 3장의 숫자를 고르고(13가지) 그 숫자의 무늬 3개를 고른다($\tbinom43=4$). 나머지 2장의 숫자는 남은 12개 가운데 하나이고 무늬 2개를 고른다($\tbinom42=6$). 곱의 법칙으로 $13\cdot4\cdot12\cdot6=3744$가지이므로

$$P(\text{풀하우스})=\frac{3744}{2{,}598{,}960}\approx0.00144 .$$

연습 1.2 (로또 ★) 1부터 45까지에서 6개를 고르는 로또에서 1등(6개 모두 일치)의 확률과, 정확히 5개가 맞을 확률(보너스 번호 무시)을 구하라.

풀이

6개를 고르는 방법은 $\tbinom{45}6=8{,}145{,}060$가지이고 1등은 그 가운데 하나다. 정확히 5개가 맞으려면 당첨 번호 6개에서 5개($\tbinom65=6$), 나머지 39개에서 1개($39$)를 고른다.

$$P(1\text{등})=\frac1{8{,}145{,}060}\approx1.23\times10^{-7},\qquad P(\text{정확히 5개})=\frac{6\cdot39}{8{,}145{,}060}\approx2.87\times10^{-5}.$$

연습 1.3 (Vandermonde 항등식의 특수형 ★★) 다음 항등식을 두 가지로 보여라.

$$\sum_{k=0}^n\binom nk^2=\binom{2n}n$$

(a) 남자 $n$명, 여자 $n$명에서 $n$명을 고르는 방법을 센다. (b) $(1+x)^n(1+x)^n=(1+x)^{2n}$에서 $x^n$의 계수를 비교한다.

풀이

(a) $2n$명에서 $n$명을 고르는 방법은 $\tbinom{2n}n$이다. 이것을 고른 남자의 수 $k$로 나누면 남자 $k$명($\tbinom nk$)과 여자 $n-k$명($\tbinom n{n-k}=\tbinom nk$)을 고르는 방법이므로 $\sum_k\tbinom nk^2$이다. (b) 이항정리로 $(1+x)^n(1+x)^n$에서 $x^n$의 계수는 $\sum_k\tbinom nk\tbinom n{n-k}=\sum_k\tbinom nk^2$이고, $(1+x)^{2n}$에서는 $\tbinom{2n}n$이다.

연습 1.4 (Galileo의 11과 12 ★) 세 주사위의 합이 11인 경우와 12인 경우를 예제 1.8처럼 조합과 순서쌍으로 각각 세어라.

풀이

합 11: $\{1,\allowbreak 4,\allowbreak 6\},\allowbreak \{1,\allowbreak 5,\allowbreak 5\},\allowbreak \{2,\allowbreak 3,\allowbreak 6\},\allowbreak \{2,\allowbreak 4,\allowbreak 5\},\allowbreak \{3,\allowbreak 3,\allowbreak 5\},\allowbreak \{3,\allowbreak 4,\allowbreak 4\}$의 6가지 조합이고, 순서쌍은 $6+3+6+6+3+3=27$가지. 합 12: $\{1,\allowbreak 5,\allowbreak 6\},\allowbreak \{2,\allowbreak 4,\allowbreak 6\},\allowbreak \{2,\allowbreak 5,\allowbreak 5\},\allowbreak \{3,\allowbreak 3,\allowbreak 6\},\allowbreak \{3,\allowbreak 4,\allowbreak 5\},\allowbreak \{4,\allowbreak 4,\allowbreak 4\}$이고, 순서쌍은 $6+6+3+3+6+1=25$가지. 분포가 10.5를 중심으로 대칭이므로 11과 10, 12와 9의 수가 같다(그림 1.1).

연습 1.5 (한 개짜리 내기의 기준 ★) 주사위 하나를 $n$번 던져 6이 적어도 한 번 나올 확률이 $\tfrac12$을 넘는 최소의 $n$을 구하라. 비례 근사 $0.693/p$와 비교하라.

풀이

$1-(5/6)^n>\tfrac12\iff n>\log2/\log(6/5)=3.80$이므로 $n=4$다($n=3$이면 $0.421$, $n=4$이면 $0.518$). 비례 근사 $0.693\times6=4.16$은 정확한 경계 $3.80$보다 크다. $p=\tfrac16$은 “작은 $p$”가 아니어서 $-\log(1-p)\approx p$가 잘 맞지 않는다.

연습 1.6 (Fermat의 공식은 Pascal의 재귀를 만족한다 ★★) 정리 1.10의 $f(a,b)$가 $a,b\ge1$에서 $f(a,\allowbreak b)=p\,f(a-1,\allowbreak b)+q\,f(a,\allowbreak b-1)$을 만족함을 보여라. (힌트: $\tbinom{m}{k}=\tbinom{m-1}{k-1}+\tbinom{m-1}{k}$를 쓰고, $f(a-1,b)$와 $f(a,b-1)$이 모두 $m-1=a+b-2$판짜리 합임에 주목한다.)

풀이

$m=a+b-1$로 두면 $f(a-1,b)$와 $f(a,b-1)$은 모두 $m-1$판짜리 합이다.

$$\begin{align*} p\,f(a-1,b)+q\,f(a,b-1) &=\sum_{k\ge a-1}\binom{m-1}{k}p^{k+1}q^{m-1-k}+\sum_{k\ge a}\binom{m-1}{k}p^kq^{m-k}\\ &=\sum_{j\ge a}\Bigl[\binom{m-1}{j-1}+\binom{m-1}{j}\Bigr]p^jq^{m-j}=\sum_{j\ge a}\binom mjp^jq^{m-j}=f(a,b). \end{align*}$$

첫 합에서 $j=k+1$로 바꿨고, 마지막에 Pascal 항등식(정리 1.5)을 썼다. 경계도 맞는다. $f(0,b)$는 $m=b-1$판의 이항 확률을 모두 더한 것이므로 이항정리로 1이고, $f(a,0)$은 $k\ge a>m=a-1$인 항이 없으므로 0이다.

연습 1.7 (실력이 다른 두 사람 ★) A가 판마다 $0.6$의 확률로 이긴다. 상태 $(a,b)=(2,3)$에서 A가 이길 확률을 구하라. $p=\tfrac12$일 때의 $\tfrac{11}{16}$과 비교하라.

풀이

$m=4$판에서 A가 2판 이상 이길 확률이다.

$$\binom42(0.6)^2(0.4)^2+\binom43(0.6)^3(0.4)+(0.6)^4=0.3456+0.3456+0.1296=0.8208 .$$

판마다 $0.6$의 우위가 승부에서는 $0.69$에서 $0.82$로 커진다.

연습 1.8 (Pascal의 항등식 증명 ★ 유도형) 정리 1.5을 두 가지로 증명하라.

1. (a)

   (세기) $\{1,\dots,n\}$의 $k$개짜리 부분집합 가운데 원소 $n$을 포함하는 것의 수와 포함하지 않는 것의 수를 각각 정의 1.3로 세어라. 두 묶음이 겹치지 않고 합치면 전체가 됨을 확인하라.

2. (b)

   (계산) $1\le k\le n-1$이면 정리 1.4의 식을 오른쪽에 넣고 통분해 왼쪽을 얻어라.

3. (c)

   $k=0$과 $k=n$, 그리고 $k<0$이나 $k>n$에서 식이 성립함을 정의 1.3의 약속으로 확인하라. (a)와 (b) 가운데 어느 증명이 이 경우들을 따로 다룰 필요가 없는가?

풀이

(a) 원소 $n$을 포함하는 $k$개짜리 부분집합은 나머지 $k-1$개를 $\{1,\dots,n-1\}$에서 고른 것과 하나씩 대응하므로 $\tbinom{n-1}{k-1}$개다. 포함하지 않는 것은 $k$개를 모두 $\{1,\dots,n-1\}$에서 고른 것이므로 $\tbinom{n-1}k$개다. 모든 부분집합은 $n$을 포함하거나 포함하지 않으며 둘 다일 수는 없으므로, 두 묶음은 겹치지 않고 합치면 전체다. (b) $1\le k\le n-1$이면

$$\binom{n-1}{k-1}+\binom{n-1}k=\frac{(n-1)!}{(k-1)!\,(n-k)!}+\frac{(n-1)!}{k!\,(n-1-k)!}=\frac{(n-1)!}{k!\,(n-k)!}\bigl(k+(n-k)\bigr)=\binom nk .$$

통분할 때 $k!=k\cdot(k-1)!$, $(n-k)!=(n-k)\cdot(n-1-k)!$을 썼다. (c) $k=0$: 왼쪽은 1, 오른쪽은 $\tbinom{n-1}{-1}+\tbinom{n-1}0=0+1$. $k=n$: 왼쪽은 1, 오른쪽은 $\tbinom{n-1}{n-1}+\tbinom{n-1}n=1+0$. $k<0$이나 $k>n$이면 양변이 0이다. (a)의 세기는 $k$의 범위를 가리지 않는다. $k=0$이면 “$n$을 포함하는 0개짜리 부분집합”이 없다는 것이 바로 $\tbinom{n-1}{-1}=0$이다. (b)는 계승의 식이 $0\le k\le n$에서만 정의되므로 경계를 따로 봐야 한다.

연습 1.9 (이항정리 증명 ★★ 유도형) 정리 1.6을 $n$에 대한 귀납법으로 증명하라.

1. (a)

   $n=0$에서 양변이 1임을 확인하라.

2. (b)

   $n$에서 식이 성립한다고 하자. $(x+y)^{n+1}=x(x+y)^n+y(x+y)^n$에 귀납 가정을 넣고, 첫째 합의 첨자를 $j=k+1$로 바꿔 두 합을 모두 $x^jy^{n+1-j}$의 합으로 써라.

3. (c)

   $1\le j\le n$인 항의 계수를 Pascal의 항등식으로 합치고, $j=0$과 $j=n+1$인 항을 따로 확인해 $n+1$에서의 식을 얻어라.

4. (d)

   귀납법 대신 세기로도 증명할 수 있다. $(x+y)^n$을 곱셈 그대로 전개한 $2^n$개의 항 가운데 $x^ky^{n-k}$인 항의 수를 정의 1.3로 세어 같은 결론을 얻어라.

풀이

(a) $(x+y)^0=1$이고 오른쪽은 $\tbinom00x^0y^0=1$이다. (b) 귀납 가정을 넣으면

$$(x+y)^{n+1}=\sum_{k=0}^n\binom nkx^{k+1}y^{n-k}+\sum_{k=0}^n\binom nkx^ky^{n+1-k} =\sum_{j=1}^{n+1}\binom n{j-1}x^jy^{n+1-j}+\sum_{j=0}^{n}\binom njx^jy^{n+1-j} .$$

첫째 합에서 $j=k+1$로 바꿨다. (c) $1\le j\le n$인 항은 두 합에 모두 있고 계수는 $\tbinom n{j-1}+\tbinom nj=\tbinom{n+1}j$이다(정리 1.5). $j=0$인 항은 둘째 합에만 있고 계수 $\tbinom n0=1=\tbinom{n+1}0$이다. $j=n+1$인 항은 첫째 합에만 있고 계수 $\tbinom nn=1=\tbinom{n+1}{n+1}$이다. 따라서 $(x+y)^{n+1}=\sum_{j=0}^{n+1}\tbinom{n+1}jx^jy^{n+1-j}$이다. (d) $(x+y)^n=(x+y)(x+y)\cdots(x+y)$을 분배법칙만으로 전개하면, 각 인수에서 $x$나 $y$를 하나씩 골라 곱한 $2^n$개의 항이 나온다. $x$를 고른 인수가 $k$개인 항은 $x^ky^{n-k}$이고, $x$를 고를 $k$개의 인수를 정하는 방법은 $n$개 인수의 $k$개짜리 부분집합의 수 $\tbinom nk$다. 귀납법은 Pascal의 항등식을 쓰고, 세기는 그것을 쓰지 않는다.

이 절을 PDF로 보기 (3쪽)노트북 1절

이 회차에서 읽은 절 0개 · 회차 차례