MATH 302 Lecture 21

« previous | Monday, November 14, 2011 | next »

Combinatorial Proofs

Show that $(\genfrac{}{}{0ex}{}{n+1}{r+1})=\sum _{j=r}^n(\genfrac{}{}{0ex}{}{j}{r})$

Let's try to count something: a binary string of length $n+1$ with $r+1$ ones

Assume that the position of the last 1 is at position $j+1$, where $j=r,\dots ,n$. The previous $r$ ones will be in the previous j positions, so $(\genfrac{}{}{0ex}{}{j}{r})$.

Example 2

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

The left-hand side represents

1. choosing a subset of size $k$ out of a set containing $n$ elements
2. choosing a special element from that subset

The right-hand side represents

1. choosing an element from a set of size $n$ to be in a subset
2. choosing the remaining subset members from the remaining elements

More Combinatorics

r-Permutations

ways to arrange $r$ elements from a set of size $n$

• no repetition
• order matters.

$P(n,r)=\frac{n!}{(n-r)!}$

r-Combinations

ways to choose $r$ elements from a set of size $n$

• no repetition
• order does not matter

$C(n,r)=\frac{n!}{r!(n-r)!}$

r-Permutations with Repetition

ways to arrange $r$ elements from a set of size $n$

• repeated choices allowed
• order matters

$n^r$

r-Combinations with Repetition

ways to choose $r$ elements from a set of size $n$

• repeated choices allowed
• order does not matter

$C(n-1+r,r)$

Multinomial Coefficients

ways to rearrange letters of "MISSISSIPPI"

• 11! possible ways
• 4 indistinguishable I's that can be arranged 4! ways
• 4 S's
• 2 P's
• 1 M

$(\genfrac{}{}{0ex}{}{11}{4,4,2,1})=\frac{11!}{4!4!2!(1!)}$

Examples

1. Number of ways to select 6 bagels from 8 different types of bagels (r-Comb w/ rep: $C(8+6-1,6)$)
2. Number of ways to select a dozen bagels with at least one of each kind (r-Comb w/ rep for rem. bagels after 8 have been picked: $C(8+4-1,4)$)