CSCE 222 Lecture 21

« previous | Monday, March 28, 2011 | next »

Permutations

Ordered arrangement of $r$ elements is called an $r$-permuation.

$P(n,r)={\frac {n!}{(n-r)!}}$ is the number of $r$-permutations on a set of $n$ elements.

Combinations

An unordered selection of $r$ elements is called an $r$-combination (a subset with $r$ elements).

$C(n,r)={\binom {n}{r}}={\frac {P(n,r)}{r!}}={\frac {n!}{r!(n-r)!}}$ is the number of $r$-combinations on a set of $n$ elements.

Lemma

${\binom {n}{r}}={\binom {n}{n-r}}$

Proof. ${\frac {n!}{r!(n-r)!}}={\frac {n!}{(n-r)!(n-(n-r))!}}$

Example

How may 5-card poker hands can be dealt from a deck of 52 cards (notice that order doesn't matter here since one can rearrange the cards in any fashion).

${\binom {52}{5}}={\frac {52!}{5!(52-5)!}}=2,598,960$

Binomial Theorem

Let $x$ and $y$ be variables and $n$ be a nonnegative integer.

$(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n-k}$

Proof. The terms of the product $\underbrace {(x+y)(x+y)\ldots (x+y)} _{n}$ are of the form $x^{n-j}y^{j}$ (i.e. the two exponents sum to $n$).

Therefore, if we choose $j$ terms $y$ from the expanded product above, there are $n-j$ $x$'s. There are ${\binom {n}{j}}$ ways to select the $y$'s, so the coefficient of $x^{n-j}y^{j}$ is ${\binom {n}{j}}$.

Q.E.D.

Corollary 1

$\sum _{k=0}^{n}{\binom {n}{k}}=2^{n}$

Proof. Substitute $x=y=1$ into the Binomial Theorem, then $(1+1)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}1^{n-k}1^{n}=2^{n}$

Q.E.D.

Corollary 2

$\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}=0$

Proof. $0=0^{n}=(-1+1)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}(-1)^{k}1^{n-k}$.

Q.E.D.

Pascal's Triangle

For any row of Pascal's Triangle, let $n,k>0$ and $n\geq k$:

${\binom {n+1}{k}}={\binom {n}{k-1}}+{\binom {n}{k}}$

Proof. Let $T$ be a set with $n+1$ elements. Let $a\in T$ be a fixed element $S=T-\{a\}$. There are ${\binom {n+1}{k}}$ subsets of cardinality $k$ in $T$. The subsets either do or do not contain $a$. There are ${\binom {n}{k}}$ subsets of $S$ (i.e. subsets of $T$ that do not contain $a$). The number of subsets of $T$ that do contain $a$ correspond to the ${\binom {n}{k-1}}$ subsets of $S$ with $a$ added. Therefore the proposition holds true.