MATH 302 Lecture 21

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

Combinatorial Proofs

Show that ${\binom {n+1}{r+1}}=\sum _{j=r}^{n}{\binom {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,\ldots ,n$. The previous $r$ ones will be in the previous j positions, so ${\binom {j}{r}}$.

Example 2

$k{\binom {n}{k}}=n{\binom {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

${\binom {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)$)