Mathematical Foundations of Computing

Unit 6

COUNTING

The Basics of Counting

 Combinatorics: the study of arrangements of objects

 Enumeration: the counting of objects with certain

properties
 Enumerate the different mobile numbers possible in Jordan
 The allowable password on a computer
 The different orders in which runners in a race can reach

 Two basic counting principles:

1. Product rule
2. Sum rule
 The Product Rule

 If there are n1 ways to do task 1, and n2 ways

to do task 2
 Then there are n1n2 ways to do both tasks in sequence

 This applies when doing the “procedure” is made up of

separate tasks
 We must make one choice AND a second choice

Product Rule Example (i)

 There are 18 CE majors and 325 ISE majors. How

many ways are there to pick one CE major and
one ISE major?

 Total is 18 * 325 = 5850

 Product Rule Example (ii)
How many different bit strings of length seven are
there?

Solution:
 Each of the seven bits can be chosen in two ways,
because each bit is either 0 or 1.
 Therefore, the product rule shows that there are a total
of 27 = 128 different bit strings of length seven.

Product Rule Example (iii)

 How many strings of 4 decimal digits that do not
contain the same digit twice?
 We want to choose a digit, then another that is not the
same, then another…
 First digit: 10 possibilities
 Second digit: 9 possibilities (all but first digit)
 Third digit: 8 possibilities
 Fourth digit: 7 possibilities
 Total = 10*9*8*7 = 5040
 How many strings of 4 decimal digits that end
with an odd digit?
 First three digits have 10 possibilities
 Last digit has 5 possibilities
 Total = 10*10*10*5 = 5000
 Product Rule Example (iv)
 How many different license plates are available if
each plate contains a sequence of 3 uppercase
English letters followed by 3 decimal digits (and
non sequences of letters are prohibited)?

 There are 26 choices for each letter and 10 choices for

each digit. So, there are
26∙26∙26∙10∙10∙10 = 17,576,000 possible license plates

Product Rule Summary

 Suppose that a procedure is carried out by

performing the tasks T1, T2, …, Tm in
sequence. If each task Ti, i=1, 2, …, n can
be done in ni ways, regardless of how the
previous tasks were done, then there are
n1 x n2 x … x nm ways to carry out the
procedure
 The Sum Rule

 If a task can be done either in one of n1 ways or

in one of n2 ways, where none of the set of n1
ways is the same as any of the set of n2 ways,
then there are n1 + n2 ways to do the task

Sum Rule Example

 Suppose either a member of faculty or a student

in the department is chosen as a representative
to a university committee. How many different
choices are there for this representative if there
are 8 members in faculty and 200 students?

 There are 8+200=208 ways to pick this representative

 Sum Rule Example

The Subtraction (Inclusion-Exclusion) Principle

 When counting the possibilities, we can’t include

a given outcome more than once!

 |A1U A2| = |A1| + |A2| - |A1∩ A2|

 Let A1 have 5 elements, A2 have 3 elements, and 1 element be

in both A1 and A2
 Total in the union is 5 + 3 - 1 = 7, not 8

 This technique is called principle of inclusion-

exclusion (or subtraction) principle
 Inclusion-Exclusion Example
 How may bit strings of length eight start with 1 or
end with 00?

 Count bit strings that start with 1

 Rest of bits can be anything: 27 = 128 (the first bit can be chosen in
one way)
 This is |A1|
 Count bit strings that end with 00
 Rest of bits can be anything: 26 = 64
 This is |A2|
 Count bit strings that both start with 1 and end with 00
 Rest of the bits can be anything: 25 = 32
 This is |A1∩ A2|

 Use formula |A1U A2| = |A1| + |A2| - |A1∩ A2|

 Total is 128 + 64 – 32 = 160

Bit String Possibilities_Example

 How many bit strings of length 10 contain either 5
consecutive 0s or 5 consecutive 1s?

 Consider 5 consecutive 0s first

 Sum rule: the 5 consecutive 0’s can start at position 1, 2,
3, 4, 5, or 6
 Starting at position 1: Remaining 5 bits can be anything: 25 = 32
 Starting at position 2
 First bit must be a 1: Otherwise, we are including possibilities from the
previous case!
 Remaining bits can be anything: 24 = 16
 Bit String Possibilities (Cont’d)
 Starting at position 3
 Second bit must be a 1 (same reason as above)
 First bit and last 3 bits can be anything: 24
 Starting at positions 4 and 5 and 6
 Same as starting at positions 2 or 3: 24 each
 Total = 32 + 16 + 16 + 16+ 16 +16 = 112
 The 5 consecutive 1’s follow the same pattern, and have
112 possibilities
 There are two cases counted twice (that we thus need to
exclude): 0000011111 and 1111100000
 Total = 112 + 112 – 2 = 222

Tree Diagrams
 Counting problems can be solved using tree diagrams.
 A tree consists of:
 a root
 a number of branches leaving the root
 Possible additional branches leaving the endpoints of other
branches.

 To use trees in counting, we:

 use a branch to represent each possible choice
 represent the possible outcomes by the leaves, which are the
endpoints of branches not having other branches starting at
them.
 Example (i)
 How many bit strings of length 4 do not have two
consecutive 1s?
 In some cases, we can use tree diagrams for counting

8 without two consecutive 1s

Example (ii)
Suppose that T- shirts come in five different sizes:
S, M, L, XL, and XXL.
 S, M, and L comes in four colors, white, red,
green, and black,
 XL comes only in red, green, and black,
 XXL comes only in green and black.
 How many different shirts does a shop have to
stock to have at least one of each available size and
color of the T- shirt?
Solution

From the above tree diagram, the shop needs to stock

17 different T-shirt

The Pigeonhole Principle

 Suppose a flock of pigeons fly into a set of
pigeonholes to rest
 If there are more pigeons than pigeonholes,
then there must be at least 1 pigeonhole that
has more than one pigeon in it
 If k+1 or more objects are placed into k
boxes, then there is at least one box
containing two or more of the objects
 Example: 13 pigeons and 12 pigeonholes:
 Pigeonhole Principle Examples

 In a group of 367 people, there must be two

people with the same birthday
 As there are 366 possible birthdays (considering February 29th
every four years)

 In a group of 27 English words, at least two

words must start with the same letter
 As there are only 26 letters in the English alphabet

EXAMPLE

How many students must be in a class to guarantee

that at least two students receive the same score on
the final exam, if the exam is graded on a scale from
0 to 100 points?

Answer: 102
 Generalized Pigeonhole Principle

 If N objects are placed into K boxes, then

𝑵
there is at least one box containing
𝑲
objects

Examples (i)
 Among 100 people, there are at least
100 / 12 = 9 born on the same month

 How many students (min. number of students)

must be in a class to ensure that 6 students get
the same grade (one of A, B, C, D, or F)?
 The “boxes” are the grades. Thus, k = 5
 Thus, we set N / 5 = 6
 Lowest possible value for N is 26
 Examples (ii)
 A bowl contains 10 red and 10 yellow balls. How
many balls must be selected to ensure getting 3
balls of the same color?
 Solution 1: consider the “worst” case
 Consider 2 balls of each color
 You can’t take another ball without hitting 3, Thus, the answer is 5

 Solution 2: Via generalized pigeonhole principle

 How many balls are required if there are 2 colors, and one color
must have 3 balls?
 How many pigeons are required if there are 2 pigeon holes (Boxes),
and one must have 3 pigeons (N/K)?
 number of boxes: k = 2, We want N/k = 3
 What is the minimum N?
 N=5

Permutations & Combinations

 Both are ways to count the possibilities

 The difference between them is whether order

matters or not

 Example:
 In how many ways we can select 3 students from a
group of 5 students?
 In how many different ways they stand in line for
picture?
 Permutations
 A permutation is an ordered arrangement of the
elements of some set S
 Let S = {a, b, c}
 c, b, a is a permutation of S
 b, c, a is a different permutation of S
 The ordered arrangement a, c is a 2-permutation of S (of two
elements only of S)

 The number of r-permutations of a set with n elements

is denoted by P(n, r)
 E.g, the 2-permutations of S = {1, 2, 3} are:
1,2; 1,3; 2,1; 2,3; 3,1; and 3,2. Hence, P (3, 2) = 6

Permutations
 The number of r-permutations of a set with n
elements is denoted by P (n, r)

n!
P(n, r ) 
(n  r )!
 Factorial Review
 n! is defined as the product of all positive
integers from 1 to n
 Examples:
1! = 1*1 = 1
2! = 2*1 = 2
3! = 3*2*1 = 6
4! = 4*3*2*1 = 24

n! = n * (n-1) * (n-2) ...* 3 * 2 * 1

 Logically, n! can also be expressed n*(n-1)!
 Special cases: n=1, using n! = n*(n-1)!
1! = 1*1 = 1*0!
which simplifies to 0! =1

Permutation Special Cases

 P(n,0)=1 whenever n is a nonnegative integer as
there is exactly one way to order zero element.
 P(n, r) = n! / (n-r)!
P(n,0) = n!/(n-0)!=1

 P(n,n) = n! / (n-r)!
= n! / (n-n)!
= n! / 0!
= n! / 1
= n!
 Permutations: Examples (i) & (ii)
In how many ways can we select In how many ways can we arrange
3 students from a group of 5 to all 5 of these students in a line?
stand in line?
There are 5 ways to select the 1st
There are 5 ways to select the 1st student
student
4 for 2nd
4 ways to select the 2nd
3 for 3rd
3 ways to select the 3rd
2 for 4th
By the product rule, there are
5 · 4 · 3 = 60 ways to select 3 1 for 5th
students out of a group of 5 Consequently, there are
which is equivalent to 5 · 4 · 3 · 2 · 1 = 120 ways

P(5, 3) = 5! / (5 - 3)! = 60 which is equivalent to

P(5, 5) = 5! / (5 - 5)! = 120

r-permutations example (iii)

 How many ways are there for 5 people in this class which
has 27 students to give presentations? Note that the order
they go in does matter in this example!

 P(27,5) = 27*26*25*24*23 = 9,687,600

 Permutations Example (iv)
 How many permutations of {a, b, c, d, e, f, g}
end with a?
 Note that the set has 7 elements

 The last character must be a

 The rest can be in any order

 Thus, we want a 6-permutation on the set

{b, c, d, e, f, g}

 P(6,6) = 6! = 720

Permutations Example (v)

 How many permutations of the letters ABCDEFGH
contain string ABC (as a block)?

 As ABC must occur as a block, we can find the answer

by finding the permutations of 6 objects:
 the block ABC and the individual letters, D,E,F,G, and H.

 As these 6 objects must occur in any order, there are

6!=720 permutations of the letters ABCDEFGH in which
ABC occurs in a block
 Combinations
 Combinations are used to count unordered selections of
objects
 This is in contrast to permutations, where the order is
important (we count ABC as different from BCA)
 In combinations, the order is not issue. When we need to
select from {A, B, C}, ABC and BCA are the same
combination
 An r-combination of elements of a set is an unordered
selection of r elements from the set.
 Thus, an r-combination is simply a subset of the set with
r elements
 Denoted by C (n,r).
n
 Note that C (n,r) is also denoted by   and is called a
binomial coefficient r

r-combination (Cont’d)

 The number of r-combinations of a set with n elements,

where n is a nonnegative integer and r is an integer
with 0≤r≤n equals

n!
C (n, r ) 
r!(n  r )!
 Combinations Examples (i)
 How many bit strings of length 10 contain:
 Exactly four 1’s?
 Find the positions of the four 1’s
 Does the order of these positions matter? No!
 Eg. positions 2, 3, 5, 7 is the same as positions 7, 5, 3, 2
 Thus, the answer is C(10,4) = 210

 At most four 1’s?

 There can be 0, 1, 2, 3, or 4 occurrences of 1
 Thus, the answer is:
 C(10,0) + C(10,1) + C(10,2) + C(10,3) + C(10,4)
= 1+10+45+120+210
= 386

Combinations Examples (ii)

 How many bit strings of length 10 contain:
 At least four 1’s?
 There can be 4, 5, 6, 7, 8, 9, or 10 occurrences of 1
 Thus, the answer is:
 C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) +
C(10,9) + C(10,10)
= 210+252+210+120+45+10+1
= 848
 Alternative answer: subtract from 210 the number of
strings with 0, 1, 2, or 3 occurrences of 1

 An equal number of 1’s and 0’s?

 Thus, there must be five 0’s and five 1’s
 Find the positions of the five 1’s
 Thus, the answer is C(10,5) = 252
 Combinations Examples (iii)
Suppose that there are 9 professors in the math department and 11
in the CS department.

How many ways are there to select a committee to develop a discrete

mathematics course if the committee is to consist of 3 professors
from the math department and 4 from the CS department?

Solution

The answer is the product of the number of 3-combinations of a set

with 9 elements and the number of 4-combinations of a set with 11
elements

C(9, 3) · C(11, 4) = [9! / (3! (9 - 3)!)] · [11! / (4! (11 - 4)!)]

= 84 · 330 = 27,720

Binomial Coefficients
 The number of r-combinations form a set with n
elements is often denoted by    C (n, r )
n
r

 Also called as a binomial coefficient as these

numbers occur as coefficients in the expansion of
powers of binomial expressions such as (a + b)n

 A binomial expression is simply the sum of two

terms, such as (x + y)
Properties of Binomial coefficients

n n
      1
0 n
 The Binomial Theorem
 The Binomial Theorem gives the coefficients of the expansion
of powers of binomial expressions.

 The binomial theorem: Let x and y be variables, and let n be a

nonnegative integer.

n
n
( x  y ) n     x n  j y j
j 0  j 

n n n  n  n 1  n  n

   x n    x n 1 y    x n  2 y 2      xy    y
0 1  2  n  1 n

Example (i)
What is the expansion of (x + y)4?

4
 4  4  4  4  4  4
( x  y ) 4     x 4 j y j    x 4    x 3 y    x 2 y 2    xy 3    y 4
j 0  j  0 1  2  3  4

= x4 + 4x3y + 6x2y2 + 4xy3 + y4

Examples (ii)

Examples (iii)
 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 (i)

 Pascal's Identity, together with the initial conditions

for all integers n, can be used to recursively define binomial coefficients.

 This recursive definition is useful in the computation of binomial

coefficients because only addition, and not multiplication, of integers is
needed to use this recursive definition.

 Pascal's Identity is the basis for a geometric arrangement of the

binomial coefficients in a triangle as shown in the figure on the next
slide

 The nth row in the triangle consists of the binomial coefficients:

 This triangle is known as Pascal's triangle.

 Pascal's Identity shows that when two adjacent binomial coefficients in

this triangle are added, the binomial coefficient in the next row
between these two coefficients is produced
Pascal Triangle (ii)