Discrete Math - Exam 2 Review

Front 1

Rule of Sum (Statement only)

Back 1

If there are m ways of doing one task, and n ways of doing another, there are m+n ways of doing one or the other, but not both.

Front 2

Rule of Sum (Justification using Set theory)

Back 2

If we have 2 disjoint finite sets A and B, then the length of the union of A and B is equal to the length of A plus the length of B.

Front 3

Rule of Product (Statement only)

Back 3

If one task can be performed m ways, and another can be performed n ways, then the number of ways to perform each task is m*n.

Front 4

Rule of Product (Proof from Rule of Sum)

Back 4

If |A|=m, and |B|=n, then |AxB| = m*n, where AxB = {(a, b) : a is element of A, b is element of B}

Front 5

Generalized Rule of Product

Back 5

Suppose there are r tasks to be performed, such that there are n1 ways to do task 1, n2 ways to do task 2, n3 ways to do task 3,......,nR ways to do task R. Then the total number of ways of doing each of the tasks is n1*n2*n3*.....*nR.

Front 6

Definition of number of r-samples from an n-set

Back 6

The number of r-samples from an n-set is n^r

Front 7

Proof of definition of number of r-samples from an n-set

Back 7

Claim: n^r

Pf: Let A={a1, a2, a3, ... , aN}. An r-sample is an ordered r-tuple: (x1, x2, ... , xR) where xi is an element of A. By the rule of product there are n choices for each xi, independent of the others, so there are n^r ways.

Front 8

Rule of Difference

Back 8

#ways to do something = #total ways - #ways you can't do it

Front 9

Rule of Quotient

Back 9

If you have an unknown number of ways to do a task, and for each there are m ways to do another task, and there are n ways to do both, then the unknown amount is n/m.

Front 10

Inclusion-Exclusion Formula

Back 10

For two sets A and B, |AuB| = |A| + |B| - |A intersect B|

Front 11

The Pigeonhole Principle

Back 11

If n+1 objects are distributed into n boxes, then some box gets more than one object

Front 12

Generalized Pigeonhole Principle

Back 12

If n objects are distributed into m boxes, then some box gets at least ceiling(n/m) objects

Front 13

ceiling(25.2)

Back 13

26

Front 14

Theorem of Erdos-Szekeres

Back 14

Any sequence of n^2 + 1 numbers has a monotonic subsequence of length n+1

Front 15

Proof of Erdos-Szekeres

Back 15

do proof then check

Front 16

Ramsey's Theorem (Statement only)

Back 16

For all k and l >= 1, if we color Red or B each edge on n points, then for n sufficiently large, we get either k points - all edges Red, OR l points - all edges Blue.

Front 17

Definition of r-permutation of an n-set

Back 17

An r-permutation of an n-set S is an arrangement or ordered r-tuple of distinct elements of S.

Front 18

Definition of permutation of a set

Back 18

This just means n-permutations (P(n, n))

Front 19

Theorem & proof of P(n, r)

Back 19

Claim: The number of r-permutations of an n-set is P(n, r) = n!/(n-r)!

Pf: There are n ways to pick the first element, then n-1 ways, then n-2.......then n-r+1 ways to pick the rth element. Rule of product says this is true.

Front 20

MISSISSIPPI Thm (Statement Only)

Back 20

If we have n objects with q1 of type 1, q2 of type 2......qR of type r, then the summation of qi from i=1 to r is equal to n, then the number of ways to arrange them all is n!/(q1!q2!.....qR!)

Front 21

MISSISSIPPI Thm (Proof)

Back 21

(#ways to arrange them)*(#ways to distinguish ones of the same type) = (#ways to arrange n distinct objects), so then:

(#ways to arrange them) = (#ways to arrange n distinct objects)/(#ways to distinguish ones of the same type)

Front 22

Definition of r-combination of an n-Set

Back 22

An r-combination from S is an unordered selection of r distinct elements from S

Front 23

Thm. & Proof of C(n, r)

Back 23

Thm: C(n, r) = n!/r!(n-r)!

Pf: P(n, r_ = #ways to arrange r elements from an n-set = (#ways to select r elements from an n-set)*(#ways to arrange the r selected elements),

so then

P(n, r) = C(n, r) * P(r, r),

C(n, r) = P(n, r)/P(r, r) = n!/r!(n-r)!

Front 24

Definition of binomial thm

Back 24

for (x + y)^n = summation of (n choose r)x^r*y^(n-r) from r=0 to n.

Front 25

Proof of binomial thm

Back 25

If we expand (x + y)^n, we'll have n terms, each (x + y). If we pick one of x or y from each factor:

ex. xyy.......x (n-terms)

2^n terms added up, each a product of n x's or y's + the number which have r x's + (n-r) y's = the number of ways to select the r terms that are x

= C(n, r) = n!/r!(n-r)!

Front 26

Pascals Recurrence (Statement)

Back 26

Let n >= k >= 1 be integers. Then:

n choose k = (n-1) choose (k-1) + (n-1) choose k

Front 27

Proof of symmetry of Pascal's triangle (2 proofs)

Back 27

1. By formula

2. Counting argument: n choose k says choose k elements from n, whereas n choose (n-k) says choose (n-k) elements that weren't

Front 28

Proof of multinomial thm

Back 28

Expand (x1 + x2+ ... + xr)^n into n factors. In the expansion we pick one variable from each factor and multiply them, we'll have rxrx...xr=r^n terms of the form xj1 xj2 .... xjr.

We collect terms with the same powers. The exponents add up to n. A term x1^i1....xr^ir occurs how many times? The number of ways to arrange i1 x1's, i2 x2's, ..... ,ir xr's. By the MISSISSIPPI thm, this is n!/i1!i2!i3!....ir!

Front 29

Definition of # of unordered r-selections of an n-set, repetitions allowed

Back 29

(n + r - 1) choose r, or C(n+r-1, r)

Front 30

Proof of # of unordered r-selections of an n-set, repetitions allowed

Back 30

This is the same as the number of ways to insert r-identical balls into n distinct boxes. Converting this model into a binary string, we'll have 100011001000......1. This begins and ends with 1, and will have r 0's, and n+1 1's. If we remove the 1's from the ends, we'll have n-1 1's, and a binary string of length n+r-1. Therefore C(n+r-1, r) will be the number of ways to insert r objects into n boxes.

Front 31

x1 + x2 + x3 + x4 + x5 = 22

n = ?

r = ?

Back 31

n = 5

r = 22