Chapter 2 - Basic Counting Rules

Question 1

Define: Product Rule

Answer 1

If something can happen in n1 ways and no matter how the first thing happens, a second thing can happen in n2 ways, and no matter how the first two things happen, a third thing can happen in n3 ways,…, then all these things can happen together in n1xn2xn3… ways

Question 2

Define: Sum Rule

Answer 2

If one event can occur in n1 ways, a second thing can happen in n2 different ways, a third event can happen in n3 different ways, …, then there are n1 + n2 + n3… ways in which exactly one of these things can happen

Question 3

Define: n-set

Answer 3

an n-set is a set of n distinct elements

Question 4

Define: permutation of an n-set

Answer 4

a permutation of an n-set is an arrangement of the elements of the set IN ORDER

n!

Question 5

define: r-permutation of an n-set

Answer 5

picking out r elements out of n elements of an n-set then arranging them in order

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

Question 6

Theorem: The number of subsets of an n-set is:

Answer 6

2x2x…x2 (n times) = 2^n

Question 7

Define: r-combination

Answer 7

an r-combination of an n-set is a selection of r elements from a set where the order DOES NOT matter

C(n,r) = n!/r!(n-r)!
or
the binomial coefficient, (n r)

C(n,r) = C(n,n-r) because the number of ways to choose r elements out of n is equivalent to choosing n-r elements to NOT be in the set

Question 8

Theorem: Pascal’s Identity

Answer 8

C(n,r) = C(n-1, r-1) + C(n-1, r)

Question 9

Theorem: Vandermonde’s Identity

Answer 9

C(n+m, r) = C(n,0)C(m,r)+C(n,1)C(m, r-1)+…+C(n,r)C(m,0) = ΣC(n,i)C(m, r-i)

Question 10

Define: probability

Answer 10

The probability of an event is the number of possible outcomes whose occurrence signals the event, divided by the total number of all possible outcomes

S: set of possible outcomes (sample space)
E: event
n(S) = number of outcomes in S
n(E) = number of outcomes in E

Probability of E = P(E) = n(E)/n(S)

Question 11

Define: P^R(m,r) = m^r

Answer 11

is the number of r-permutations of an m-set WITH REPLACEMENT/REPETITION ALLOWED

Question 12

Define: C^R(m,r) = C(m+r-1,r)

Answer 12

is the number of r-combinations of an m-set in which REPLACEMENT/REPETITION IS ALLOWED

Question 13

Occupancy problems: case 1a

Answer 13

distinguishable objects, distinguishable boxes, empty boxes allowed

k^n

Question 14

Occupancy problems: case 1b

Answer 14

distinguishable objects, distinguishable boxes, empty boxes NOT allowed

k!S(n,k)

Question 15

Occupancy problems: case 2a

Answer 15

indistinguishable objects, distinguishable boxes, empty boxes allowed

same as counting n-combinations of a k-set
or
C^R(k,n) = C(k+n-1, n)

Question 16

Occupancy problems: case 2b

Answer 16

indistinguishable objects, distinguishable boxes, empty boxes NOT allowed

C(n-1, k-1)

Question 17

Occupancy problems: case 3a

Answer 17

distinguishable objects, indistinguishable boxes, empty boxes allowed

S(n,k) + S(n, k-1) + … + S(n,2) + S(n,1)

Question 18

Occupancy problems: case 3b

Answer 18

distinguishable objects, indistinguishable boxes, empty boxes NOT allowed

S(n,k)

Question 19

Occupancy problems: case 4a

Answer 19

Indistinguishable objects, indistinguishable boxes, empty boxes allowed

= the number of ways to partition n into AT MOST k parts

Question 20

Occupancy problems: case 4b

Answer 20

Indistinguishable objects, indistinguishable boxes, empty boxes NOT allowed

= the number of ways to partition n into exactly k parts

Question 21

Theorem: Pigeonhole Principle

Answer 21

If k+1 pigeons are placed into k pigeonholes, then at least one pigeonhole will contain two or more pigeons.

Question 22

Theorem: The Equal Degrees

Answer 22

In any graph, there are two vertices of equal degree

Question 23

Theorem: Subsets without divisors

Answer 23

For any subset S ⊆ [2n] of size |S| > n, there are two numbers a,b ∈ S s.t a|b

Question 24

Theorem: Monotone Subsequences

Answer 24

For any sequence of mn+1 distinct real numbers a_0,…,a_mn, there is an increasing subsequence of length m+1 or a decreasing subsequence of length n+1

Question 25

Theorem: Erdos and Szekeres

Answer 25

Given a sequence of n^2+1 distinct integers, either there is an increasing subsequence of length n+1 or a decreasing subsequence of length n+1

Question 26

Theorem: Generalization of PHP

Answer 26

If m pigeons are placed into k pigeonholes, then at least one pigeonhole will contain MORE THAN the floor of (m-1)/k

Question 27

State the Ramsey Theorem for a graph on 6 vertices:

Answer 27

For any graph on 6 vertices, we can always find a clique of size 3 or a coclique of size 3

R(3,3) = 6

Question 28

State the Ramsey Theorem using subsets:

Answer 28

Suppose that S is any set of 6 elements. If we divide the 2-element subsets of S into 2 classes, say X and Y, then either

1) there is a 3-element subset of S, all of whose 2-element subsets are in X
OR
2) There is a 3-element subset of S, all of whose 2-element subsets are in Y

Generalized version: A positive integer N has the (p,q)-Ramsey Property for integers p,q ≥ 2. If the following holds, given any set of size N, if we divide the 2-subsets of S into two classes X and Y, then either:

1) there is a p-element subset, all of whose 2-element subsets are in X
OR
2) there is a q-element subset, all of whose 2-element subsets are in Y

Question 29

Define: clique

Answer 29

a clique of size t is a set of t vertices in a graph such that all pairs of vertices among them are adjacent

Question 30

Define: coclique

Answer 30

a coclique or independent set of size s is a set of s vertices such that there is NO edge between them

Question 31

Define: the Ramsey number R(p,q)

Answer 31

The Ramsey number R(p,q) is the minimum number N with (p,q)-Ramsey property

1) R(p,q) = R(q,p) = 1 for all p,q ≥ 1

2) R(3,3) = 6, R(3,4) = 9, R(3,5) = 14, R(4,4) = 18

3) The Ramsey Number R(p,q) is the minimum number N such that any graph on n vertices contains either a coclique of size p or a clique of size q

4) for any p≥ 1, R(p,1) = R(1,p) = 1

5) for any p≥ 2, R(p,2) = R(2, p) = p

6) R(p,q) ≤ C(p+q-2, p-1)

Question 32

State the Ramsey Numbers on the exam syllabus

Answer 32

1) R(k, l)
2) R(k) = R(k,k)
3) R(3,3) = 6
4) R(k,2) = k

Question 33

Define: Relatively prime

Answer 33

Two integers are relatively prime if they have no common divisor greater than 1

Question 34

Define: Euler’s Function

Answer 34

Euler’s function is defined to be the number of integers from 1 to n that are relatively prime to n

Φ(n) = nπ(1-(1/pi))