MATH 302 Lecture 20

« previous | Wednesday, November 9, 2011 | next »

Permutations and Combinations

Suppose we wanted to count the number of injective functions from a set $A$ to $B$ where $| A | = r$ and $| B | = n$

This is identical to $P (n, r)$ in that $A$ and $B$ are labeled.

For $n > 1$ ,

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

For example:

$(x + y)^{3} = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}$

This introduces the concept of a combinatorial proof:

A proof in which something is counted:

Proof of Binomial Theorem.

The semi-expansion of $(x + y)^{n} = \underset{n}{\underset{⏟}{(x + y) (x + y) \dots (x + y)}}$ has $n$ factors.

From these $n$ factors, there are $(\binom{n}{k})$ ways to choose a sequence of factors that match $x^{n - k} y^{k}$ for $0 \leq k \leq n$

$(1 + 1)^{n} = 2^{n} = \sum_{k = 0}^{n} (\binom{n}{k})$

The power set has a cardinality of

2^{n}

$(1 + (- 1))^{n} = 0 = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k})$

The number of sets of an odd order is the same ast the number of sets of an even order

The definition of constructing Pascal's triangle: take the two above and add them to make the one below.

(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) = (\binom{n}{k})

This is the way you count the number of subsets of order $k$ out of a set of size $n$ :

The number of subsets of order $r$ from a set of size $m + n$ is $(\binom{m + n}{r})$ :

(\binom{m + n}{k}) = \sum_{k = 0}^{r} (\binom{n}{k}) (\binom{m}{r - k})