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.

Binomial Theorem

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}+3x^{2}y+3xy^{2}+y^{3}$

This introduces the concept of a combinatorial proof:

Combinatorial Proofs

A proof in which something is counted:

Proof of Binomial Theorem.

The semi-expansion of $(x+y)^{n}=\underbrace {(x+y)(x+y)\dots (x+y)} _{n}$ 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$

Interesting Side-Effects

$(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

Pascal's Identity

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$:

1. number of sets which have a certain element $x$: ${\binom {n-1}{k-1}}$
2. number of sets which do not have a certain element $x$: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{n-1}{k}}

Corollary: Vander Monde's Identity

The number of subsets of order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} from a set of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m+n} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{m+n}{r}} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{m+n}{k} = \sum_{k=0}^r \binom{n}{k} \binom{m}{r-k}}