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\rightarrow 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:

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

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

${\binom {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},\ldots ,A_{k}$ such that $\bigcup A_{i}=A$