Stat 110 Strategic Practice 1, Fall 2011

1. Naive Definition of Probability

For each part, decide whether the blank should be filled in with =, <, or >, and give a short but clear explanation.

Problem
(a) (probability that the total after rolling 4 fair dice is 21) (probability that the total after rolling 4 fair dice is 22)

Sol
일단 4번 굴려서 합이 21이 나오는 경우는 (6,6,6,3), (6,6,5,4), (6,5,5,5)이다.

중복된 값이 있는 permutation으로 각각의 경우의 수를 구해보면

(6,6,6,3): $\frac{4!}{3!} = 4$, (6,6,5,4) : $\frac{4!}{2!} = 12$, (6,5,5,5) : $\frac{4!}{3!} = 4$

따라서 $\frac{20}{6^4}$이다.

그러나 합이 22이 나오는 경우는 (6,6,6,4), (6,6,5,5)이다.

(6,6,6,4): $\frac{4!}{3!} = 4$, (6,6,5,5) : $\frac{4!}{2!2!} = 6$

따라서 $\frac{10}{6^4}$이다.

그러므로 정답은 >이다.

Problem
(b) (probability that a random 2 letter word is a palindrome1) (probability that a random 3 letter word is a palindrome)

Sol
2개 문자가 같은 것이 나올 경우의 수는 $\frac{26 \times 1}{26^2}$이다.

3개 문자를 나열 할 때 양 끝 문자가 같을 경우의 수는 $\frac{26 \times 26 \times 1}{26^3}$

그러므로 정답은 =이다.

Problem
(a) How many paths are there from the point (0, 0) to the point (110, 111) in the plane such that each step either consists of going one unit up or one unit to the right?

(b) How many paths are there from (0, 0) to (210, 211), where each step consists of
going one unit up or one unit to the right, and the path has to go through (110, 111)?

Sol
(a) 위로 110번, 오른쪽으로 111번 가야한다. 따라서 두가지 방법으로 접근 할 수 있는데, 중복이 있는 permutation과 combination이다.

Combination 측면에서 바라봤을 때 211개의 빈 자리 중 위로 올라가는 110개의 자리를 배치하는 것이기에 $_{221}C_{110}$이다.

(b) 먼저 (110, 111)로 가고 나서 (110, 111)에서 (210, 211)로 가야한다.

210-110 = 100, 211-111 = 100이다. 200개를 나열하는 모든 경우의 수를 구하고 그 안에서 중복되는 것들을 고려해서 나누어 주면 $\frac{200!}{100!100!}$이다.

Multiplication rule에 따라 정답은 $\binom{211}{110}\cdot\frac{200!}{100!100!}$이다.

Problem
A norepeatword is a sequence of at least one (and possibly all) of the usual 26 letters a,b,c,. . . ,z, with repetitions not allowed. For example, “course” is a norepeatword, but “statistics” is not. Order matters, e.g., “course” is not the same as “source”.
A norepeatword is chosen randomly, with all norepeatwords equally likely. Show that the probability that it uses all 26 letters is very close to 1/e.

Sol
$\binom{26}{k}k!$는 26개의 알파벳 중에서 $k$개를 선택하는 경우의 수와, 선택한 $k$개의 알파벳을 배열하는 경우의 수를 곱한 것이다.

---

2. Story Proofs

Problem
Give a story proof that $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Sol
동일한 대상, 즉 $n$명 중에서 만들 수 있는 모든 부분집합을 한쪽에서는 크기별로 나누어 세고 $\left(\sum \binom{n}{k}\right)$, 다른 한쪽에서는 각 원소의 선택 여부에 따라 세었으므로 $\left(2^n\right)$, 두 값은 서로 같을 수밖에 없다.

Problem
Give a story proof that $\frac{(2n)!}{2^n \cdot n!} = (2n-1)(2n-3)\cdots 3 \cdot 1$

Sol
좌변은 $2n$명을 한 줄로 세운 뒤, 같은 쌍을 이루는 경우를 중복해서 센 것을 제거한 것이다. 먼저 각 쌍 내부의 순서($A-B$와 $B-A$)는 서로 같은 경우이므로, 각 쌍마다 $2$가지씩 중복해서 세게 된다. 총 $n$개의 쌍이 있으므로 이를 제거하기 위해 $2^n$으로 나눈다. 또한 쌍들 사이의 배치 순서도 중요하지 않으므로, $n$개의 쌍을 배열하는 $n!$가지 경우의 수도 중복으로 세어진다. 따라서 좌변은 $2n$명을 일렬로 배열한 뒤 이러한 중복을 제거한 것이다.

우변은 각 사람의 파트너를 한 명씩 차례대로 선택하는 방식이다. 처음 사람은 자신을 제외한 $2n-1$명 중에서 파트너를 선택할 수 있고, 그다음 사람은 이미 짝이 정해진 사람을 제외한 $2n-2$명 중에서 선택할 수 있다. 이러한 과정을 반복하면 모든 사람이 하나의 쌍을 이루게 된다.
Problem
Show that for all positive integers n and k with n≥k,

doing this in two ways: (a) algebraically and (b) with a “story”, giving an interpretation for why both sides count the same thing.

Sol
(a)

(b)
좌변 $\left(\binom{n}{k}+\binom{n}{k-1}\right)$

전체 $n+1$명 중에서 특정 한 사람(예: 앤)을 미리 정해두고, 앤이 위원회에 포함되는지 여부에 따라 경우를 나누어 생각해 보자.

앤이 위원회에 포함되는 경우에는 앤이 이미 한 자리를 차지하고 있으므로, 나머지 $k-1$명의 위원을 앤을 제외한 $n$명 중에서 선택하면 된다. 따라서 경우의 수는 $\binom{n}{k-1}$이다.

앤이 위원회에 포함되지 않는 경우에는 앤을 제외한 나머지 $n$명 중에서 $k$명의 위원을 선택하면 되므로, 경우의 수는 $\binom{n}{k}$이다.

따라서 앤이 포함되는 경우와 포함되지 않는 경우를 모두 합하면 좌변은 $\left(\binom{n}{k}+\binom{n}{k-1}\right)$이 된다.

우변 $\left(\binom{n+1}{k}\right)$

전체 $n+1$명 중에서 특별한 조건 없이 $k$명을 바로 선택하면 되므로, 경우의 수는 $\left(\binom{n+1}{k}\right)$이다.

결국 두 식은 같은 $n+1$명 중에서 $k$명을 선택하는 경우의 수를 서로 다른 방식으로 센 것이므로,

가 성립한다.