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)=(\genfrac{}{}{0ex}{}{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

$(\genfrac{}{}{0ex}{}{n}{r})=(\genfrac{}{}{0ex}{}{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).

$(\genfrac{}{}{0ex}{}{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(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$

Proof. The terms of the product $\underset{n}{\underbrace{(x+y)(x+y)\dots (x+y)}}$ 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

$(\genfrac{}{}{0ex}{}{n}{j})$

ways to select the

$y$

's, so the coefficient of

$x^{n-j}{y}^j$

is

$(\genfrac{}{}{0ex}{}{n}{j})$

.

Q.E.D.

Corollary 1

$\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})=2^n$

Proof. Substitute

$x=y=1$

into the Binomial Theorem, then

$(1+1{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})1^{n-k}{1}^n=2^n$

Q.E.D.

Corollary 2

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

Proof.

$0=0^n=(-1+1{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{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\ge k$:

$(\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k-1})+(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{n+1}{k})$ subsets of cardinality $k$ in $T$. The subsets either do or do not contain $a$. There are $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{n}{k-1})$ subsets of $S$ with $a$ added. Therefore the proposition holds true.