Mathematics for Business

1Part 3: Combinatorics
Combinatorics

• Basic Counting
• Permutation and Combination
• The Pigeonhole Principle
• Mathematical Induction and Binomial Theorem
• Recursive Formula
Combinatorics
1
Basic Counting
Addition Principles
• If one operation can be performed in m different ways and another operation can
be performed in n different ways, then the total number of ways in which either of
the two operations can be performed is (m + n).

• Subtraction principle:

• Including excluding principle:

• General addition principle:

• Eg. 1: A college offers 7 courses in the evening and 5 in the morning. Find the
number of ways a student can select exactly one course, either in the evening or in
the morning.
Multiple Principles
• If a certain thing can be done in m ways and another thing is done independently in
n ways, then the total number of ways in which both the things can be done are m
× n ways.
• If you have m ways of doing an event 1, n ways of doing event 2 and k ways of
doing event 3, the total number of doing things can be given as m × n × k.
• Eg. 1: A newly opened hotel offers food stuff in combos for `80. Along with the
combo food stuff, one can get one variety rice, chappathi and a fruit juice. The
different choices are as follows:
Variety Rice: lemon, tomato and curd
Rotti: Chappathi and poori
Juice: Lemon, apple and grape
Find the total number of choices and draw a tree diagram.
• Eg. 2: A pair of dice is thrown. How many possible outcomes are there?
• Eg. 3: A company offers 6 different posts in Group D category and 4 in Group C
category. Find the possible number of ways with the applicant if he wants to select
one post in Group D category and one in Group C category.
• Eg. 4: Aiswariya has 6 tops, 7 skirts and 5 caps from which to choose an outfit. In
how many ways can she select one top, one skirt and one cap?
Combinatorics
1Permutation and Combination
 Permutation and Combination
• Permutation: A permutation is an arrangement of all or part of a set of objects with
regard to the order of arrangement.
• Combination: A combination is a selection of all or part of a set of object without
regard to the order in which they are selected.

1) In how many ways can 5 men draw water from 5 taps if no tap can be used more than
once?
2) How many different signals can be made by 5 flags from 8 flags of different colors?
3) In how many ways can 5 questions be selected from 8 questions?
Properties
 Combinations of Different Things

The total number of combinations of ‘n’ different things taken

some or all of them at a time is 2n – 1.
1) Kabir has 8 friends. In how many ways can he invites one or more of them
to dinner?
2) From 8 boys and 5 girls, how many different selections can be made so as to
include at least one boy and one girl?
3) In an examination a candidate has to secure minimum marks in each of the 5
subjects to pass the examination. In how many cases can a student fail?
 Combinations of Things not All
different
The total number of combinations of (p + q + r + …) things of which ‘p’ things
are of one kind, ‘q’ of the second kind and ‘r’ of the third kind and so on, taken
any number of things at a time = [(p +1)(q +1)(r +1).........] -1
• Eg. 1: A box contains 12 black balls, 7 red balls and 6 blue balls. In how many ways
can one or more balls be selected?
• Eg. 2: Find the number of different choices that can be made from 5 apples, 4 bananas
and 3 mangoes, if at least one fruit is to be chosen.
• Eg. 3: A box contains 4 red, 3 white and 2 blue balls. Three balls are drawn at random.
Find out the number of ways of selecting the balls of different colors?
• Eg. 4: There are 8 English books, 6 Hindi books and 5 Bengali books in a library. In
how many ways can one or more than one book be selected?
• Eg. 5: A person has in his bag 15 coins of 10p each, 10 coins of 5p each, 5 coins of 2p
each and 8 coins of 1p each. In how many different ways can he contribute to a
charitable fund?
Rule of Things not all different

The number of permutations of n things taken all at a time, in

which ‘p’ of them are of one type, ‘q’ of them are of second type,
‘r’ of them are of third type, and rest are all different:

1) In how many ways can 12 different mangoes be divided into three groups
containing 3, 4 and 5 mangoes?
2) In how many ways can 9 different apples be distributed equally among 3
boys?
3) There are 6 books in Economics, 3 in Mathematics and 2 in Accountancy. In how
many ways can the books be arranged in a book-shelf so that books of the same subject
will always be together?
 Repeated Permutation

The number of permutations of n-things, taken ‘r’ at a time when

each thing can be repeated r-times is nr.
1) In how many ways can three prizes, one in recitation, one in music and one
in drawing, be given to 5 students, when each student is eligible for all the
prizes?
2) Find out the number of ways in which 6 rings of different types can be worn
in 3 fingers?
3) A gentlemen has 6 friends to invite. In how many ways can he sent invitation cards to
them if he has 3 servants to carry the cards?
 Circular Permutation

In the case of symmetric then:

1) In how many ways can 4 persons be seated at a circular table?

2) In how many ways can 8 flowers of different colors be strung together on a garland?
3) How many necklaces of 6 beads each can be made from 10 beads of different colors?
4) In how many ways can 7 boys be seated in a circular order?
5) In how many ways can 7 beads can be arranged to form a necklace?
6) In how many ways can 5 boys and 5 girls be seated at a round table so that no two
girls may be together?
7) A company has 10 software engineers and 6 civil engineers. In how many ways can
they be seated around a round table so that no two of the civil engineers will sit
together?
8) In how many ways can six different coloured stones be stringed together on a
necklace so that red and pink stones will not remain side by side?
 Examples
1) How many ways are there in selecting 5 members consisting 3 males and 2 females
from 6 males and 5 females?
2) A question paper has two parts A and B, each containing 10 questions. If a student
needs to choose 8 from Part A and 4 from Part B, in how many ways can he do that?
3) In how many ways can a cricket-eleven be chosen out of 15 players? If
(i) A particular player is always chosen
(ii) A particular player is never chosen
4) Tulu has 10 friends and he wants to invite 6 of them to a party. How many times will 3
particular friends never attend the party?
5) A board meeting of a company is organized in a room for 24 persons along the two
sides of a table with 12 chairs on each side. 6 persons want to sit on a particular side and
7 persons want to sit on the other side. In how many ways can they be seated?
6) A man has 20 acquaintances of which 12 are relatives. In how many ways he may
invite 13 guests out of them so that 9 would be relatives and one his best friend?
7) A candidate is required to answer 6 out of 10 questions which are divided into two
groups, each containing 5 questions, and he is not permitted to attempt more than 4 from
each group. In how many different ways can he make his selection?
 The Pigeonhole Principle
Theorem: If n + 1 objects are distributed into n boxes, then at least one box contains two
or more of the objects.
Theorem: Let ql, q2, . .. ,qn be positive integers. If ql + q2 + ... + qn - n + 1 objects are
distributed into n boxes, then either the first box contains at least q l objects, or the second
box contains at least q2 objects, ... , or the nth box contains at least qn objects.
• Eg. 1: A basket of fruit is being arranged out of apples, bananas, and oranges. What is
the smallest number of pieces of fruit that should be put in the basket to guarantee that
either there are at 'least eight apples or at least six bananas or at least nine oranges?
• Eg. 2: Two disks, one smaller than the other, are each divided into 200 congruent
sectors. In the larger disk, 100 of the sectors are chosen arbitrarily and painted red; the
other 100 sectors are painted blue. In the smaller disk, each sector is painted either red
or blue with no stipulation on the number of red and blue sectors. The small disk is then
placed on the larger disk so that their centers coincide. Show that it is possible to align
the two disks so that the number of sectors of the small disk whose color matches the
corresponding sector of the large disk is at least 100.
• Eg. 3: A child watches TV at least one hour each day for seven weeks but, because of
parental rules, never more than 11 hours in anyone week. Prove that there is some
period of consecutive days in which the child watches exactly 20 hours of TV. (It is
assumed that the child watches TV for a whole number of hours each day.)
 Mathematical Induction

• Step 1: Prove the statement for n = 1.

• Step 2: It is an inductive step, i.e. assuming the statement for n =
m and proving it for n = m + 1. Then by induction, we consider
that the statement is true for any real value of n.
• Binomial Theorem:
(x + y)n = nC0xn + nC1xn – 1y + … + nCrxn – ryr + … + nCny
 Examples
1) Every day a student walks from her home to school, which is located 10 blocks east
and 14 blocks north from home. She always takes a shortest walk of 24 blocks.
(a) How many different walks are possible?
(b) Suppose that four blocks east and five blocks north of her home lives her best friend,
whom she meets each day on her way to school. Now how many different walks are
possible?
(c) Suppose, in addition, that three blocks east and six blocks north of her friend's house
there is a park where the two girls stop each day to rest and play. Now how many
different walks are there?
(d) Stopping at a park to rest and play, the two students often get to school late. To avoid
the temptation of the park, our two students decide never to pass the intersection where
the park is. Now how many different walks are there?
2) A talk show host has just bought 10 new jokes. Each night he tells some of the jokes.
What is the largest number of nights on which you can tune in so that you never hear on
one night at least all the jokes you heard on one of the other nights? (Thus, for instance, it
is acceptable that you hear jokes 1, 2, and 3 on one night, jokes 3 and 4 on another, and
jokes 1, 2, and 4 on a third. It is not acceptable that you hear jokes 1 and 2 on one night
and joke 2 on another night.)
Combinatorics
1
Recursive Formula
 Fibonacci’s Sequence
A newly born pair of rabbits of opposite sexes is placed in an enclosure at the
beginning of a year. Beginning with the second month, the female gives birth to a
pair of rabbits of opposite sexes each month. Each new pair also gives birth to a
pair of rabbits each month starting with their second month.3 Determine the
number of pairs of rabbits in the enclosure after one year.
f0 = 0, f1 = 1, f2 = 1, f3 = 2, and f4 = 3 ...
fn = fn-l + fn-2,
fn = qn
qn – q n – 1 – q n – 2 = 0 → q 2 – q – 1 = 0
 Linear Homogenous Recursive
Relations
• Linear Recursive Relations

Multiple Solution:
• Homogenous: Double solution
• Constant coefficient
Multiple s solution
• Solutions of the forms:

• Characteristic equation
,
• General Solution:

• Inititial conditions
Non-homogeneous Equations
Towers of Hanoi puzzle. There are three pegs and n circular disks of increasing size
on one peg, with the largest disk on the bottom. These disks are to be transferred, one
at a time, onto another of the pegs, with the provision that at no time is one allowed
to place a larger disk on top of a smaller one. The problem is to determine the
number of moves necessary for the transfer.
hn = 2hn – 1 + 1 = 2(2hn – 2 + 1) + 1 = 4hn – 2 + 2 + 1
= … = 2n – 1 (h0 + 1) + 2n – 2 + 2n – 3 + … + 1 =
2n – 1 + 2n – 2 + 2n – 3 + … + 1 = 2n – 1

• , find solution
• , find solution
• , find solution
• , find solution
 Examples
1) Consider a two-sector model:
Yt = Ct + It Ct = 0.8Yt−1 + 100 It = 200
Find an expression for Yt when Y0 = 1700. Is this system stable or unstable?
2) Consider the supply and demand equations
QSt = 4Pt−1 − 10 QDt = −5Pt + 35
Assuming that the market is in equilibrium, find expressions for Pt and Qt when P = 6.
Is the system stable or unstable?
3) Consider the two-sector model:
Yt = Ct + It Ct = 0.7Yt−1 + 400 It = 0.1Yt−1 + 100
Given that Y0 = 3000, find an expression for Yt. Is this system stable or unstable?
 Examples
4) The Harrod–Domar model of the growth of an economy is based on three assumptions.
(i) Savings, St, in any time period are proportional to income, Yt, in that period, so that
St = aYt (a > 0)
(ii) Investment, It, in any time period is proportional to the change in income from the
previous period to the current period so that It = b(Yt − Yt−1) (b > 0)
(iii) Investment and savings are equal in any period so that It = St
Use these assumptions to show that and hence write down a formula for Yt in terms of Y0.
Comment on the stability of the system in the case when α = 0.1 and β = 1.4.
 Examples
5) A bank offers an individual a loan of $A at a rate of interest of r% compounded monthly.
The individual pays off the loan by monthly instalments of $a. If ut denotes outstanding
balance after t months, explain why

and show that

Hence write down an expression for the monthly repayment if the loan is paid off after N
months.