Suppose you have seven dice–each a different color of the rainbow; otherwise the dice are standard,with faces numbered 1 to 6. A roll is a sequence specifying a value for each die in rainbow(ROYGBIV) order. For example, one roll is(3,1,6,1,4,5,2)indicating that the red die showed a3, the orange die showed 1, the yellow 6, etc.
Combinatorial Arguments
Discrete Mathematics
City College of San Francisco
Outline
• Counting Techniques: Peer Review Assignment Q&A
• Combinatorial Arguments
• Combinatorial Proofs
• The Pigeonhole Principle
Combinatorial Arguments
Combinatorial Proofs
• Rather than relying on algebraic techniques, you can sometimes prove the
equality of two mathematical expressions by using each expression to count the
same set.
• Combinatorial Proofs:
•
•
•
•
Define some set S.
Determine |S| using some formulaic expression l.
Determine |S| using some other formulaic expression r .
Conclude l = r .
A point of struggle is that S can present anything: strings, numbers, people, etc.
Let S contain elements that are easy for you to count conceptually.
zyBooks Exercise 11.2.4 (b)
Prove the following proposition by using a combinatorial argument:
Proposition
For positive integers, n, m, and k , where k ≤ m ≤ n:
n m
m
k
=
n n − k
k
m−k
.
zyBooks Exercise 11.2.4 (b) – Sample Response
Proof.
We will argue the truth of this statement using a combinatorial argument. Consider the
set A := {1, 2, 3, . . . , n}. This gives that |A| = n. Now, let’s count the number of ways
to select two disjoint subsets B and C from A where |B| = k and |C| = m − k for
positive integers, n, m, and k, where k ≤ m ≤ n. This means that
|B ∪ C| = k + m − k = m. All such pairs of disjoint subsets B and C form the set S we
want to count. Let’s count |S| in two ways.
n
1. There are m
ways to pick the m elements for the two subsets, and there are m
k
ways to pick from those m elements the elements for B. There is no choice for the
elements of C as they
would be the remaining m − k elements selected.
This
n m
n m
means there are m
ways to form these two subsets (i.e. |S| = m
).
k
k
2. Another approach is to count
the number of ways to pick the k elements for B from
the n elements of A (i.e. kn ) and count the number of ways to select the m − k
n−k
elements for C from the remaining n − k elements from A − B (i.e. m−k
). This
n−k
n−k
would give a total of kn m−k
such subset formations (i.e. |S| = kn m−k
).
This argument shows that
n m
m
k
=
n n − k
k
m−k
.
The Pigeonhole Principle
• The Pigeonhole Principle: If |A| > |B|, then for every function f : A → B defined
on A, there exist two different elements of A that are mapped by f to the same
element of B.
• When you are trying to verify some statement using the Pigeonhole Principle, you
want to identify
• the set A,
• the set B where |B| < |A|, and
• the function f : A → B that is defined on all of A.
• The Generalized Pigeonhole Principle: If |A| > k · |B|, then for every function
f : A → B defined on A, there exist k + 1 different elements of A that are mapped
by f to the same element of B.
zyBooks Exercise 11.3.2 (a)
There are 121.4 million people in the United States who earn an annual income that is
at least $10,000 and less than $1,000,000. Annual income is rounded to the nearest
dollar. Show that there are 123 people who earn the same annual income in dollars.
zyBooks Exercise 11.3.2 (a) – Sample Response
Proof.
Let’s use the Generalized Pigeonhole Principle to resolve this statement. We’ll define
the set A to represent the 121.4 million people. So, |A| = 121, 400, 000. Also, let’s
define the set B to be the set of incomes. This means that
|B| = 1000000 − 10000 = 99000. If we map A to B by assigning each person to their
annual
thenm the Pigeonhole Principle says that there will be at least
l m income,
l
|A|
121400000
=
= 123 people assigned to the same income as stated.
|B|
99000
WRITING PROMPT TWO
1. How many paths are there from point (0,0) to point (50,50) on the two-dimensional plane
if each step along a path increments one coordinate and leaves the others unchanged and
there is an impassable obstacle at the points (10,11) and (20,19)? Provide a formula
representation of your result that includes binomial coefficients, and navigate the reader
through the development of your formula.
2. Using the Pigeonhole Principle, prove that in every set of 100 integers, there exist two whose
difference is a multiple of 37. Identify the function (including its domain and target) outlined
in either of our class resources while explaining how the principle is being applied.
Purchase answer to see full
attachment
