4. Exam 1 Review

In Class Review

1 bar, 15 tars, 17 chips, 13 g bars

1. 13 snacks, order doesn’t matter

46 choose 13 = 1.02 x 10

2. ways to choose 15 snacks, order doesn’t matter

46 choose 15 = 46!/(15!(46-15)!) = 5.11 x 10

3. ways to choose 13 snacks, order matters

46 pick 13 6.34 x 10

Stars and Bars

Organize $n$ items into $k$ groups using $\left(\genfrac{}{}{0ex}{}{n+k-1}{n}\right)=\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$.

Because accounting for arrangement of $k-1$ bars

must be indistinct items into distinct groups

Induction

prove base cases

assume induction hypothesis for up to k, prove it works for k + 1

Bijectivity

Injective (one-to-one)

• set two y equal, prove that their x must be equal

Surjective (onto)

• pick any y and compute an x from it. put it through function and show there is an x for every y

Plus Session Basic problems

relation - subset bijection - $|X|=|Y|$

pigeonhole

51 integers from 1-100 sum to 101 proof

• pigeonhole
• 50 pairs that sum to 101 (holes)
• pigeons are 51 integers selected
• one pair must have more than one

S25 Exam

1 - $X=1,2,3$ and $Y=A,B,C$