Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
31 Cards in this Set
- Front
- Back
Rule of Sum (Statement only) |
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. |
|
Rule of Sum (Justification using Set theory) |
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. |
|
Rule of Product (Statement only) |
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. |
|
Rule of Product (Proof from Rule of Sum) |
If |A|=m, and |B|=n, then |AxB| = m*n, where AxB = {(a, b) : a is element of A, b is element of B} |
|
Generalized Rule of Product |
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. |
|
Definition of number of r-samples from an n-set |
The number of r-samples from an n-set is n^r |
|
Proof of definition of number of r-samples from an n-set |
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. |
|
Rule of Difference |
#ways to do something = #total ways - #ways you can't do it |
|
Rule of Quotient |
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. |
|
Inclusion-Exclusion Formula |
For two sets A and B, |AuB| = |A| + |B| - |A intersect B| |
|
The Pigeonhole Principle |
If n+1 objects are distributed into n boxes, then some box gets more than one object |
|
Generalized Pigeonhole Principle |
If n objects are distributed into m boxes, then some box gets at least ceiling(n/m) objects |
|
ceiling(25.2) |
26 |
|
Theorem of Erdos-Szekeres |
Any sequence of n^2 + 1 numbers has a monotonic subsequence of length n+1 |
|
Proof of Erdos-Szekeres |
do proof then check |
|
Ramsey's Theorem (Statement only) |
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. |
|
Definition of r-permutation of an n-set |
An r-permutation of an n-set S is an arrangement or ordered r-tuple of distinct elements of S. |
|
Definition of permutation of a set |
This just means n-permutations (P(n, n)) |
|
Theorem & proof of P(n, r) |
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. |
|
MISSISSIPPI Thm (Statement Only) |
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!) |
|
MISSISSIPPI Thm (Proof) |
(#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) |
|
Definition of r-combination of an n-Set |
An r-combination from S is an unordered selection of r distinct elements from S |
|
Thm. & Proof of C(n, r) |
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)! |
|
Definition of binomial thm |
for (x + y)^n = summation of (n choose r)x^r*y^(n-r) from r=0 to n. |
|
Proof of binomial thm |
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)! |
|
Pascals Recurrence (Statement)
|
Let n >= k >= 1 be integers. Then:
n choose k = (n-1) choose (k-1) + (n-1) choose k |
|
Proof of symmetry of Pascal's triangle (2 proofs)
|
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 |
|
Proof of multinomial thm
|
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! |
|
Definition of # of unordered r-selections of an n-set, repetitions allowed
|
(n + r - 1) choose r, or C(n+r-1, r)
|
|
Proof of # of unordered r-selections of an n-set, repetitions allowed
|
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.
|
|
x1 + x2 + x3 + x4 + x5 = 22
n = ? r = ? |
n = 5
r = 22 |