CMPS 2120 Lecture Notes - Basic Combinatorics
Combinatorics is the study of countable discrete structures.
In the following rules, A and B are finite sets.
#1. A problem that asks you to count elements from A or from B can be
solved by finding the cardinality of A union B.
*--------------The Sum Rule-------------------*
|A u B|, where A n B = {}, is |A| + |B| (no overlap)
Example. Count the blue cars or green cars in the parking lot.
A={7 blue cars} B={8 green cars} |A u B| = 15
Principle of Inclusion-Exclusion.
|A u B|, where A n B != {} is |A| + |B| - |A n B| (overlap)
Example. Count the even numbers in two sets.
A={2,4,6,8} B={6,8,10,12,14}
|A| = 4 |B| = 5 |A n B| = 2
A u B = {2,4,6,8,10,12,14}
|A u B| = 4 + 5 - 2 = 7
Example. There are 20 students. How many own blue cars or green cars?
A={7 own blue cars} B={10 own green cars} A n B = {3 own both}
|A u B| = 7 + 10 - 3 = 14.
If |U| = 20 (20 students total), how many do not own blue or green cars?
20 - 14 = 6.
#2. A problem that asks you to count all the ways that set elements can be
combined is looking for the cardinality of a Cartesian product.
*---------The Product Rule----------*
|A x B x C x ... | = |A| * |B| * |C| * ...
Example: Count the number of ways you can create a 4-digit password, with
digits 1-9.
Let A = {1,2,...9}.
The cardinality of this cross-product is |A| x |A| x |A| x |A| = 9^4.
Example:
Count the number of functions from A -> B, where |A| = m and |B| = n.
To be a function, each of the m elements in A must be mapped to one of the
n elements in B. For, A={1,2) and B={1,2,3}, the combinations of all
possible mappings for (a,b) are:
A B A B A B A B A B A B A B A B A B
1-1 1-1 1-1 1-2 1-2 1-2 1-3 1-3 1-3
2-1 2-2 2 3 2-1 2-2 2-3 2-1 2-2 2-3
2 3 2 3 3 1 2 1 2
3 1
For m=2 and n=3, there are nine (3^2). The general rule is n^m possible
functions from A -> B.
Example: Count the number of ways you can create a 4-digit passwords
beginning with 1, and using any digit 0-9 after that.
1*10*10*10
- - - -
This variation on the product rule "fixes" one of the choices in the
Cartesian product. All other choices are computed in the usual fashion.
*---------The Rule of Falling Powers----------*
Any problem that asks you to count the ways that set elements can be
"arranged" follows the rule of falling powers (a variation of the product
rule). If you are arranging the elements in A in m ways, where elements in
A cannot be repeated and |A| = n, the rule of falling powers is:
_
n^m = n(n-1)(n-2)... (n-m+1) (read "the falling powers of n to the m")
Example:
Count the number of one-to-one functions from A -> B, where |A|=m and |B|=n
and m <= n. To be one-to-one, each of the m elements in A must be mapped to
a single element in B and vice versa. Once an element from n is used, it
cannot be reused. This is a falling power. For m=5 and n=7,
_
7^5 = 7 * 6 * 5 * 4 * 3.
Thus, there are n(n-1)(n-2)...(n-m+1) one-to-one functions.
Example: Count the number of ways you can create a 4-digit password, with
digits 0-9 and with no digit used twice.
_
This is the falling powers of 10^4 = 10*9*8*7
EXAMPLES OF THE ABOVE RULES.
1. There are 18 mathematics majors and 325 computer
science majors at a college (and no double majors).
a) How many ways are there to pick two students, so that one is a
mathematics major and the other is a computer science major?
18 * 325 = 5850
b) How many ways are there to pick one representative who is either
a mathematics major or a computer science major?
18 + 325 = 343
2. A multiple-choice test contains ten questions. There
are four possible answers for each question.
a) How many ways can a student answer the questions on the
test if every question is answered?
4 4 4 4 4 4 4 4 4 4 = 4^10
- - - - - - - - - -
b) How many ways can a student answer the questions on the test
if the student can leave answers blank?
5^10
3. A particular brand of shirt comes in 12 colors, has a
male version and a female version, and comes in three
sizes for each sex. How many different types of this
shirt are made?
12 * 2 * 3 = 72
4. There are six different airlines that fly from New York
to Denver and seven that fly from Denver to San Francisco.
How many different possibilities are there for a trip from New
York to San Francisco via Denver, when an airline is picked for
the flight to Denver and an airline is picked for the continuation
flight to San Francisco?
6 * 7
5. There are four major auto routes from Boston to Detroit and six from
Detroit to Los Angeles. How many major auto routes are there from Boston
to Los Angeles via Detroit?
4 * 6 = 24
6. How many different three-letter initials can people have?
26*26*26 = 26^3 <= 26 uppercase letters
7. How many different three-letter initials with none of the letters
repeated can people have?
26*25*24
8. How many different three-letter initials are there that begin with an A?
1 * 26 * 26 = 676
9. How many unique bit strings are there of length eight?
2 2 2 2 2 2 2 2 = 2^8
- - - - - - - -
10. How many bit strings of length ten begin and end with a 1?
1 * 2^8 * 1
11. How many unique bit strings are there of length six or less?
(including the empty string)
2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 2^7 - 1 = 127
12. How many bit strings with length not exceeding n, where n is a positive
integer, consist entirely of 1s? (including the empty string)
l= 0 1 2 3 ... n
1+1+1+1+...+1 = n+1
13. How many bit strings of length n, where n is a positive integer, start and
end with 1s? (note: this means exactly length n, not <= n)
For n=1, there is one bit string of length n: '1'.
1*2*2*2*2*2*...*2*1 = 2^(n-2), for n>=2
14. How many strings are there of lowercase letters of length four or less?
(include the empty string)
1 + 26 + 26^2 + 26^3 + 26^4
15. How many lowercase letter strings of length four have the letter z in them?
The easiest way to compute this is to take the number of all possible
strings and subtract off the number of strings that don't have an x in them:
26*26*26*26 - 25*25*25*25
16. How many strings of five ASCII characters contain the character @ at least
once? (Note: There are 128 different ASCII characters.)
The easiest why to compute this is to subtract off the strings that do not
contain @ from all possible strings:
128^5 - 128^4 = 1,321,368,961
17. How many positive integers less than or equal to 1000
a) are divisible by 7?
floor(1000/7) = 142
b) are divisible by both 7 and 11?
floor(1000/77) = 12
c) are divisible by 7 but not by 11?
Include integers divisible by 7: 142
Exclude integers divisible by 7 and 11: 12
142 - 12 = 130
d) are divisible by either 7 or 11 ? (assume this is NOT xor)
Include integers divisible by 7: 142
Include integers divisible by 11: 90
Exclude divisable by both: 12
142 + 90 - 12 = 220
e) are divisible by exactly one of 7 and 11? (this is XOR)
Include integers divisible by 7: 142
Include integers divisible by 11: 90
Exclude divisable by both TWICE: 12
142 + 90 - 12 - 12 = 208
f) are divisible by neither 7 nor 11 ?
#Total integers: 1000
#Divisable by 7 or 11: 220
1000 - 220 = 780
g) have distinct digits? (note: assume integers cannot begin with zero)
1 digit: 9
2 digits: 9*9 (fix the leftmost digit first with 1-9 choices)
3 digits: 9*9*8
4 digits: 1
9 + 81 + 648 + 1 = 739
h) have distinct digits and are odd?
1 digit: 5
2 digits: 8*5 (fix the rightmost digit first with 5 choices)
3 digits: 8*8*5 (fix the rightmost digit then the leftmost digit)
4 digits: 1
5 + 40 + 320 + 1 = 366
18. How many positive integers are there between 100 and 999 inclusive?
There are 900 numbers between 100 and 999, inclusive.
Of these numbers, how many
a) are divisible by 7?
floor(999 / 7) = 142
floor(99 / 7) = 14
142 - 14 = 128
b) are odd?
floor(999 / 2) = 499 <= the even ones
floor(99 / 2) = 49 <= the even ones
499 - 49 = 450 even ones, thus
= 450
Or:
There are 900 numbers between 100 and 999, and you start with an even
number and end with an odd, thus half are even and half are odd. Thus,450.
c) have the same three decimal digits?
000 is not an option, thus 9
d) are not divisible by 4?
The numbers that are divisable by 4:
floor(999 / 4) = 249
floor(99 / 4) = 24
thus, 249 - 24 = 225 are divisable by 4
and 900 - 225 = 675 are not.
e) are divisible by 3 or 4?
INCLUDE
Numbers divisable by 4:
= 225
INCLUDE
Numbers divisable by 3:
floor(999 / 3) = 333
floor(99 / 3) = 33
= 300
EXCLUDE
floor(999 / 12) = 83
floor(99 / 12) = 8
= 75
225 + 300 - 75 = 450
f) are not divisible by either 3 or 4?
divisable by 4 = 225
divisable by 3 = 300
divisable by both = 75
900 - 225 - 300 + 75 = 450
g) are divisible by 3 but not by 4?
INCLUDE
divisable by 3 = 300
EXCLUDE
divisable by both = 75
300 - 75 = 225
h) are divisible by 3 and 4?
INCLUDE
divisable by both = 75
21. How many strings of three decimal digits
a) do not contain the same digit three times?
10*10*10 = 1000 = total number of strings with three decimal digts
10 = number of string that contain the same digit
1000 - 10 = 990
b) begin with an odd digit?
5 * 10 * 10 = 500
c) have exactly two digits that are 4s?
1*1*9 +
1*9*1 +
9*1*1 = 30 (note: there are only 9 other choices since 4 is taken)
23. A committee is formed containing either the governor or one of the
two senators of each of the 50 states. How many ways are there to form
this committee?
3^50
31. How many one-to-one functions are there from a set
with five elements to sets with the following number of elements?
a) 4
b) 5
c) 6
d) 7
32. How many functions are there from the set
{1,2, ..., n}, where n is a positive integer, to the set
{O,l}?
33. How many functions are there from the set
{l, 2, ..., n}, where n is a positive integer, to the set
{O,l}
a) that are one-to-one?
b) that assign 0 to both 1 and n?
c) that assign 1 to exactly one of the positive integers
less than n?
36. How many subsets of a set with 100 elements have
more than one element?
37. A palindrome is a string whose reversal is identical
to the string. How many bit strings of length n are
palindromes?
38. In how many ways can a photographer at a wedding arrange 6 people
in a row from a group of 10 people, where the bride and the groom
are among these 10 people, if
a) the bride must be in the picture?
6 ways to fix the bride:
1*9*8*7*6*5
9*1*8*7*6*5
9*8*1*7*6*5
9*8*7*1*6*5
9*8*7*6*1*5
9*8*7*6*5*1 =
6(9*8*7*6*5)
b) both the bride and the groom must be in the picture?
For each of the 6 ways to fix the bride are 5 ways to fix the groom:
= 6*5(1*1*9*8*7*6*5)
c) exactly one of the bride and the groom is in the picture?
There are six ways to fix either the bride or the groom. The remaining
5 seats can be filled out of 8 choices. Thus,
6(2*8*7*6*5*4)