COUNTING

PRINCIPLE
RJA
Topics to Be Discussed:

■ Counting Rules
■ Mathematical Functions in Combinatorics
■ Permutation
■ Combination
■ Pigeonhole Principle
■ Tree Diagram
BASIC COUNTING PRINCIPLES:

■ There are two basic counting principles used throughout this chapter. The first one
involves addition and the second one multiplication.
Elaboration:

■ Sum Rule: If no two events can occur at the same time, then one of the events can
occur in:
– n1 + n2 + n3 +・ ・ ・ ways.

■ Product Rule: If the events occur one after the other, then all the events can occur in
the order indicated in:
– n ・ n ・ n ・ . . . ways.
1 2 3
Application:

■ EXAMPLE 5.1 Suppose a college has 3 different history courses, 4 different

literature courses, and 2 different sociology courses.

– The number m of ways a student can choose one of each kind of courses is:
■ m = 3(4)(2) = 24

– The number n of ways a student can choose just one of the courses is:
■ n=3+4+2=9
Rewriting the Concept in terms of Sets:

■ Sum Rule Principle: Suppose A and B are disjoint sets. Then

n(A ∪ B) = n(A) + n(B)

■ Product Rule Principle: Let A × B be the Cartesian product of sets A and B. Then
n(A × B) = n(A) ・ n(B)
 MATHEMATICAL FUNCTIONS:
■ We discuss two important mathematical functions frequently used in combinatorics.
– Factorial Function
– The product of the positive integers from 1 to n inclusive is denoted by n!, read “n
factorial.” Namely:
– n! = 1 ・ 2 ・ 3 ・ . . . ・ (n−2)(n−1)n = n(n−1)(n−2) ・ . . . ・ 3 ・ 2 ・ 1

– Binomial Coefficients
 Binomial Coefficients and Pascal’s
Triangle

The coefficients of the successive powers of a + b can be arranged in a triangular array of numbers,
called Pascal’s triangle, as pictured in Fig. 5-1. The numbers in Pascal’s triangle have the following
interesting properties:
(i) The first and last number in each row is 1.
(ii) Every other number can be obtained by adding the two numbers appearing above it.
PERMUTATIONS

■ Any arrangement of a set of n objects in a given order is called a permutation of the

object (taken all at a time).
■ Any arrangement of any r ≤ n of these objects in a given order is called an “r-
permutation” or “a permutation of the n objects taken r at a time.”
■ Consider, for example, the set of letters A, B, C, D.
Continuation

■ (i) BDCA, DCBA, and ACDB are permutations of the four letters (taken all at a time).
■ (ii) BAD, ACB, DBC are permutations of the four letters taken three at a time.
■ (iii) AD, BC, CA are permutations of the four letters taken two at a time.
Theorem in Permutation:

■ The number of permutations of n objects taken r at a time will be denoted by P(n, r)

(other texts may use nPr, Pn,r , or (n)r ).
– P(n, r) = n(n − 1)(n − 2) ・ ・ ・ (n − r + 1) = n!/(n − r)!

– We emphasize that there are r factors in n(n − 1)(n − 2) ・ ・ ・ (n − r + 1).

 Application
■ EXAMPLE 5.4 Find the number m of permutations of six objects, say, A, B, C, D, E, F, taken
three at a time.

– In other words, find the number of “three-letter words” using only the given six letters
without repetition.
– Let us represent the general three-letter word by the following three positions:
——, ——, ——
– The first letter can be chosen in 6 ways; following this the second letter can be chosen
in 5 ways; and, finally, the third letter can be chosen in 4 ways.

– By the Product Rule there are m = 6 ・ 5 ・ 4 = 120 possible three-letter words without
repetition from the six letters. Namely, there are 120 permutations of 6 objects taken 3
at a time.
Permutations with Repetitions:

■ Frequently we want to know the number of permutations of a multiset, that is, a set
of objects some of which are alike. We will let
■ EXAMPLE 5.5 Find the number m of seven-letter words that can be formed using the
letters of the word “BENZENE.”
– We seek the number of permutations of 7 objects of which 3 are alike (the
three E’s), and 2 are alike (the two N’s).
Ordered Samples:

■ Many problems are concerned with choosing an element from a set S, say, with n
elements. When we choose one element after another, say, r times, we call the
choice an ordered sample of size r. We consider two cases.
– (1) Sampling with replacement
– (2) Sampling without replacement
Sampling with replacement

■ Here the element is replaced in the set S before the next element is chosen. Thus,
each time there are n ways to choose an element (repetitions are allowed). The
Product rule tells us that the number of such samples is:

n ・ n ・ n ・ ・ ・ n ・ n(r factors) = n^r

Sampling without replacement

■ Here the element is not replaced in the set S before the next element is chosen.
Thus, there is no repetition in the ordered sample. Such a sample is simply an r-
permutation. Thus the number of such samples is:
■ EXAMPLE 5.6 Three cards are chosen one after the other from a 52-card deck. Find
the number m of ways this can be done: (a) with replacement; (b) without
replacement.

– (a) Each card can be chosen in 52 ways. Thus m = 52(52)(52) = 140 608.

– Here there is no replacement. Thus the first card can be chosen in 52 ways,
the second in 51 ways, and the third in 50 ways. Therefore:
m = P(52, 3) = 52(51)(50) = 132 600
COMBINATIONS

■ Let S be a set with n elements. A combination of these n elements taken r at a time

is any selection of r of the elements where order does not count. Such a selection is
called an r-combination; it is simply a subset of S with r elements. The number of
such combinations will be denoted by
■ EXAMPLE 5.7 Find the number of combinations of 4 objects, A, B, C, D, taken 3 at a
time
– Each combination of three objects determines 3! = 6 permutations of the
objects as follows:

– Thus the number of combinations multiplied by 3! gives us the number of

permutations; that is,
Combination Theorem:
■ EXAMPLE 5.8 A farmer buys 3 cows, 2 pigs, and 4 hens from a man who has 6 cows,
5 pigs, and 8 hens. Find the number m of choices that the farmer has.
THE PIGEONHOLE PRINCIPLE

■ Many results in combinational theory come from the following almost obvious
statement.

■ Pigeonhole Principle: “If n pigeonholes are occupied by n + 1 or more pigeons, then

at least one pigeonhole is occupied by more than one pigeon.”
EXAMPLE 5.9

■ (a) Suppose a department contains 13 professors, then two of the professors

(pigeons) were born in the same month (pigeonholes).

■ Generalized Pigeonhole Principle: If n pigeonholes are occupied by kn + 1 or more

pigeons, where k is a positive integer, then at least one pigeonhole is occupied by k
+ 1 or more pigeons.
■ EXAMPLE 5.10 Find the minimum number of students in a class to be sure that
three of them are born in the same month.
THE INCLUSION–EXCLUSION PRINCIPLE

n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

– In other words, to find the number n(A∪B) of elements in the union of A and B,
we add n(A) and n(B) and then we subtract n(A ∩ B); that is, we “include” n(A)
and n(B), and we “exclude” n(A ∩ B).
■ EXAMPLE 5.11 Find the number of mathematics students at a college taking at least
one of the languages French, German, and Russian, given the following data:
– 65 study French, 20 study French and German,
– 45 study German, 25 study French and Russian, 8 study all three languages.
– 42 study Russian, 15 study German and Russian,
TREE DIAGRAMS

■ A tree diagram is a device used to enumerate all the possible outcomes of a

sequence of events where each event can occur in a finite number of ways.
■ EXAMPLE 5.12
■ (a) Find the product set A × B × C, where A = {l, 2}, B = {a, b, c}, C = {x, y}.
■ (b) Mark and Erik are to play a tennis tournament. The first person to win two games
in a row or who wins a total of three games wins the tournament. Find the number of
ways the tournament can occur.