MATH 302 Lecture 26

« previous | Wednesday, December 7, 2011 | next »

"Extra lecture" final exam study session

Chapter 5: Induction

Theorem: For $n<3$, $2^n<n!$

Proof by Induction.

Basis step. for $n=4$, $2^4=16<24=4!$ True.

Inductive step. Assume for some $k>3$ that $2^k<k!$. Multiply both sides by $k+1$

$(k+1)2^k<(k+1)k!=(k+1)!$

Since $2<k+1$, then

$2\cdot 2^k=2^{k+1}<(k+1)2^k$

By combining the two steps, we get

$2^{k+1}<(k+1)2^k<(k+1)!$

This proves the inductive step and the general result follows by the principle of mathematical induction.

Chapter 6: Counting

Suppose we break a committee of 5 people into three different subcommittees with at least one person in each subcommittee. How many ways can this be done?

Let $A$ represent the people and $B$ represent the committees. We need to count the number of onto functions $f:A\to B$

$3!S(5,3)$

Combinations with Repetion

How many ways are there to distribute 5 ping-pong balls into 3 boxes with at least one ball in each box? 3 are already accounted for, so we need to put 2 balls into 3 boxes with possible repettion:

$(\genfrac{}{}{0ex}{}{3-1+2}{2})$

How many ways are there to pick a dozen apples from a bushel of 3 different types when at least 3 of each kind must be chosen? 9 are already accounted for, leaving 3 to pick from 3 types with possible repetition:

$(\genfrac{}{}{0ex}{}{3-1+3}{3})=10$

Multinomial Coefficient

• How many ways can you put 5 different people into 3 different committees so that 2 are in the first, 2 are in the second, and 1 is in the third?*

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

Permutations with Repetition

How many ways are there to put 5 different people into 3 different committees with no restrictions?

There are 3 ways to put the first person into a committee, 3 ways for the second, etc.

$3\cdot 3\cdot 3\cdot 3\cdot 3=3^5$

Ex. 45

6 objects into 5 boxes with

1. everything labeled: $5^6$
2. objects labeled, boxes unlabeled: ???
3. objects unlabeled, boxes labeled: $C(6-1+5,5)$

Pigeonhole Principle

Given a set $A$ containing 3 elements, show that the union between a pair of any 5 subsets produces $A$

There are 8 subsets, and there are 4 pairs of subsets and their complements. Once a pair is completed, their union is $A$.

Chapter 9: Relations

Antisymmetry

If a is related to b and a is not equal to b, then b is not related to a In other words, if (a,b) is in R and (b,a) is in R, then a = b

Composition

for $(a,b)\in R_1$, if $(b,c)\in R_2$, then $(a,c)\in R_1\circ R_2$

Partitions

For $A=\{1,2,3\}$, a partition of $A$ consists of a collection of nonempty disjoint sets $A_1,A_2,\dots ,A_k$ such that $\bigcup A_i=A$