Chapter 3:- Counting methods

3.1. Sum and product rules

A. Addition principle (AP)
Assume that there are n1 different ways for the event E1 to occur

n2 different ways for the event E2 to occur

n3 different ways for the event E3 to occur

n4 different ways for the event E4 to occur

n5 different ways for the event E5 to occur

nk different ways for the event Ek to occur

If the ways in which these events occur are pair- wise disjoint, then the number of ways for at least one
of the events E1, E2, - - - or Ek to occur is given by n1+n2+ - - - +nk = ∑

An equivalent form of AP,

let A1, A2, - - -, Ak be any finite sets, if the given sets are pair- wise disjoint, then

|⋃ | | |, where | | stands for number of elements in (or

cardinality of ).

Example 1. If there are 14 boys and 12 girls in a class, then find the number of ways of selecting one
student as class representative.

Solution:- using sum rule, there are 14+12=26 ways of selecting one student (either a boy or girl) as
class representative.

Example 2. A student can choose a computer project from one of three lists. The three lists contain 23,
15, 19 possible projects, respectively. How many possible projects are three to choose from?

Solution:- The student can choose a project from 1st list in 23 ways

2nd list in 15 ways

3rd list in 19 ways

Example 3. One can reach city B from city A by bus, train, air or by foot. Suppose that there are 2
ways by bus, 3 ways by train, 4 ways by air and 5 ways by foot. What is the total no of
going from city A to city B?

1
Solution:- By (AP) there are a total of 2+3+4+5 =14 ways to go from city A to city B by bus or by train
or by air or by road.

Example 4. Let F is the event of choosing prime nos less than 10 and E is the event of choosing even
no less than 10. In how many ways can F or E occur?

Solution:- E = * +, F= * +.(E or F) = 4+4-1= 7 ways

B. Multiplication principle (MP)

Assume that an event E can be decomposed in to reordered event E1, E2, - - - , Er and that there are: n1
different ways for the event E1 to occur

n2 different ways for the event E2 to occur

n3 different ways for the event E3 to occur

nr different ways for the event Er to occur

Then the total number of ways for the event E to occur is given by

n1×n2× - - - ×nr = ∏
An equivalent form of (MP), Let A1, A2, - - -, Ak be any finite sets and

Let ∏ = A1×A2× - - - ×Ar = *( ) +

Then |∏ | = |A1|×|A2|× - - - ×|Ar|=∏ | |

Example 1. In how many ways can a college having 20 staff members elect dean, vice dean and
program manager assuming no person is elected more than one position?
Solution:- 20×19×18 = 6840.
Example 2. Suppose a college has 3 different calculus, 4 different algebra and 2 different optimization
courses. Then
a. The no of ways a student can choose one of each kind of the course is 3×4×2=24 ways
b. The no of ways a student can choose one of the courses is 3+4+2=9

Exercises
1. To reach city D from city A, one has to pass through city B and then through city C. If there are 2
ways to travel from A to B, 5 ways from B to C and 3 ways from c to D, what is the no of ways to
go from city A to city D.

2
Solution:- by (MP), A B≣C D. The no of ways is 2×5×3=30
2. If two die are thrown once, then find the no of ways in which we get even sum.

Solution:- Even, E1= *( )+, to get 2

E2 = *( )( )( )+ to get 4

E3 = *( )( )( )( )( )+ to get 6

E4 = *( )( )( )( )( )+ to get 8

E5 = *( )( )( )+ to get 10

E6 = *( )+ to get 12

Number of ways which we get even sum is | | = 18

Note:- since 1st die can fall (event E1) in 6 ways and the 2nd die can fall (event E2) in 6 ways.

Thus, there are 6×6=36 out comes when 2 dice are rolled.

Note: - If a natural number „n‟ has its prime factorization,

, where are distinct and the are positive integers, then the no of
positive divisors of is given by ∏ ( ).
Example 3. Find the number of positive divisors of 600.

Solution:- We know 600 = . Thus the no of positive divisors of 600 is 4×2×3=24

3.2. Permutations
Let * + be a given set of distinct objects.

For 0 , an r- permutation of is a way of arranging any of the objects of in a row.

When , an – permutation is simple called a permutation of

Example 1 Let * +. Then all the 2- permutations of are . They are 6 in no

An -permutation of can be formed in steps. There are n choices for the 1stposition, ( )
choices for the 2nd position ( ) choice for the 3rd position and so on until the position is filled
in ( ) ways.

Thus by (MP), we have ( )( ) ( )

Definition: - for an integer , factorial denoted by is defined

By

3
 ( )( ) ( )( )( )
( )( ) ( )( )
Note:- ( ) (check exercise)
( ) ( )

Example 2. The number of permutation of the letters in the word computer is 8! .

If only five of the letters are used. Then ( ) ( ) ( )

3. How many Pairs of dance partners can be selected from a group of 12 women and 20 men?
Solution:-The 1st women can be paired with any of 20 men
The 2nd women can be paired with any of the remaining 19 men
The 3rd women can be paired with any of the remaining and so on

This are ( )

Exercises
1. What is the value of if ( ) ( )

Solution:- ( ) ( )

( )
= 12( )
. Thus is the only answer.

2. How many three letter „‟words‟‟ can be formed from letters in the set * +

i. If repeated letters are allowed

ii. If repeated letters are not allowed

Solution:- Here is 4 and is 3. So i) the no of such words is 4.4.4= =64

ii) ( )=( )
= 24

3. How many “words” of 3 distinct letters can be formed from the letters of the word MAST?

Solution: - the no is =( )
= = 24

4. How many different 4 digit nos can be formed out of the digits and when
a. repetition is allowed
b. repetition is not allowed

Solution:- a. 6.6.6.6 = b. p(6.4) = ( )

4
Note:- If there are objects with of the 1st type, of the 2nd type, - - - , and of the type,
Where + - - - + = , then there are linear arrangements of the given -objects.

Example 1. Find the no of arrangement (permutation) can be made from.

a) 4black, 3red, 2white b) 2black, 2red, 2white
2. Find the no of arrangement (permutation) can be made out of the letters of the word
a) LAMP b) FOOD c) CALCULUS
3. a) Find the no of arrangement (permutation) that can be made out of the letters of the ward
”MATHEMATICS”. In how many of these permutations
b) Do all the vowels occur together
c) Do the word start with I
d) Begins with the two A
e) Begins with E and ends with C

Solution:- 1. a)

b)

2. a) ( ) ( )
b) there are 1F, 2‟O‟, 1D. Thus different ways.

C) there are 2C, 1A, 2L, 2U, 1S. Thus

3. a) The word „‟MATHEMATICS‟‟ consists of 11 letters of which 2 are As , 2 are Ms , 2 are

Ts , and the rest all different. Therefore the no of arrangements are

b) there are 2 are Ts , 2 are Ms , 1 is H, 1 is C, and 1 is S . Total no of arrangements are

( )( )

c) d) e)

Circular permutation:-
Definition: - The circular arrangement of out on distinct objects is ( ) ( )

Example: The arrangement of 5 students in a linear is ( ) ways. But in a circular is

( )
( ) ( )

( )
Example: for A, B, C on circular chair, we have ( ) ways of arrangements.

5
Restricted permutation
Permutation of object in places when particular objects will
( )
i. always occur is ( ) ( )
( )
ii. never occur is ( ) ( )

Example: In how many ways can we choose 11 out of 18 players?

i. If 2 papers are choose ii. If 2 players are not choose
Solution:- i. p (18-2, 11-2) = p (16, 9) ii. p(18-2,11) = p(16, 11)

3.3. Combinations
In how many ways can we choose two letters from A, B, C?
Solution:- 3 ways. i.e, AB, Bc and AC.

Definition:- combination is the no of ways of selecting r objects from a set of - objects without
( )
regarding to the order of selection. It is denoted by ( ) or ( ) and is ( ) =

( )
and is called the no of combination of objects taken at a time.

Example 1. How many different 5 cards can be selected out of 52 different cards

Solution:- ( )=( )

Exercises
1. How many different seven person committees can be formed each containing three women from an
available set of 20 women and 4 men an available set of 30 men?
Solution:- We have two tasks
Task1: choose 3 women from the set of 20 women
Task2: choose 4 men from the set of 30 men
Thus task1 can be performed in ( )=1140 ways and
Task2 can be performed in ( )=27,405 ways

By multiplication principle (MP), there are (1140) (27,405) =31,241,700 different committees.

2. A men is going to toss a coin eight times. In how many ways can get five heads and three fails.

Solution:- ( )= ( ) = 56.

6
Restricted combination
Combination of object taking at a time when particular will

i) always occur is ( )

ii) never occur is ( )

Example 1. How many committees of five people can be chosen from 20 men and 12 women
a. if exactly three men must be on each committee
b. if at least four women must be on each committee
Solution:- a. ( ) ( )= (1140) (66) =75,240

b. by addition principle (AP), ( ) ( ) ( ) ( )=495(20)+792=10,692.

Exercise. In how many ways can a committee of 5 be formed from a group of 11 people consisting of 4
teachers and 7 students if
i. there is no restriction in the selection
ii. The committee must include exactly 2 teachers
iii. The committee must include at least 3 teachers
iv. A particular teacher and particular student cannot be both in the committee.
Solution:- The no of ways is

i. ( )=( = 462
)

ii. ( ) ( ) = 210
iii. ( ) ( )+ ( ) ( ) = 91
iv. ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )

3.4. Binomial theorem

The sum of two distinct terms say “x+y” is called a binomial then ( ) for is binomial
expansion.
Binomial theorem: If x and y are variables and new, then

( ) =( ) +( ) ( ) ( )

= +
( ) ( ) ( ) ( )

Example 1. Expand ( ) and ( )

7
Solution:- ( )
( ) ( )

( ) = ( ) ( ) ( ) ( )
( )

= + .

Example 2. Find the fourth term in the expansion of ( )

Solution:- Since appears in the 2nd term Appears in the 3rd term

Appears in the 4th term

Then the variables of the fourth term are . And the coefficient must be = = 84
( ) ( )

Thus fourth term is =

( )

Example 3. Find coefficient of in the expansion of ( )

Solution:- ( ) ( ) ( ) 76,545

Note: - 1. ( ) ( )+( ) ( )

2. ( ) ( )+( ) ( ) ( ) ( )

Example 4. Using the Binomial theorem, expand( ) and find the constant term

Solution:- ( ) = ( ) ( ) ( ) ( ) ( )

Theorem (Multinomial theorem)

For positive interest the coefficient of in the expansion of (
) is , Where 0 and

Example 1. In the expansion of ( ) , find the coefficient of a) b) c)

Example 2. In the expansion of ( ) , find the coefficient of

a. b. c.

Solution:- 2. a. ( ) b. ( ) c. ( )

8
3.5 The pigeonhole principle
The pigeonhole principle states that of object (pigeon) are places in to boxes (pigeonholes),
then at least one box contain more than one object.

Examples
1. In any given set of 14 people at least two of them have their birth day during the same month.
2. Among any group of 8 people at least two were born on the same day of the week.
The generalized pigeonhole principle:-

If N object are placed into k boxes then there is at least one box continuing ⌈ ⌉ objects. i.e, the no of
object exceeds a multiple of the no of boxes.

Note:- ⌈ ⌉ is the smallest integer , such that .

Examples 1. Among 100 people there are at least ⌈ ⌉ who were born in the same month.

2. What is the minimum no of students in a discrete mathematics class to be sure that at least 6 will
receive the same grade if the possible grades are A, B, C.D and F?

Solution:- let N be the smallest integer than ⌈ ⌉ Thus N = 5.5+1= 26

3.6 Generating functions

Definition:- given a sequences * + with k 0, its generating function ( ) is defined by

( ) ∑

Example 1. For any ,

( ) ( ) ( ) ( ) ( ) . Thus ( ) is the generating function for

the sequence ( ), ( ), ( ), ( ) ( )

Example 2. a) For , From ( )( ),

we have, ( )( )

Thus is a generating function for the sequence 1, 1, 1, - - - ,1, 0, 0, 0, - - -.

Where the first terms are 1.

9
b. Extending the idea in part (a) we find that

where | | as from 2a and so is

generating function for the sequence

c. from

we can taking the derivative for both sides

( ) ( )

( )

( )
is the generating function for the sequence

d. multiply both sides by , we have

( )
is also the generating function for the sequence

e. continuing from part (d).

Example:- 3. ( ) = 1+2x+( ) +( ) + - - - is the generating function for the sequence

1, , , , - - -

Exercise:-1. Let f(x) = . Then find the sequence for

a. F(x) = f(x) - b. H(x) = f(x) +

2. Find the generating function for the sequence 0, 2, 6, 12, 20, 30, 42, - - -

Solution:- ( )

( )

( ) ( ) ( ) ( ) ( )
( )
=( ) ( )= ( )
+ ( )

= ( )
is generating function for the given sequence 0, 2, 6, 12, 20, 30, 42, - - -

3. Find the generating function for the sequence

. ( )

10