9 - Gen. Perms. Combs. and Binomial Coefficients - 6.3,6.7

ucla | MATH 61 | 2022-10-10T11:45

Recall
Notes
Lecture

Recall

Notes

Supplemental Definitions

binomial coefficients
- $(a + b)^{n} = \prod_{k = 1}^{n} (a + b)$
- $a^{n - k} b^{k}$ appears as a term in our expansion by choosing b from k of the factor (a+b) and choosing a from (n-k) of the factors (a+b)
- $a^{n - k} b^{k}$ chosen in $(\binom{n}{k}) = (\binom{n}{n - k})$ ways

Examples

e.g. anagrams
- how many ways to reorder “MISSISSIPPI”
- $\frac{11!}{1! 4! 4! 2!}$
e.g. RGB piles (thm. 2)
- sps you have piles of RGB cubes w/ ≥ 8 in each color
- how many ways to select 8 total cubes
  - t-elements: 8 cubes
  - k-elements: 3 colors
  - $(\binom{8 + 3 - 1}{3 - 1})$
e.g. non-neg solutions (thm. 2)
- how many non-neg integer solutions to
- $x_{1} + x_{2} + x_{3} + x_{4} = 29$
- t-elements = 4 x’s
- k-elements = 29
- $(\binom{29 + 4 - 1}{4 - 1})$
- how many solutions if $x_{1} > 0, x_{2} > 1, x_{3} > 2, x_{4} \geq 0$
  - t-elts = 4
  - k-elts = 29 - 1 - 2 - 3 = 23
    - bc constraints for roots “Eats up” options
  - $(\binom{23 + 4 - 1}{4 - 1})$
e.g. binomial coefficients
- $(a + b)^{3} = (a + b) (a + b) (a + b)$
- $a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3}$
e.g. binom. thm.
- expand $(3 x - 2 y)^{4}$
- $a = 3 x, b = 2 y$
- $(a + b)^{4} = \sum_{k = 0}^{4} (\binom{4}{k}) a^{4 - k} b^{k}$
e.g. proof of pascals triangle thm. (combinatorically)
- show LHS & RHS are different ways to count the same set
- LHS
  - $(\binom{n + 1}{k})$
  - i.e. ways to choose k-subset from n+1 elements
- RHS
  - case 1: element $a_{n + 1}$ is in the k-subset
    - $(\binom{n}{k - 1})$ options left
  - case 2: not in k-subset
    - $(\binom{n}{k})$ options left
  - by addition principle (of distinct combinations)
  - $(\binom{n}{k - 1}) + (\binom{n}{k})$
- both LHS & RHS are computing cardinalities of the same set, they must be equal
e.g. proof of $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$ using binom. thm
- sps. a=1, b=1
- binom. thm. suggests
- $\sum_{k = 0}^{n} (\binom{n}{k}) (a)^{n - k} (b)^{k} = (1 + 1)^{n} = 2^{n}$

Big Ideas

Theorem 1
- suppose sequence S has n items with $n_{t}$ objects of type t
- the number of permutations is:
- $\frac{n!}{\prod_{1}^{t} n_{t}!}$
Theorem 2
- sps. x has t elts. the number of k=elt. selections from X, allowing repetitions, is
- $C (k + t - 1, t - 1) = C (k + t - 1, k)$
- $(\binom{k + t - 1}{t - 1}) = (\binom{k + t - 1}{k})$
binomial theorem
- for $a, b \in R, n \in Z_{> 0}$ , then
- $(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k} b^{k}$
pascals triangle
- in levels of rows, enumerated i, starting with 1, where each level represents the monomials $(a + b)^{i}$
pascals triangle theorem
- for $1 \leq k \leq n ⟹ (\binom{n + 1}{k}) = (\binom{n}{k - 1}) + (\binom{n}{k})$

Lecture

📌

**SUMMARY
**

9 - Gen. Perms. Combs. and Binomial Coefficients - 6.3,6.7

Table of Contents

Recall

Notes

Lecture