Discrete Mathematics: Counting
Discrete Mathematics: Counting
Discrete Mathematics: Counting
Mathematics
Counting
1
The Basics of counting
A counting problem:
Each user on a computer system has a
password, which is six to eight characters long,
where each characters is an uppercase letter or a
digit. Each password must contain at least one digit.
How many possible passwords are there?
2
Basic counting principles
The sum rule:
If a first task can be done in n1 ways and
a second task in n2 ways, and if these tasks n1 n2
cannot be done at the same time. then there
are n1+n2 ways to do either task.
n1 + n2 ways
Example 1
Suppose that either a member of the mathematics faculty or
a student who is a mathematics major is chosen as a
representative to a university committee. How many different
choices are there for this representative if there are 37
members of the mathematics faculty and 83 mathematics
majors and no one is both a faculty member and a student?
3
Sol: There are 37 ways to choose a member of the
mathematics faculty and there are 83 ways to choose a student
who is a mathematics major. Choosing a member of the
mathematics faculty is never the same as choosing a student
who is a mathematics major because no one is both a faculty
member and a student.
4
Example 2 A student can choose a computer
project from one of three lists. The three lists contain
23, 15 and 19 possible projects respectively.
How many possible projects are there to choose
from?
6
Example 4
How many different license plates are available if each
plate contains a sequence of 3 letters followed by 3
digits ?
Sol: □ □ □ □ □ □ →263 . 103
letter digit
. . :
am bn f(am)=? Can be b1 ~ bn, Total n
7
Example 5 How many one-to-one functions are there
from a set with m elements to one with n element?
(m n)
9
Example 7
In a version of Basic, the name of a variable
is a string of one or two alphanumeric characters, where
uppercase and lowercase letters are not distinguished.
Moreover, a variable name must begin with a letter and
must be different from the five strings of two characters
that are reserved for programming use. How many
different variable names are there in this version of
Basic?
Sol:
Let Vi be the number of variable names of length
i.
V1 =26
V2 =26 . 36 – 5
∴26 + 26 . 36 – 5 different names. 10
※ The Inclusion-Exclusion Principle
A B A B A B
A B
Sol:
12
The subtraction rule, or the principle of
inclusion–exclusion, can be generalized to find
the number of ways to do one of n different tasks
or, equivalently, to find the number of elements
in the union of n sets, whenever n is a positive
integer.
For 3 sets
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Example 10
A total of 1232 students have taken a course in Spanish, 879 have taken a
course in French, and 114 have taken a course in Russian. Further, 103 have
taken courses in both Spanish and French, 23 have taken courses in both
Spanish and Russian, and 14 have taken courses in both French and
Russian. If 2092 students have taken at least one of Spanish, French, and
Russian, how many students have taken a course in all three languages?
Sol:
|S ∩ F ∩ R| = 7.
13
The Principle of Inclusion–Exclusion
Let A1,A2, . . . , An be finite sets. Then
bit 1 bit 3
15
Exercise
How many bit strings of length ten both begin and end with a 1?
How many strings of five ASCII characters contain the character @ (“at” sign) at
least once? [Note: There are 128 different ASCII characters.
How many strings of three decimal digits
16
Ex 40. How many subsets of a set with 100 elements
have more than one element ?
Sol: 100 100 100 100
(1) ... 2100 101
100 99 98 2
( 2) a1 , a2 ,..., a100 Thm. 4 of §4.3
Proof
Suppose that none of the k boxes contains more than
one object. Then the total number of objects would
be at most k. This is a contradiction.
20
Example 5: During a month with 30 days a baseball
team plays at least 1 game a day, but no more
than 45 games. Show that there must be a period
of some number of consecutive days during which the
team must play exactly 14 games.
day 1 2 3 4 5 ... 15 30
# of game 3 2 1 2 sum 45
Number of games for some time =14
21
Sol:
Let aj be the number of games played on or before the
jth day of the month. (1 j 30)
23
Theorem 3. Every sequence of n2+1 distinct real
numbers contains a subsequence of length n+1 that is
either strictly increasing or strictly decreasing.
24
Exercise
Show that among any group of five (not necessarily consecutive)
integers, there are two with the same remainder when divided by 4.
a) Show that if five integers are selected from the first eight
positive integers, there must be a pair of these integers
with a sum equal to 9.
b) Is the conclusion in part (a) true if four integers are selected
rather than five?
a)How many numbers must be selected from the set { I , 2, 3, 4, 5, 6}
to guarantee that at least one pair of these numbers add up to 7?
b)There are 38 different time periods during which classes at a
university can be scheduled. If there are 677 different classes, how
many different rooms will be needed?
25
Permutations and Combinations
27
Def. An r-combination of elements of a set is an
unordered selection of r elements from the set.
28
Example 10. We see that C(4,2)=6, since the
2-combinations of {a,b,c,d} are the six subsets
{a,b}, {a,c}, {a,d}, {b,c}, {b,d} and {c,d}
pf : From Thm 2.
n! n!
C ( n, r ) C ( n, n r )
r!(n r )! (n r )!(n (n r ))!
29
Example 6. How many ways are there to select 5
players from a 10-member tennis team to make a trip to
a match at another school ?
Sol: C(10,5)=252
30
Exercise
How many permutations of {a , b, e, d, e , t, g} end with a?
How many bit strings of length 10 contain
¨ exactly four 1s?
¨ at most four 1s?
¨ at least four 1s?
¨ an equal number of 0s and 1s?
a)A group contains n men and n women. How many ways are there to arrange these
people in a row if the men and women alternate?
b)How many permutations of the letters ABCDEFG contain
a) the string BCD? b) the string CFGA?
c) the strings BA and GF? d) the strings ABC and DE?
e) the strings ABC and CDE? f) the strings CBA and BED?
a)Suppose that a department contains 1 0 men and 1 5 women. How many ways
are there to form a committee with six members if it must have the same number of
men and women?
b)Suppose that a department contains 1 0 men and 1 5 women. How many ways
are there to form a committee with six members if it must have more women than
men?
31
Binomial Coefficients
Example 1.
( x y ) 3 ( x y )( x y )( x y ) ? x 3 ? x 2 y ? x y 2 y 3
To obtain a term of the form xy2 ,
a y must be chosen from two of the brackets, and an x
must be chosen from one of the
brackets
3
(Note : x and y in the same bracket cannot be multiplied) 2 ) xy 2
The coefficient = (
( x yare
∴There ) 3 different
( 30 ) x 3 (ways
3
1 ) x y
2 to get
( 3
2 ) xxy
y 22
( 3
3 ) y 3
∴
Theorem 1. (The Binomial Theorem)
Let x,y be variables, and let n be a positive integer, then
n
( x y ) n ( 0n ) x n (1n ) x n 1 y ... ( nn 1 ) xy n 1 ( nn ) y n ( nj ) x n j y j
j 0
32
Example 2. What is the coefficient of x12y13 in
the expansion of (2 x 3 y ) ?
25
Sol: (2 x 3 y ) 25 (2 x ( 3 y )) 25
∴ 25
(13 ) 212 (3)13
k 0 1
( n
k 0
) ( n
) ( n
) ... ( n
n ) 2 n
pf : By Thm 1, let x = y = 1
(1 1) n ( 0n ) (1n ) ( n2 ) ... ( nn )
n
pf : by Thm 1. (11)n = 0
33
Theorem 2. (Pascal’s identity)
Let n and k be positive integers with n k
Then
n 1 n n
k k 1 k
PASCAL’s triangle
( 00 ) 1
(10 ) (11 ) 1 1
2
1 2 1
2 2
( ) ( ) ( )
0 1 2 1 3 3 1
( 30 ) (13 ) ( 32 ) ( 33 ) 1 4 6 4 1
…
…
( 34 )
34
n 1 n n
pf : ①(algebraic proof) k k 1 k
n 1 (n 1)!
k
k!( n 1 k )!
n n n! n!
k 1 k
(k 1)!(n k 1)! k!(n k )!
k n! (n k 1) n! (n 1) n!
k!(n k 1)! k!(n k 1)! k!( n k 1)!
②(combinatorial proof):
n 1 n 1 n 1
‧ = ‧ + ‧ n 1 n 1 n 1
k k 1 0 k 1
k k 0 k 1
1 35
Theorem 3. (Vandermode’s Identity)
m, n, r , 0 r m, n
r
C (m n, r ) C (m, r k ) C (n, k )
k 0
pf :
m n
mn mn mn
C(m+n, r) = = ↓ ↓ + ↓ ↓ +...+ ↓ ↓
r, 0 r1, 0 0, r
r
m n m n ... m n
r 0 r 1 1 0 r
r
C (m, r k ) C (n, k )
k 0
36
37
Generalized Permutations and Combinations
Permutations with Repetition
Example 1 How many strings of length r can be formed
from the English alphabet?
Sol. 26r
Thm 1. The number of r-permutations of a set of n objects
with repetition allowed is n r.
38
Thm 2. There are C(r+n1, r) r-combinations from
a set with n elements when repetition of elements is
allowed.
pf : (Each r-combination of a set with n elements when
repetition is allowed can be represented by a list of n − 1 bars
and r stars. The n − 1 bars are used to mark off n different
cells, with the ith cell containing a star for each time the ith
element of the set occurs in the combination)
11 2
By theorem 2 11 solutions
40
※ since x1, x2, x3 are nonnegative integers, x1 1, x2 2, x3 3,
Original equation is x1 + x2 + x3 = 11
can be changed to (x1 1) + (x22) + (x33) = 11123 = 5
At this point y1 + y2 + y3 = 5
Where y1 = x1 1, y2 = x2 2, y3 = x3 3 and y1, y52,2y3 N
∴5 stars to be inserted between 2 bars 5
solutions
(Note : case y1 = 1, y2 = 3, y3 = 1 is equal to x1 =2, x2 =5, x3 =4)
∴ A total of 5 5 2 2 2 2 combinations
41
42
※ Permutations with indistinguishable objects
Example 5. How many different strings can be made
by reordering the letters of the word SUCCESS ?
Sol:
There are 3 Ss, 2 Cs, 1 U and 1 E,
The three Ss can be placed among the seven positions in C(7,3)
different ways leaving four positions free.
Then the two Cs can be placed in C(4, 2) ways, leaving two free
positions.
Then the two Cs can be placed in C(2, 1) ways, leaving two free
positions.
Hence E can be placed in C(1, 1) way
Consequently, from the product rule, the number of different
strings that can be made is
C(7, 3)C(4, 2)C(2, 1)C(1, 1) = 420 43
Thm 3. The number of different permutations of n objects,
where type 1 : n1 ways
n!
type 2 : n2 ways is
n1!n2! nk !
type k : nk ways
pf :
n n n1 n n1 n2 n n1 n2 nk 1 n!
n n
1 2 n 3 nk n1!n2 ! nk !
44
Exercise
Solve the following
a) How many ways are there to deal hands of five cards to six players
from a standard 52-card deck?
b) How many ways are there to distribute n distinguishable objects
into k distinguishable boxes so that ni objects are placed in box i?
How many ways are there to choose a dozen apples from a bushel
containing 20 indistinguishable Delicious apples, 20 indistinguishable
Macintosh apples, and 20 indistinguishable Granny Smith apples, if at
least three of each kind must be chosen?
How many ways are there to pack eight identical DVDs into five
indistinguishable boxes so that each box contains at least one DVD?
How many ways are there to distribute six indistinguishable objects into
four indistinguishable boxes so that each of the boxes contains at least
one object?
45
Distributing objects into Boxes
Distinguishable Objects and distinguishable boxes
Example 8. How many ways are there to distribute
hands of 5 cards to each of four players from the
standard deck of 52 cards?
52
Sol: player 1 : 5
ways
47
player 2 : from the remaining 5 5
52! 47! 42! 37! 52!
52 47 42 37
5 5 5 5 5! 47! 5! 42! 5! 37! 5! 32! 5! 5! 5! 5! 32!
Note: the above question is equivalent to 52 cards in 5 different box
method,
that is box 1 for player 1,
box 2 for player 2
box 3 for player 3
box 4 for player 4 46
while box 5 is for the cards left.
Exercise
How many ways can n books be placed on k
distinguishable shelves
a) if the books are indistinguishable copies of
the same title?
b) if no two books are the same, and the
positions of the books on the shelves matter?
47
Thm 4. The number of ways to distribute n distinguishable
objects into k distinguishable boxes so that ni
objects are placed into box i, i=1, 2, …, k, equals
n!
n1! n2 ! nk ! (the same as Thm 3)