M.Sc_.-Mathematics-PAPER-V-DISCRETE-MATHEMATICS-SUBJECT-CODE-PSMTPAMT105-Inside-Pages-munotes

Page 1

1
DIVISIBILITY THEORY O) INTE*ERS AND
ARITHMETIC )UNCTIONS
Unit Structure :
1.0 Objectives
1.1 Introduction
1.2 Division Algorithm
1.3 The Greatest Common divisor
1.4 Euclidean Algorithm
1.5 Solving Linear Diophantine equations
1.6 Cardano ’s Method
1.7 Congruence Relations
1.8 Quadratic Residues
1.9 Arithmetic Functions
1.10 Let us sum up
1.11 Solved numerical
1.12 Unit End Exercise
1.0 ObMectives
After reading this chapter, you will know about.
x Division Algorithm.
x The Greatest common divisor of two integers.
x The Euclidean Algorithm as a rep etition of division algorithm.
x Solution to linear Diophantine equations.
x The concept of Congruence.
x Cardano ’s method to solve a general cubic equation.
x Quadratic Residues.
x Number - Theoretic functions like M ᠰbius inversion formula, The greatest
integer function etc. 1Unit 1
munotes.in

Page 2

2DISCRETE MATHEMATICS1.1 INTRODUCTION
The theory of numbers starts with many properties of the intege rs and particularly
with the positive integers 1, 2, 3…. when it comes to a questio n of checking
whether a given integer b divides another integer a, we look for some integer q
such that a bq a n d c o n c l u d e t h a t t h e d i v i s i o n i s p o s s i b l e w i t h
bqa, one
important theorem, explaining the division process in the integ ers is the division
algorithm, roughly it states that an integer a can be divided b y another integer b in
such a way that the remainder has a magnitude smaller than b. Let us prove this
theorem.
1.2 Theorem : Division Algorithm
Given integers a and b, with b ! 0, there exist unique integers q and r satisfying ,0 d d
ab qr rb. The integers q and r are called, quotient and remainder in the
division of a by b.
Proof :
We show that the set ^`is an integer, 0 t
Sa x b x a x bis a non-empty set.
For this, it is enough to exhibit a value of x, making a – xb nonnegative.
Since the integer 1t
b, we have t
ab a a n d t h e r e f o r e 0 t t
aa b a a b a a. Hence, for ,
xa a x b S. By
applying the well-ordering principle, the set S contains a smallest integer, call it r.
By definition of S, there exists an integer q satisfying ,0 d
raq b r, we argue
that r v. If t
rb then 10 t
aq ba q bb r b 1
aq b S.
But 1
aq b r b r, violating the fact that r is the smallest member of S.
Hence r b. We shall show that such q and r are unique. Suppose a can be
represented by two expressions, say aq brq br
cc , where 0, 0rb r b
c d d t h e n 1 rr b q q rrb q q
cc c c c . Also 0 d
br a n d t h e r e f o r e 00br rb br rb
cc ,
equivalently, rrb
c. Thus 0 bq q b q q
cc d. Now qq
c is a
nonnegative integer, therefore the only possibility is that 0, 0 qq qq qq
cc c , this gives that rr
c . munotes.in

Page 3

3Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsTo understand the Division Algorithm, when 0
b, take 7
b. Then for the
choices of a 1, – 2, 61 and – 59, we get the expressions
1 0 ( – 1) + 1
– 2 1 ( – 7) + 5
61 ( – 8) (– 7) + 5
– 59 9 ( – 7) + 4.
As one of the application of the division algorithm, we show th at the square of
any odd integer is of the form 8 k + 1.
By division algorithm, any integer is described as one of the f our forms 4 k, 4k +
1, 4k + 2, 4 k + 3. In this form only those integers of the form 4 k + 1 and 4 k + 3
are odd. 2 241 8 2 1 8 1kk k k
c
and similarly 2 243 8 2 3 1 1 81kk k k
c .
For example, the square of the odd integer 7 is 274 9 8 . 6 1
.
1.3 The *reatest Common Divisor
When the remainder r 0 in the division algorithm, such cases are of special
significance.
Definition of divisibility:
An integer b is divisible by an integer 0z
a, symbolically _ab, if there exists
some integer c such that b ac. We write _ab to indicate that b is not divisible
by a.
For example, – 12 is divisible by 4, since –12 4 ( –3). However, 10 is not
divisible by 7 for there is no integer c, which makes the statement 10 7 c true.
When a divides b, we say that b is a multiple of a whenever _ab, a also divides
– b. Therefore to find all divisers of a given integer, it is suff icient to obtain the
positive divisers and then adjoin them with the corresponding n egative integers.
Let us state the consequences of the above definition. munotes.in

Page 4

4DISCRETE MATHEMATICSTheorem : For integers a, b, c the following hold :
1) a 0, 1 a, a a.
2) a 1 if and only if 1r
a.
3) If a b and c d then ac bd.
4) IF a b and b c, then a c.
5) if a b and b a then r
ab.
6) If a b and b 0, then d
ab.
7) If a b and a c, then a (bx + cy) for any choice of int egers x and y.
Proof :
We shall prove only (6) and (7).
If a b then there exists on integer C. such that b ac also 00zz
bc.
Taking absolute values,
ba ca c. Since c 0, it follows that 1t
c. t d
ba ca ab. To prove (7), ab and
ac b a rand c as for
some integers r and s. Then ()
bx cy arx asy a rx sy, for any choice of
integers x and y. This shows that
ab x c y.
Definition :
If a and b are integers, then an integer d is said to be a comm on divisor of a and b
if both d a and d b. Since 1 is a divisor of every integer, 1 is a common divisor
of a and b, hence the set of positive divisions for a and b is not empty when, at
least one of a or b is different from zero, there are only a fi nite number of positive
common divisions among these, the re is largest one, called the greatest common
divisor of a and b.
Definition :
Let a and b be given integers, with atleast one of them differe nt from zero. The
greatest common divisor of a and b is denoted by gcd (a, b), it is the positive
integer d satisfying
1) d a and d b.
2) If c a and c b, then c d. munotes.in

Page 5

5Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsFor example the positive divisors of - 12 are 1, 2, 3, 4, 6, 12 , while the positive
divisors of 30 are 1,2,3,5,6,10,15,30 hence, the positive comm on divisors of - 12
and 30 are 1,2,3,6 since 6 is the largest, it follows that gcd (-12, 30) 6. In the
same way, one can show that gc d (-5, 5) 5, gcd (8, 17) 1 an d gcd (-8, -36) 4.
The next theorem shows that gcd(a,b) ax + by for some integer s x and y, say
gcd (-8, -36) 4 (-8) 4 + (-36) (-1).
Theorem :
Given integers a and b, not both of which are zero, there exist integers x and y
such that gcd(a, b) ax + by.
Proof :
Consider the set S of all positive linear combinations of a and b. ^`0 , , a r e i n t e g e r sXX X !
Sa u b a u b u. Notice that S is not empty. For
example, if a 0, then 0
aa u bwill lie in S, if we choose u 1 or u -1,
according to as a is positive or negative. By virtue of the wel l-ordering principle,
s must contain a smallest element d. ? There exist integers x and y, for which d ax + by. We claim that d gcd(a, b)
using the division algorithm, one can find q and r such that a qd + r, d
ord.
Then r can be written in the form ()
(1 ) ( )

r a qd a q ax by
a qx b qy
rS and r d, a contradiction to a ssumption that d is the smalles t member of
S. therefore 0
ra q dor d a. By similar reasoning
db dis a common
divisor of both a and b.
If ca and cb then d
ca x b y cd c c d d so that d is greater than
every positive common divisor of a and b. gcd( , )
da b.
It may happen that 1 and -1 are the only common divisors of a g iven pair of
integers a and b gcd , 1
ab. For example, gcd 2,5 gcd 9,16 1
.
Definition :
Two integers a and b, not both zero, are said to be relatively prime, whenever
gcd(a, b) 1.
munotes.in

Page 6

6DISCRETE MATHEMATICSTheorem :
Let a and b be integers, not both zero. Then a and b are rela tively prime if and
only if there exist integers x and y such that 1
ax by.
Proof :
Let a, b be relatively prime numbers, then gcd( , ) 1
ab. There exist integers x
and y such that 1 ax + by. Conversely, if 1
ax byfor some choice of integers
x and y and gcd( , )
da b d a x b y or d 1, 01 .t
dd
Corollary : If gcd(a,b) d, then gcd , 1§· ¨¸©¹
ab
dd.
Proof :
If gcd ,
da bthese exist integers x and y such that
da xb y, after
dividing throughout by d, we get 1§·§· ¨¸¨¸©¹©¹
abxf ydd. §·¨¸©¹
a
d and §·
¨¸©¹b
d a r e
relatively prime gcd , 1§·? ¨¸©¹
ab
dd
For example, gcd(-12, 30) 6 and gcd(-126, 306) gcd(-2,5) 1.
Theorem : (Euclid’s lemma) :
If a bc, with gcd(a, b) 1, then ac.
Proof : gcd , 1
ab There exist integers x and y such that 1
ax by multiplying
throughout by C gives 1. ( )
cc a x b y C a c x b c y. Since
aa cand
ab c a a c x b c y ac.
If a and b are not relatively prime, then the conclusion may fa il to hold. For
example, 129.8 but 12 doesn’t divide 8 or 9.
Theorem :
Let a, b be integers, not both zero. For a positive integer d, gcd ( , )
da b if and
only if munotes.in

Page 7

7Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions1) da and db.
2) Whenever ca and cb then cd.
Proof :
Suppose that gcd ,
da bda and
db dis expressible as d ax + by for
some integers x and y. Thus, if ca and cb then co x b y or cd. conversely,
let d be any positive integer such that da and db and wheneve r ca and cb then t
cd d c dis the greatest common divisor of both a and b.
1.4 Euclidean Algorithm
A more efficient process, involving repeated application of the division algorithm
is known as the Euclidean Algorithm. The Euclidean algorithm ca n be described
as following :
Let a and b be two integers, whose gcd is to be calculated. Sin ce gcd , gcd( , )
ab a b. Assume that t!
abo. The first step is to apply the
division algorithm to a and b to get 11 , d
aq br orb. Were 1 ro or 110, 0 !
rr b aand gcd(a,b) b. when 1z
ro, divide b by r 1 find integers q 2
and r 2 such that 22 2 2 1 , d
bq r r or r.
If 2
ro t h e n s t o p , o t h e r w i s e p r o c e e d a s b e f o r e t o o b t a i n r 3 and q 3 s u c h t h a t 13 2 3 3 2 , d
rq rr o rr. This process continues until some zero remainder
appears, say at (n + 1)th step, r n-1 is divided by r n.
The result is the following system :
11 1
21 2 2 1
13 2 3 3 2
21 1
11,
,
,
,

nn n nn n
nn naq br orb
bq r r or r
rq r r o rr
rq r r o r r
rq r o
We claim that r n, the last nonzero remainde r in these steps, is equal to gcd( a,b). munotes.in

Page 8

8DISCRETE MATHEMATICSLemma : If a qb + r, then gcd , gcd( , ) ab br
.
Proof : Let . da
and db( )da q b
or dr. Thus d is a common
divisor of both b and r on the other hand, if c is an arbitrary common divisor of b
and r, then
cq b r c a. This make c a common divisor of a and d
bc d. Therefore d gcd(b,r) using this lemma, for the given system .
11 gcd , gcd , gcd ,
gcd ,

nn
nnab br r r
ro r
Example
To calculate gcd (12378, 3054)
Write 12378 4 3054 162, u

3054 18 162 +138,
162 1 138 + 24,
138 5 24 +18,
24 1 18 + 6,
18 3 6 + 0u
u
u
u
u

6 g c d ( 1 2 3 7 8 ,3 0 5 4 )

To express 6 as a linear combination of 12378 and 3054, followi ng is the
procedure.
62 41 8?

24 (138 5 24)
62 41 3 8
6( 1 6 2 1 3 8 ) 1 3 8 u
u

61 6 2 71 3 8
61 6 2 7 ( 3 0 5 41 81 6 2 )
132 162 7 3054
132 (12378 4 3054) 7 3054
132 12378 ( 535) 3054 u u
u u
u u
u
u u
munotes.in

Page 9

9Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsThus, we get 6g c d ( 1 2 3 7 8 , 3 0 5 4 )1 2 3 7 8 3 0 5 4 xy
where x 132 and y -
535.
An important consequence of the Euclidean Algorithm is the foll owing theorem.
Theorem :
If k ᦫ 0, then gcd (ka, kb) k gcd (a,b).
Proof :
Let gcd ( , )dk a k b
There exist integers x and y such that ( dk a xk b y k a x b y
kd suppose that dk
for some integer
. We shall claim that gcd , ab
.
Since gcd( , ) dk a k b d k a
and ddk b ak§·¨¸©¹
and dbk§·
¨¸©¹. Hence a
and b
. Assume that some integer ca and cb ca x b y
. Therefore
cd. Applying the theorem on gcd, we obtain gcd ,dabk

gcd( , ) dR a b

gcd( , ) gcd( , )ka kb k a b

There is a concept parallel to that of the gcd of two integers, known as their least
common multiple.
Definition :
An integer C is said to be a common multiple of two non zero integers a and b
whenever a/c and b/c. 0 is a common multiple of a and b. The products -(ab) and
ab are both common multiples of a and b. By well-ordering princip le, the set of
positive common multiples of a and b must contain a smallest in teger, we call it
the least common multiple of and b. here we define it formally.
Definition :
The least common multiple of two nonzero integers a and b, den oted by
lcm(a,b) , is the positive integer m satisfying
1) a/m and b/m,
2) If a/c and b/c, with c>0, then mcd.
For example, the positive common multiples of the integers - 12 and 30 are 60,
120, 180, …., hence lcm(-12, 30) = 60. munotes.in

Page 10

10DISCRETE MATHEMATICSNote : G i v e n n o n z e r o i n t e g e r s a a n d b , lcm(a,b) always exists and (,)lcm a b ab d
.
To connect gcd and lcm of integers a and b, the following is a theorem.
Theorem :
For positive integers a and b, gcd( , ) , )ab l c m ab a bu
.
Proof :
Let d gcd(a,b) write a dr, b ds for integers r and s. If m ab d
, then ma sr b m is a common multiple of a and b. let c be any positive integer
that is common multiple of a and b, say ca ub X
. As we know, there exist
integers x and y satisfying da xb y
. In consequence, ca x b y cc d a cxyma b a b b a§· §· ¨¸ ¨¸©¹ ©¹
xu yX
mc m c d
. By definition (,) ml c m a b
, that is (,)gcd( , )ab ablcm a bda b
gcd , ( , ) ab l c mab a b u
.
Corollary : G i v e n p o s i t i v e i n t e g e r s a a n d b , .. . ( , )lcm a b a b
i f a n y o n l y i f .. . ( , ) 1gcd a b
.
For example, we know that gcd(3054, 12378) 6
3054 12378(3054,12378) 6,300,4026lcmu
.
We shall now take up the study of Diophantine equations. Any eq uation in one or
more unknown, which is to be solved in the integers, is taken a s the Diophantine
equation. The simplest type of Diophantine equation that we wil l consider is the
linear Diophantine equation in two unknownsax by c
, where ,,abc a r e
given integers and ,ab n o t b o t h z e r o . A s o l u t i o n o f t h i s e q u a t i o n i s a p a i r o f
integers 00,xy such that00ax by c
. A given linear Diophantine equation can
have a number of solutions, for example 361 8xy
has many solutions.

34 611 8
36 6 6 1 8
31 0 6 2 1 8uu
u u
u u
munotes.in

Page 11

11Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsWhereas the equation21 01 7xy
has no solution so, we shall discuss the
circumstances under which a solution is possible to such a line ar Diophantine
equation.
1.5 Solving Linear Diophantine ETuations
The Diophantine equation ax by c
has a solution if and only if d/c, where gcd ( , )da b
.
Theorem :
The linear Diophantine equation ax by c
has a solution if and only if dc,
where gcd ( , )da b
. If 00,xyis any particular solution of this equation then all
other solutions are given by 0bxx td§· ¨¸©¹
, 0ayy td§· ¨¸©¹
for varying integers t.
Proof : Let gcd( , )da b
There exists integers r and s for which a dr and b
ds. If a solution of ax by c
exists, so that 00ax by c
for suitable 0xand 0y, then 00 0 0 ca x b y d r x d s y
00()dr x s y
dc. Conversely
assume that dc, say c dt
T h e r e e x i s t s i n t e g e r s 0x, 0ysatisfying 00 da x b y
, when this relation is multiplied by t, we get. 00 0 0 (( ) cd t a x b yta t x b t y
t h e D i o p h a n t i n e e q u a t i o n ax by c
has 0 xt x
and 0 yt y
as particular solution.
Let us now suppose that a solution 0x, 0y of the given equation is known if 1x, 1yis any other solution, then 11
00ax by c ax by
, which is equivalent to 11
00 ax x by y
.
By theorem, there exist relatively prime integers r and s such that a dr, b ds
substituting these values in the last equation and canceling th e common factor d,
we find that 11
00 rx x sy y
1
0 rs y y
with gcd( , ) 1rs
. ? By
Euclid’s lemma, 1
0ry y . 1
0yyr t
for some integer t.
1
0 xxs t
munotes.in

Page 12

12DISCRETE MATHEMATICS 1
00bxxs t x td§· ¨¸©¹
.
1
00t ayyry td§· ¨¸©¹
.
It can be seen that these values satisfy the Diophantine equat ion, 11
00baax by a x t b y tddªº ªº§· §· ¨¸ ¨¸«» «»©¹ ©¹¬¼ ¬¼

00ab abax by tdd
co tc§· ¨¸©¹

Thus there are an infinite number of solutions of the given equ ation, one for each
value of t.
Example :
C o n s i d e r t h e l i n e a r D i o p h a n t i n e e q u a t i o n s 172 20 1000xy
.
T o f i n d gcd 172, 20
. Apply Euclid’s Algorithm,
172 8 20 12,
20 1 12 8,
12 1 8 4,
8240 u
u
u
u

gcd 172, 20 4
. Since 41 0 0 0
a solution to this equation exists. To
obtain 4 as a linear combination of 172 and 20,
41 28

12 (20 12)
21 2 2 0
2( 1 7 2 8 2 0 ) 2 0
21 7 2 ( 1 7 )2 0
u
u
u u

munotes.in

Page 13

13Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsBy multiplying throughout by 250, we obtain
>@ 1000 250 4 250 2 172 ( 17) 20
500 172 ( 4250) 20 u u u u
u u

500x
and y - 4250 is a solution. All other solutions are given by
20500 500 54xt t§· ¨¸©¹

1724250 4250 434yt t§· ¨¸©¹
form integer t.
If we put t - 99, we get a positive solution x 5, y 7.
Corollary :
If gcd(a, b) 1 and if 0x, 0yis a particular solution of the linear Diophantine
equation ax by c
then all solutions are given by 0xx b t
, 0 yy a t
for
integral values of t.
For example, the equation 5x + 22y 18 has 008, 1xy
as one solution,
from the corollary, a complete solution is given by 82 2 , 15xt yt
for
arbitrary t.
In the following section, we shall see the cardanos method for finding roots of
cubic polynomials.
1. Cardanos Method
Given a cubic polynomial in unknown x, 320 xa xb x c
, eliminate the
square term by using the substitution 3axt
32
0333aaata tb t c§·§·§· ¨¸¨¸¨¸©¹©¹©¹
. munotes.in

Page 14

14DISCRETE MATHEMATICSTherefore 23 2
32 2 233 033 3 3 3 3aa a a t a a btt t a t b t cªº §· §· §· §· «» ¨¸ ¨¸ ¨¸ ¨¸©¹ ©¹ ©¹ ©¹ «»¬¼
3 22 2 3
32
23
3323039 2 7 3 9 3
29032 7at a t a a t a abta t b t c
aa a btb t c§· ¨¸©¹
§·§ · ¨¸¨ ¸©¹© ¹

Put 2
3apb
and 329
27a abqc§· ¨¸©¹
.
Then 30 t pt q
is the reduced form of the given cubic equation. Now, let tPX
and rewrite the above equation as 30 pq PX PX
or 3330 pq PX P XP X
. Set 30 p PX
, then the above equation
becomes 33q PX
. And we are left with these two equations.
33q PX

33 32 7p PX

Since these equations are the product and sum of 3P and 3X therefore these exist
a quadratic equation 3
2027pt qt
w i t h r o o t s 3P and 3X. Therefore this
equation has solutions as following. 23
3
23
324 2 7
24 2 7qq p
qq pPX
XX§· § ·§· ¨¸ ¨ ¸¨¸©¹©¹ © ¹
§· §·§· ¨¸ ¨¸¨¸©¹©¹ ©¹

We must find the cube roots of these equations to solve for 3P and 3X.
If 2327 4 0qp
then the roots will complex number. If 2327 4 0qpt
then
the roots are real numbers. Let us solve certain cubic polynomi als by this method. munotes.in

Page 15

15Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions F o r e x a m p l e , c o n s i d e r t h e c u b i c e q u a t i o n 320.75 0.1875 0.015625 0xx x

this equation has a form 320 xq xb x c
therefore substitute ,3axt
to
eliminate the 2x term we get a new equation 30, tp t q
where 2329,3 27a a abpb qc§· ¨¸©¹
.
H e r e 20.750.1878 03p

32( 0 . 7 5 ) 9 ( 0 . 7 5 )( 0 . 1 8 7 5 )0.015625 027q

So, the new equation is 300 , to t
that is 30t
. Since 2327 4 0 0qp t
,
therefore all roots ar e real and equal to 3a because 033aaxt x t
. ? T h e r o o t s a r e 1230.25, 0.25, 0.25xxx
. Let us consider another
example, 3261 1 6 0xx x
, after putting 3axt
, to eliminate 2x term,
we get new equation 23
3 290, ,3 27a a qbt pt q p b q c§· ¨¸©¹
.
Here 2611 13p
,
326 9 ( 6 ) 1 1
6027q§·¨¸ ¨¸©¹

So, the new equation is 310 0tt
. 30 tt
, has a solution 0t
or 1 t r
.
If 0t
, 6233ax
, hence 2 x
is a root of the given equation. If 61, 1 13tx
, hence 1 x
is another root of the given equation. For munotes.in

Page 16

16DISCRETE MATHEMATICS61, 1 33tx
, hence 3 x is the third root of the given equation.
Gauss has introduced the concept of congruence and the notation , which makes it
such a useful technique. According to Gauss. If a number n measures the
difference between two numbers a and b, then a and b are said t o be congruent
with respect to n, if not then they are use called incongruent. Let us start wit h the
definition of congruence relation.
1.7 Congruence Relations
Let n be a fixed positive integer. Two integers a and b are said to be congruent
modulo n, write by ab{
(mod n), if n divides the difference a - b that is , abk n
for some integer k.
F o r e x a m p l e , c o n s i d e r n = 7 . we can see that 32 4 ( m o d 7 ) , 7 ( 2 43 ){
.
31 11(mod7), 7 11( 31)
15 64 (mod7), 7 64 ( 15){
{

I f ()na bF
, then we say that a is incongruent to b modulo n and in this c ase
we write a{
(mod )bn
. For example,e 25{
12 (mod 7)
, because 7 doesnot
divide 25 - 12 13.
Given an integer a, let q and r be it’s quotient and remainder upon division by n,
so that ,0 aq nr rn d
.
Then by definition of congruence, (mod ) ar n{
, because ( )nar q n
.
Since there are n choices for r, we observe that every integer is congruent modu lo
n to exactly one of the values 0,1, 2,... , 1 n
. The set of n - integers ^`0,1, 2,
is called the set of least positive residues modulo n.
In general, a collection of n - integers 12,, . . . ,n aa a
is said to form a complete set
of residues modulo n if every integer is congruent modulo n to one and only one
of theka. For example, 12, 4,11,13, 22,82,91
f o r m a c o m p l e t e s e t o f
residues modulo 7 here 12 2 (mod7), 4 3 (mod 7),11 4 (mod7),13 6 (mod7),{ { { {

22 1(mod7), 82 5 (mod7), 91 0 (mod7){{{
. munotes.in

Page 17

17Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsWe shall prove a theorem, which gives a useful characterization o f c o n g r u e n c e
modulo n in terms of remainders upon division by n.
Theorem :
For arbitrary integers a and b, (mod ) ab n{
if and only if a and b leave the some
non-negative remainder, when divided by n.
Proof :
Assume that (mod ) ab n{

abk n
for some integer k.
L e t ,0 bq nr r c n d
.
T h e n () . abk nq nrk n qk nr

, an r q k
.
a leaves the same remainder r, upon division by n.
Conversely, assume that 1 aq nr
and 2 bq nr
, with the same remainder (0 )rr nd
.
Then 12 1 2 () ( ) abq nr q nr q q n
. ( m o d )na b a b n {
. For example, - 56 and -11 can be expressed in the
form - 56 (-7) 9 + 7, -11 (-2) 9 + 7 with the same remainde r 7, hence from the
above theorem, 56 11(mod9){ congruence relation can be considered as a
generalized form of equality. Some of the basic properties of e quality holds true
in case of congruence’s we propose to prove these properties as the next theorem.
Theorem :
Let n > 0 be fixed and a, b, c, d be arbitrary integers. Then the follow ing
properties hold.
1. (mod ) aa n{
.
2. If(mod ) ab n{
, then(mod ) ba n{
.
3. If (mod ) ab n{
and(mod )bc n{
, then(mod ) ac n{
. munotes.in

Page 18

18DISCRETE MATHEMATICS4. If (mod ) ab n{
and(mod ) cd n{
, then (mod ) acbd n{

and(mod ) ac bd n{.
5. If(mod ) ab n{
, then (mod ) acbc n{
and(mod ) ac bc n{.
6. If(mod ) ab n{
, then (mod )kkab n{
for any positive integer k.
Proof :
1. For any integer a, we have a - a 0. n, so that(mod ) aa n{
.
2. If (mod ) ab n{
, then ab k n f o r s o m e i n t e g e r k, Hence () ba k n k n , since kis an integer (mod ) ba n{.
3. If (mod ) ab n{
and (mod )bc n{
then integers kand
satisfying, ab k n and bc n

() () () .
( is an integer)
( m o d )ac ab bc k n n k n
ac p n p k
na c a c n

{

4. If (mod ) ab n{
and (mod ) cd n{
. Then ab k n , cd q n for some
integers k and q. Therefore, we obtain () () ( ) () ac bd ab cd k nq n kq n
.
( ) ( )
(mod )nac bd
acbd n
{
S i m i l a r l y () ( ) ac b kn d qn

2bd bqn dkn kqn
() . ac bd bq dk kqn n
, ac bd pn where pb qd kk q n is some integer.
( m o d )na c b d a c b d n {
5. Given that (mod ) ab n{
, we know that (mod )cc n{
, by (4) we get, (mod ) acbc n{& (mod ) ac bc n{. munotes.in

Page 19

19Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions6. (mod )kkab n{is true if 1k . By induction hypothesis, assume that the
result is true for km
(mod )mmab n{ (mod ) ab n{
and applying (4), we get 11(mod )mmab n{
. Therefore the
result hold true for every positive integer k,(mod )kkab n{, whenever (mod ) ab n{
For example, to show that 41 divides2021. Note
that521 ( m o d 4 1 ){ 44 2025 9 (mod 41) 2 81.81(mod 41){ {.
But 20 2081 1(mod 41) 2 1(mod 41) 41 2 1{ { .
Theorem :
I f (mod ) ca cb n{, then modnabd§·{¨¸©¹, where gcd( , )dc n .
Proof :
(mod ) ca cb n ca cb kn{
for some integer k.
S i n c e gcd( , )dc n
relatively prime integers r and s s.t. , cd r nd s .
(mod ) dra drb n
dr a b kds{

ra b k s . Hence ( )sr a b .
S i n c e gcd( , ) 1 rs s a b
(mod ) ab s{. (B7 Eudid’s Lemma).
For example, consider the congruence 33 15(mod9){. 3.11 3.5(mod9){
.
Since gcd(3,9) 3 11 5(mod3) {.
Now let us consider the congruence relation 20(mod ) ax bx c p { whose p is
a prime greater than 2 and a{
0( m o d ) , p
t h a t i s , gcd( , ) 1ap . The
assumption that p i s a n o d d p r i m e i m p l i e s t h a t gcd(4 , ) 1 ap . Therefore the
given congruence is equivalent to 24 ( ) 0(mod )a ax bx c p {. munotes.in

Page 20

20DISCRETE MATHEMATICS 22 2
224( ) ( 2 ) ( 4 )
(2 ) ( 4 )(mod )aa x b x c a x b b a c
ax b b ac p
{

Now, put 2ya x b and 24 db a c to get 2(mod ) yd p{.
If 0(mod ) xx p{ is a solution of the congruence 20(mod ) ax bx c p {, then 02m o dya x b p{
satisfies the congruence 2(mod ) yd p{
.
Conversely, if 0(mod ) yy p{ is a solution of the congruence 2(mod ) yd p{,
then 0 2( m o d )ax y b p{ can be solved to obtain a solution of the
congruence 20(mod ) ax bx c p {.
Thus a problem of finding a solution to the quadratic congruenc e 20(mod ) ax bx c p {is same as that of finding a solution to a linear
congruence and a quadratic congruence of the form 2(mod ) xa p{.
If pa then this congruence has 0(mod )xp{ as the only solution. So, let us
assume that paF consider a simple example of the congruence 25 6 2 0(mod13)xx {. To obtain the solution, replace this congruence by 229(mod13)( 4 9) y b ac{ .
Now this congruence has solutions 3mod13, 10mod13yy{{
. Next, we solve
the linear congruence 10 9 mod13 ,x{ 10 16(mod13)x{
.
If can be checked that 10 mod13x{ and 12 mod13x{satisfy these
equations. Hence solving a linear congruence 0 2( m o d )ax y b p{ f o r x
required a test for the existence of solutions of the congruenc e 2(mod ), xa p{ gcd( , ) 1ap . In other words, we wish to find those integers a, which are p erfect
squares modulo p.
Definition :
Let p be an odd price and gcd( , ) 1ap . If the congruence 2(mod ), xa p{has a
solution, then a is said to be a quadratic residue of p. otherw ise, a is called a
quadratic non residue of p. munotes.in

Page 21

21Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsFor example, consider the case of the prime p = 13 we must know, which of the
congruence 2(mod13) xa{has a solution, when a runs through the set ^`1, 2, ..,12. Mod ulo 13, the squares of the integers 1,2,3,…,12 are :
22
22
22
22
22
221 12 1,
2 11 4,
3 10 9,
493 ,
5 8 12,
6 7 10{{
{{
{{
{{
{{
{{
Therefore, the quadratic residues of 13 are 1,3,4,9,10,12, whil e the non-residues
are 2,5,6,7,8,11.
Euler stated a simple criterion for deciding whether an integer a is a quadratic
residue of a given price p or not.
Theorem : (EULER’S CRITERION) :
Let p be an odd price and gcd( , ) 1ap . Then a is a quadratic residue of p if and
only if 1 21(mod )pap{
.
Proof :
Suppose that a is a quadratic residue of p, so that 2(mod ) xa p{
has a solution
call it 1x. Since 1 gcd( , ) 1 gcd( , ) 1ap x p .
?By Fermat’s theorem 11 221 2
11 1(mod )pppax x p{{ {

1 21(mod )pap{.
(Note : Fermats theorem says that, if p is a prime and paF, then 11(mod )pap{). Conversely, assume that 1 21(mod )pap{.
Let r be a primitive root of p, that is gcd( , ) 1rp a n d 1(mod )prp{ (mod )kar p{
for some integer ,1 1kk pdd. munotes.in

Page 22

22DISCRETE MATHEMATICS
1 2 1 2
1 21(mod )
1(mod )
1( ( 1 )2)kp p
kpra p
rp
pk p
{ {
{

k?is an even integer let 2kj .
Hence 2 2(mod )jkrj r r a p {
1. 4uadratic Residue
Hence jxr is a solution of the congruence 2(mod ) xa p{. This prove that a
is a quadratic residue of the prime p.
Corollary :
Let p be an odd prime and gcd( , ) 1ap . Then a is a quadratic residue or non
residue of p according as 1 21(mod )pap{ or 1 21(mod )pap{.
Proof :
If p is an odd prime and gcd( , ) 1ap , then 1 2 1 2 111 1 0 ( m o d )pp paa a p {
.
Hence either 1 21(mod )pap{or 1 21(mod )pap{ but not both.
For example, if p = 13 , we find that 13 1 2 622 6 4 1 2 1 ( m o d 1 3 ) {{
.
2?is a quadratic non-residue of 13.
Since 2 13 1 2 6233 2 7 1 1 ( m o d 1 3 ) {{
, the corollary indicates that 3 is a
quadratic residue of 13 and so the congruence 23(mod13)x{ is solvable.
Certain functions are of special importance in connection with the study of the
divisors of an integer. Any function whose domain is the set of positive integers is
said to be an arithmetic function. In the following section, we shall study certain
number - theoretic functions.

munotes.in

Page 23

23Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions1. Number Theoretic/Arithmetic )unctions
Definition :
Given a positive integer n, let of nW denote the number of positive divisors of
n and nV
denote the sum of these divisors.
For example, consider n = 12, since 12 has the positive divisors 1, 2, 3, 4, 6, 12

we find that 12 6V
and 12 1 2 3 4 6 12 28V
.
Let us introduce a notation
dnfd¦to mean, the sum of values of fdas d
runs over all positive divisors of the positive integers n. For instance, we have
20(1) (2) (4) (5) (10) (20)
dfd f f f f f f
¦ with these understanding,
of and
1,
dnnV ¦
dnndV ¦. If
1010, 10 1 1 1 1 1 4
dnn WW ¦
,
because there are just four positive divisors of 10 namely 1,2, 5,10. Also, we
obtain 10 1 2 5 10 18V
w h e n e v e r 12
12....r kk k
r np p p
is the prime
factorization of 1n!
, then the positive divisors of n are precisely those integers d
of the form 12
12 ....r aa a
r dp p p
, where 0( 1 , 2 , . . . , )iiak i rdd
.
Now, let us find the formulae for nWand nVin terms of prime factorization
of a positive integer n ! 1.
Theorem :
If 12
12....r kk k
r np p p
is the prime factorization of n ! 1, then
a) 1211 . . . 1r nk k kW
and
b) 1211 1
12
1211 1...11 1r kk k
r
rpp pnpp p
V §· §· §· ¨¸ ¨¸ ¨¸ ©¹ ©¹ ©¹
Proof :
a) The positive divisors of n a r e p r e c i s e l y t h o s e i n t e g e r s 12
12 ....r aa a
r dp p p
,
where 0iiakdd
There are 11k
choices for the exponent 12,1ak
choices for munotes.in

Page 24

24DISCRETE MATHEMATICSthe exponent 2,...., 1r ak
c h o i c e s f o r ra, hence there are 1211 . . . . . 1r kk k possible divisors of n.
In order to evaluate nV, consider the product. 12 22
11 1 2 2 1. . . 1 . . . 1. . .r kk k
rr r pp p p p pp p
. Each
positive divisors of n appears once and only once as a term in the expansion of
this product, so that 1 2
11 11. . . . . .knp pp
V . 21. . .rk
rr rpp p

Using the geometric series formula, 1
2 11. .1i
ik
k i
ii i
ippp pp

If follows that 1211 1
12
1211 1...11 1r kk k
r
rpp pnpp p
V §· §· §· ¨¸ ¨¸ ¨¸ ©¹ ©¹ ©¹
A notation for the products is defi ned by the Gree k capital let ter p i, denoted by 3
for example.
15
12345
139d
dqfd f f f f f
fd f f fdd3
3

In this notations.

1
1
11
1
1iiir
k
i
irink
pnp
V
Vdd

dd 3
3
For example, the number 22180 2 .3 .5 has 180 2 1 2 1 1 1 18

positive divisors the sum of these 18 integers is 332213151180 7 13 6 54621 31 51V§· §· §· u u ¨¸ ¨¸ ¨¸©¹ ©¹ ©¹
.
Definition :
An arithmetic function f i s s a i d t o b e m u l t i p l i c a t i v e i f , fm n fmfn

whenever gcd , 1 mn . munotes.in

Page 25

25Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsTheorem :
The functions W and V are both multiplication function.
Proof :
Let m and n be relatively prime integers. Assume that 1m!
and 1n!. If 12
12....r kk k
r mp p p
and 12
12....sj jj
s nq q q
are the prime factorizations of m and n
then, since (,)1ij mn p q z
for any j.
11
11.... ....s r j kk j
rs mn m p p q q

of 1 1 1 ( ) ( )ris mn k j j of m of n
?
S i m i l a r l y , 11 1 11 1
11
111 11 1
11 1 1s r j j
s r
rsq pp qmnpp q qV §· §· ¨¸ ¨¸ ©¹ ©¹

mnVV

Thus, W and V a r e m u l t i p l i c a t i v e f u n c t i o n s w e i n t r o d u c e a n o t h e r n a t u r a l l y
defined functions on the positive integers, the mobius P-function.
Definition : for a positive integer n, define Pby the rules.
1nP
if 1n
0
if 2pn for some prime P.
1r
if 12...r np pp where ipare distinct primes.
For example, 1rnP
, if nis square free with r prime factors.
330 2.3.5 1 1PP
.
The first few values of P a r e 11 , 21 , 31 ,PPP
4P 0, 5 1, 6 1PP
, .. If p i s a p r i m e n u m b e r , i t i s c l e a r t h a n 1 pP
, also 0 pP
f o r 2t. We can observe that the Mobius P-
function is multiplicative.
Theorem : The function P is a multiplicative function. munotes.in

Page 26

26DISCRETE MATHEMATICSProof :
Assume that both m a n d n are square free integers. Say 21 2.. . ., . . . .rs mp pp nq q q
, the primes ip and iqbeing all distinct. Then 11... ... 1rs
rs mn p p q qPP

11rsmnPP .
Let us see what happens if dPis evaluated for all the positive divisors d of an
integer n and the results added.
If
11, 1 1
dn dnd d PP P ¦¦

Suppose 1n!
, put
()
dnFn d P ¦
.
If knp
the power or prime, then the positive divisors of kpare just the k+1
integers 21, , ,pp pso that
2
1. . .
dpFp d p p p PP PP P
¦

11 ( 1 ) 0 p PP

If n has a prime factorization 12
12....r kk k
r np p p
, then F(n) is the product of the
values assigned of F for the prime powers in this representation :
12
12 .... 0r kk k
r Fn Fp Fp Fp
, since F is a multiplicative function. ? For each positive integer 1,nt
1
dndP ¦
if 1n 0 if 1n!
where d
runs through the positive divisors of n.
For example, consider n=10 . The positive divisors of 10 are 1, 2, 5,10 and the
desired sum is

101251 0
ddPP PPP ¦

1( 1 )( 1 )10
. munotes.in

Page 27

27Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsTheorem : (MOBIUS INVERSION )ORMULA) :
Let F and f be two arithmetic functions related by the formula.
() ()
dnFn f d ¦
Then () () ()
dn dnnnFn d F FdddPP§· §· ¨¸ ¨¸©¹ ©¹¦¦

Proof :
C o n s i d e r ( )() () ( )
dn dn cndndF d fcdPP§·§· ¨¸¨¸©¹©¹¦¦ ¦

( )()( )
dn cnddfcP§· ¨¸
©¹¦¦
It can be verified that d/n and c/(n/d) if and only if o/n and d/(n/c)
( ) ( )dn c nd cn d ncdf c f c dPP§· §·? ¨¸ ¨¸
©¹ ©¹¦¦ ¦¦

( )cn d ncfc d P§· ¨¸
©¹¦¦

Now, the sum
( )dn cdP¦vanishes except when 1n
c
(that is nc ), in this
case 1dP
.

( ) .1 ( )
cn d nc cnfc d fc fn P§·? ¨¸
©¹¦¦ ¦
.
Definition :
For an arbitrary real number x, we denote by > x@, the largest integer less than or
equal to x, that is, > x@ is the unique integer satisfying >@1xx x d
.
For example, >@ > @312, 2 1, 0 3, 423SSªº ª ºªº «» « » ¬¼¬¼ ¬ ¼
.
Note >@xx
if and only if x is an integer. munotes.in

Page 28

28DISCRETE MATHEMATICS1.10 Let Us Sum Up
1) Division Algorithm :
Given integers a and b, with b>0 t h e r e e x i s t u n i q u e i n t e g e r s q and r s a t i s f y i n g ,0 ab qr rb d d
the integers q and r are called quotient and remainder in the
division of a by b.
2) The gcd of two integers a and b can be computed by the Eucli dean algorithm
as follows :
W r i t e 11 1
21 2 2 1
13 2 3 3 2
21 1
11,0
,0
,0
,0
0nn n n n n
nn naq br rb
bq r r r r
rq r r rr
rq r r r r
rq r

Here the last step involves a complete division, hence giving u s rn as the gcd of
integers a and b.
3) A Linear Diophantine equation ax by c
can be solved for x and y only if gcd , ab divided c. If 0x and 0y are particular solution of ax by c
, then all
other solutions are given by :
00 ,baxx t yy tdd§· §· ¨¸ ¨¸©¹ ©¹
for varying integer t.
4) Cardanos method helps us solve a cubic equation 320 xa xb x c
by
reducing the equation to 30 t pt q
. If tPX then the equation 3
2027pt qt
has roots 3P and 3X given by 23
3
2 4 27qq pu X§· §·§· ¨¸ ¨¸¨¸©¹©¹ ©¹
, 23
3
2 4 27qq pXX§· §·§· ¨¸ ¨¸¨¸©¹©¹ ©¹
.
5) Two integers a and b are said to be congruent modulo n, writ ten by (mod ) ab n{
, if ( )na b congruence is a general form in equality. munotes.in

Page 29

29Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions6) A problem of finding a solution to the quadratic congruence 20 (mod ) ax bx c p {
is some as that of finding a solution to a linear
congruence and a quadratic congruence of the form 2(mod ) xa p{
. If p is an
odd prime and gcd , 1 ap
a n d t h e c o n g r u e n c e 2(mod ) xa p{
is solvable
then a is called as the quadratic residue of p otherwise, a is called a quadratic non
residue of p.
7) Euler’s criterion is helpful to decided whether a is a quadratic residue of an
add prime p or not. It states that if gcd , 1 ap
, then a is a quadratic residue of
p if and only if (1 ) 21(mod )pap{
.
8) Given a positive integer n, of (n) and nV denote the number of positive
divisions of n and the sum of these divisors respectively. If 12
12....r kk k
r np p p
is
the factorization of n>1, then
12 () 1 1 . . . 1r of n

1211 1
12
1211 1() . . .11 1r
r
rpp pnpp pV §· §· §· ¨¸ ¨¸ ¨¸ ©¹ ©¹ ©¹

9) One of the very important arithmetic function is the Mobius P-function
defined by :
1nP
if 1n
0
if 2pnfor some prime p.
1r if 12...r np pp where ipare distinct primes.
10) Mobius Inversion formula :
Let f and F be two arithmetic functions related by the formula
() ()
dnFn f d ¦
Then
() () ()
dn dnnnfn d F F dddPP§· §· ¨¸ ¨¸©¹ ©¹¦¦
. munotes.in

Page 30

30DISCRETE MATHEMATICS1.11 Solved Numericals
1) Show that the expression 22
3aa is an integer for all 1at.
Solution :
According to the Division Algorit hm, every integer a is of the form 3, 3 1 , 3 2qq q
. If 3aq t h e n 2
22
913aa
qq

which is clearly an
integer. Similarly, if 31aq , then 2 231 31 2 3 31 3 21qq q q q
and22
3aa is an
integer in this case. Finally, if 32aq then we get
2
2 2 3232 233aa qq

232 3 42qq q
an integer once again.
2) Use the division Algorithm to establish that the square of a ny integer is either
of the form 3 or 31.
Solution :
Given any integer a, by the Division Algorithm,
3, 3 1aq aq
or 32aq
If 2 22 233 9 3 3 3aqa q q q

If 2 22 231 31 9 61 3 3 2 1 3 1aq a q q q q q

If 2 22 232 32 9 64 3 3 21 1aq a q q q q q

31

3) Prove that 231ais never a perfect square. munotes.in

Page 31

31Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsSolution :
If 2231ab
for some integer b then 231 3a or 231 3 1a , by
problem (2)
22
2233 1 o r 33 2
31 o r 3 2ak ak
aa

Neither case is possible, because 2a is an integer 231a can’t be perfect
square for some integer b.
4) If a, b are integer, not both of which are zero, verify that

gcd , gcd , gcd ,
gcd ,ab ab a b
ab

Solution :
Let gcd( , )da b and gcd( , )ca b
ca
and cb
ca
and cb, but gcd( , )da b
cd similarly dc, hence gcd( , ) gcd( , ) cd a b a b
gcd( , ) gcd( , )ab ab

Putting a as -a on both the sides gcd( , ) gcd( , ) ab ab

L e t gcd( , )da b and gcd( , )ca b
ca
and cb
ca
and cbbut d is the gcd of a & b cd.
Similarly dc cd.
gcd( , ) gcd( , ) ab a b

L e t gcd( , )da b and gcd( , )ca b
ca & cb munotes.in

Page 32

32DISCRETE MATHEMATICSca & cb but d being the gcd of a & b cd. Similarly, we can show
that dccd .
Hence gcd( , ) gcd( , )ab a b

5) Use the eudidean algorithm to obtain integers x and y satisfying.
a ) g c d ( 5 6 , 7 2 ) 5 6 x + 7 2 y
b) gcd (119, 272) 119x + 272y
Solution :
a) Write 72 1 56 16 u

56 3 16 8
16 2 8 0 u
u

?The last nonzero remainder is 8.
? gcd(56,72) 9
85 63 1 6
56 3(72 1 56)
56 3 72 3 56
45 637 2
gcd(56,72) 56(4) 72( 3) u
u
u u
u u?

6) Prove that if gcd(a,b) 1, then gcd (a+n, ab) 1.
Solution :
L e t d g c d ( a + b , a b )
d / a+b and d/ab
a + b = dm and ab = dn for some integers m,n
a = dm - b, ab = dn
(dm - b) b = dn
dmb - b2 = dn d(mb - n) = b2
Hence d/b2. similarly d/a2
d/b and d/a. munotes.in

Page 33

33Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ionsBut d is the gcd of a + b & ab and gcd(a,b) = 1. So, by definition 1 1dd
or 1 d , being gcd 1d .
gcd , 1 ab a b

7) Use cardanos method to s olve the cubic equation 3233 2 0xxx .
Solution :
Substituting 3133axt t t , to eliminate the 2xterm, we obtain new
equation 30 t pt q .
W h e r e 2
3apb
and 329
27a abqc§· ¨¸©¹
2
3330 ,3
2(3 ) 9(3) (3)22 ( 2 3 )27
3p
q
q
§· ¨¸©¹

S o , t h e n e w e q u a t i o n i s 330 to t
.
33 t

So 331 x .
I n s u m m a r y , t h e r o o t s f o r t h e c u b i c .
32
1
2
333 2 a r e
0.4422495703
1.7211247852 1.2490247665
1.7211247852 1.2490247665xxx
x
xi
xi

8) Use Cardanos method to find the roots of the cubic 3264 48 12xx
.
Solutions :
S u b s t i t u t e 91.3xx t In the cubic 320.75 0.1875 0.015625xx x , to get a
new equation 30 t pt q , 2329,32 7
0, 0aa q bpb qc
pq§· ¨¸©¹?
munotes.in

Page 34

34DISCRETE MATHEMATICS S o , t h e n e w e q u a t i o n i s 300 to t

900 . 2 53tx
.
? All three roots are real equal to 0.25.
9) A customer bought a dozen pieces of fruit, apples and orange s for 1.32. If an
apple costs 3 cents more than an orange and more apples than or anges were
purchased, how many pieces of each kind were bought"
Solution :
Let x be the number of apples and y be the number of oranges purchased, also, let
z represents the cost (in cents) of an orange. Then the conditio n of the problem
lead to 31 3 2zx z y
or 3( )1 3 2xx y z
.
Since x + y = 12 , the above equation may be replaced as 31 21 3 2xz
, which
in turn simplifies to 44 4xz
.
As gcd 1,4 1 is a divisor of 44, there is a solution to this equation.
11 ( 3 ) 4 ( 1 ) ,
upon multiplying by 44, we get
44 1( 132) 4.44 .
00 132, 44 xz
is a solution.
A l l o t h e r s o l u t i o n s a r e o f t h e f o r m
132 4 xt
44zt
, t is any integer we want x s.t. 12 6. xt!
12 132 4 6
36 & 132 4 6
34
2
35 and 36t
tt
t
ttt !
d !
!?

? These are two possible choices. munotes.in

Page 35

35Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions12 apples costing 11 cents per piece or 8 apples at 12 cents ea ch and 4 oranges at
9 cents each.
10) Solve the following puzzle :
Alcuin of such a way that each man receives 3 bushels, each woman 2 bushe ls and each
child ò bushels. How many men, women & children are there"
Solution :
Let there be z men, y women and z children.
132 1 0 02xy z
and there are 100 persons in all. Therefore
100
100
132 ( 1 0 0 ) 1 0 02
535022
531 0 0xyz
zx y
xy x y
xy
xy
?
§· §· ¨¸ ¨¸©¹ ©¹

As gcd(5,3) 1
, is a divisor of 100, there is a solution to this equation 1( 1 )52( 3 ) uu
? multiplying the above equation throughout by 100, we
obtain
100 ( 100) 5 (200) 3? u u

0 100 x? and 0200y
is a solution, All other so lutions are of the form
100 3 xt

200 5yt
, t is any integer, if we put t 34, we get
100 5 34 100 102 2
200 5 34 200 170 30x
y u
u
? A p o s s i b l e s o l u t i o n i s t h a t t h e r e a r e 2 m e n , 3 0 w o m e n a n d 100 32 68

number of children.
11) Find the remainder, when 502 and 6541are divided by 7. munotes.in

Page 36

36DISCRETE MATHEMATICSSolution :
10 5 5
102 2 2 32 32
2 32 32 mod 7
32 mod 7 32 mod 7 u u
?{u
{u

510 54 mod 7 4 mod 7
16 mod 7 2 mod 7
2 2 mod 7 32 mod 7 4 mod 7{u
{{?{{{

? The remainder, when 502 is divided by 7 comes out to be (4).
N e x t , w e k n o w t h a t 41 6 mod 7{
.
65 65
5
135 1341 6 mod 7
6 7776 6 mod 7.
6 6 mod 7?{
{?{

13
253
55
36m o d 7
66 m o d 7
6m o d 7 6m o d 7 2 1 6 m o d 7
6m o d7 6m o d7 6m o d7
6m o d 7 6 m o d 7{
ªº{«»¬¼
{u
{uu
{{

? The remainder, when 6541 is divided by 7 found to be (6)
12) Solve the quadratic congruence 27 10 0 (mod11)xx{
.
Solution :
H e r e 1, 7, 10, 11ab c p

?Replace this congruence by the simpler one 2(mod ) yd p{

2
229 & 4
27 74 0 9yx b d b a c
yxa n d d ?
munotes.in

Page 37

37Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions29 mod11y{
, this has two solution 3m o d1 1y{
and 8m o d 1 1y{
, next
we solve the linear congruences,
0 2( m o d )ax y b p{
for
003& 8
27 m o d 1 1 & 21 m o d 1 1yy
xx
{ {

It can be seen that 9m o d1 1x{
& 6m o d1 1x{
a r e s o l u t i o n s o f t h e s e
congruences respectively. 9m o d1 1x?{
and 6m o d1 1x{
a r e s o l u t i o n s o f t h e g i v e n c o n g r u e n c e 27 10 0 (mod11)xx{
.
13) Show that 3 is a quadratic residue of 23, but non-residue o f 31.
Solution :
By Eulen’s criterion, a is a quadratic residue of P iff gcd , 1 ap a n d 1
21m odp
ap
{
.
? Consider 23 1
511 2 233 3 3§·
¨¸©¹

23 152 23 3 .3 mod 23?{

5
2
2
29. 3m o d2 3
81 .9.3 mod 23
81 mod 23 4 mod 23
81mod 2381mod 23 4 mod 23
12 mod 23 4 mod 23
8m o d2 3 4m o d2 3
24 mod 23 1mod 23{
{
{
{
{u
{u
{{

munotes.in

Page 38

38DISCRETE MATHEMATICSHence 23 1
23 mod 23
{
. Therefore 3 is a quadratic residue of 23.
I f 13 1 1
15 2231, 3 3 3p
p

31 1515 2 5 2
55
31 1
23 3 mod 31 3 .3 mod 31
9m o d 3 1 . 3m o d 3 1
25 mod 31. 26 mod 31
650 mod 31 30 mod 31
30 mod 31
3
?{ {
{
{
{{
{
{
1mod 31

3
is a quadratic non-residue of 31.
14) Knowing that 2 is a primitive root of 19, find all quadrati c residues of 19.
Solution :
In the proof of Euler’s criterion, we saw that, if r is a primitive root of p then modkkr p{
for some integer
,1 1kp dd
and 2Kj
? consider even powers of 2r
0 2 4 6 8 12 142 1, 2 4, 2 16, 2 64 7, 2 28 9, 2 36 17, 2 68 11,{{{ { {{ { { { { {
16 182 44 6, 2 24 5{{ {{
1, 4,16, 7, 9,17,11, 6, 5
are the quadratic residues of 19.
15) Find the gcd(12378, 3054)
and (12378, 3054)lom
Solution :
11 0 112378 2 3 2060
3054 2 3 509
12378 2 3 509 2063 & uu
uu
u u u

11 1 03054 2 3 509 2063 uu u
munotes.in

Page 39

39Chapter 1: Divisibility Theory of Integers and Arithmetic Funct ions ?By the theorem,
min1,1 min1,1 min 0,1 min 0,1
11 0 0
max1,1 max1,1 max 0,1 max 0,1gcd(12378, 3054) 2 3 509 2063
235 0 9 2 0 6 3
&( 1 2 3 7 8 , 3 0 5 4 ) 2 3 5 0 9 2 0 6 3lom uu u
uu u
uu u
235 0 42 0 6 3
6,18,400 uu u

1.12 Check Your Progress
Unit End Exercises:
1) Show that the product of any set of n consecutive ingeters is divisible by n.
(Hint : any product of n consecutive integers looks like
1( ) ( 1 )kk n
for some integer k).
2) Find the quadratic residues of 29 & 31.
3) Let m & n be positive integers and 12,, . . ,r pp pbe distinct primes, which
divide atleast one of m or n. The n m & n can be written in the form
12
12r kk k
r mp pp
, with 01 , 2 ,iir t

12
12 0r jj j
ri np pp j t
for 1, 2,ir

Then prove that
12
12 gcd ,r uu u
r mn p p p
& 12
12 ,r
r lcm m n p p pXX X
where
^`
^`min , ,
max ,ii i
ii ij
jP
X

4) Solve the following quadratic congruence 23 9 7 0 (mod13)xx {
.
5) Using cardanos method solve the following cubic polynomial e quation 3225 6 0xxx
. munotes.in

Page 40

40DISCRETE MATHEMATICS6) Determine all solutions in the integers for the following Di ophantine equation 24 138 18xy
.
7) Show that the cube of any integer is of the form 7 or 71r
. (Hint : Apply
division algorithm).
8) Given an odd integer a, establish that 222( 2) ( 4) 1 aa a
is divisible
by 12.
9) Find gcd 119,272 and (143, 227)lcm.
munotes.in

Page 41

2
BASIC PRINCIPLES O) COUNTIN*
Unit Structure :
2.0 Objectives
2.1 Introduction
2.2 Elementary Set Theory
2.3 The sum Rulep
2.4 The Product Rule
2.5 Double Counting
2.6 Permutations
2.7 Combinations
2.8 Binomial and Multinomial Co-efficient
2.9 Pascal’s Identity
2.10 Binomial and Multinomial Theorems
2.11 Let us Sum up
2.12 Solved Numerical
2.13 Unit End Exercises
2.0 ObMectives
After going through this chapter, you will come to know about
Basic concepts in set theory
Counting Techniques like the sum rule and the product rule
Two way counting the size of the set
Permutations as on arrangement o f finitely many objects in a line
Combinations or selection of r objects form given n – distinct objects
Binomial and Multinomial theorem to count the size of a set d efined by
certain constraints
Some identities like Pascal’s identity by using two way countin g 41Unit 1
munotes.in

Page 42

42DISCRETE MATHEMATICS2.1 Introduction
We shall understand sets and functions as basic requirements to formulate certain
counting techniques we deal only with the sets consisting of on ly finitely many
objects in it . We will regard the word set as synonymous with the word “Clas s”
“collection” and “family”
2.2 Elementary Set Theory
In this section, we shall review of the terminology and notatio n that will be used
in this text. If an element x is in a set A, we write x A and say that x is a
member of A or that x belongs to A. If x is not in A, we write x .A. If every
element of a set A also belongs to a set B, we say that A is a subset of B and write
A B or B A.
Definition : Two sets A and B are said to be equal and we write A = B , if they
both contain the same elements.
Thus, to prove that the sets A and B are equal, we must show th at
A B and B A
If Principal denotes a property that is meaningful and unambigu ous for elements
of a set S, then we write {x s : P(x)} for the set of all elements x in s for which
the property p is true.
For example, the set of natural numbers
= {1, 2, 3, …..} The set of integers
= {0, 1, –1, 2, –2, ……} The set of rational numbers

{m
n : m, n
, n z 0} The set of all real numbers

Set operations :-
a) The union of sets A and B is the set
A B = {x : x A or x B}
b) The intersection of the sets A and B is the set
A B = {x : x A or x B} munotes.in

Page 43

43Chapter 2: Basic Principles of Countingc) The complement of B relative to A is the set
A – B : = {x : x A or x B}

The set that has no elements is called the empty set and it is denoted by the
symbol . Two sets A and B are said to be disjoint, if they have no ele ments in
common, symbolically, use write A B
Theorem :- (De Morgan ’s laws)
If A, B, C are sets, then
a) A – (B C) = (A – B) (A – C)
b) A – (B C) = (A – B) (A – C)
For a finite collection of sets {A1, A2, ….., A n}, their union is denoted by n
k=1UAr
consisting of all elements that belong to atleast one of the se ts A R a n d t h e i r
intersection is denoted by n
k=1UArconsists of all elements that belong to all of the
sets A R.
Cartesian Products :
In order to discuss functions, we define the Cartesian product of two sets.
Definition :- If A and B are nonempty sets, then the Cartesian product A u B of A
and B is the set of all ordered pairs (a, b) with a A and b B. That is
A u B = {(a, b) : a A, b B}
Thus if A = {1, 2, 3} and B = {1, 5}
Then A u B consists of the ordered pairs (1, 1), (1, 5), (2, 1), (2, 5) , (3, 1), (3, 5)
we will not discuss the fundamental notion of a function or a m apping. To the munotes.in

Page 44

44DISCRETE MATHEMATICSmathematician of the early nineteenth century, the word functio n meant a definite
formula, such as f(x) = x2 + 3 x – 5, which associates to each real number x,
another number f(x). Here f(0) = –5, f(1) = –1, f(5) = 35
A function f from a set A into a set B is a rule of corresponde nce that assigns to
each element x in A, a uniquely determined element f(x) in B.
Definition :- Let A and B be sets. Then a function from A to B is a set f of
ordered pairs in A u B such that for each a A there exists a unique b B with
(a, b) f. The set A of first elements of a function f is called the dom ain of f,
denoted by D(f). The set of all second elements in f is called the range of f an d it’s
often denoted by R(f). Note that D(f) = A , we only have R(f) B.
The essential condition that (a, b) f and (a, b c) f implies that b = b1. The
notation f : A o B is often used to indicate that f is a function from A into B w e
will also say that f is a mapping of A into B or f maps A into B. It is customary to
write b = f(a) or a
b
Direct and Inverse Images :
Let f : A o B be a function with domain
D(f) = A and range R(f) B.
Definition : If E is a subset of A, then the direct image of E under f is t he subset
f(E) of B given by
f(E) = {f(x): x E}.
If H is a subset of B, then the inverse image of H under f is t he subset
f–1(H) of A given by
f–1 (H) = {x A : f(x) H}
Special types of functions :
The following definitions identify some very important types of functions.
Definitions : Let f : A o B be a function from A to B
a) The function f is said to be injective or one –to-one) if whenever x1 z x2,
then f(x1) z f(x 2). If f is an injective function, w e say that f is on injection. munotes.in

Page 45

45Chapter 2: Basic Principles of Countingb) The function f is said to be surjective (or onto B) if f(A) = B , that is, if the
range R(f) = B . If f is a surjective function, w e say that f is a surjection.
c) If f is both injective and surjective, then f is said to be bijective. If f is
bijective, we say that f is a bijection.
For example, Let A = {x
: x z 1}, define f(x) = 2x
x-1 for all x A. Then if is
injective for 12
122x 2x
=x- 1 x- 1 i m p l i e s t h a t 12 21x (x - 1) = x (x - 1) x1 x 2. To
determine the range of f, we solve the equation 2xyx1 for x, in terms of y we
obtain yx=y-2, which is meaningful if y z 2. Thus the range of f is the set B = {y

: y z 2}. Thus f is a bijection of A onto B.
Inverse functions :
If f : A o B is a bijection then we can define another function g : B o A
such that g(b) = a whenever f(a) = b . Here g is called the inverse function of f,
denoted by g = f–1.
Definition :-
If f : A o B is a bijection of A on to B, then g = {(b, a) B u A : (a, b) f} is a
function of B into A, denoted by g = f–1
For example, the function f(x) = 2x
x-1 is a bijection of A = {x
: x z 1} on to
the set B = {y
: x z 2}. The function inverse to f is given by
f–1(y) = y
y-2 for y B.
Composition of )unctions :
If often happens that we want to compose two functions f, g by first finding f(x)
and then applying g to get g(f(x)) . However, this is possible only when f(x)
belongs to the domain of g.
Definition :- I f f : A o B and g: B o C a n d i f R(f) D(g) = B , then the
composite function (g o f) is the function from A into C defined by munotes.in

Page 46

46DISCRETE MATHEMATICS(g o f) (x) = g(f(x)) for all x A

For example, let f(x) = 1 – x2 and g(x) = x, then since D(g) = {x : x t 0} the
composition function (g of) is given by the formula
(g o f) (x) = g(f(x))
2f(x) = 1- x
Only for x D(f) that satisfy f(x) t 0, that is for x satisfying –1 d x d 1.
Restrictions of functions :
If f : A o B is a function and if A1 A, we can define a function f1 : A 1oB
by f 1 (x) = f(x) for x A1, denoted by f1 =f/A 1.
Principles of Mathematical Induction :
1) Let s be a subset of
that possesses the following properties :
a ) T h e n u m b e r 1 s
b) For every k
, if k s then k + 1 s
T h e n w e h a v e s =

2) Let s be a subset of
such that
a ) 1 s
b) For every k
, if {1, 2, …., k} s, then k + 1 s
T h e n s =

The above two principles of mathematical induction are used to prove a result
P(n) is true for every positive integer n. munotes.in

Page 47

47Chapter 2: Basic Principles of CountingNow, let us start with elementary counting techniques, based on t h e s i m p l e
observations summarized as the sum role and the product rule.
2.3 The Sum Rule
Suppose Task 1 can be done in m different ways and Task 2 in n different ways.
Also there is no way of doing both the tasks together, then the number of ways of
doing either Task 1 or Task 2 can be done in (m + n) different ways.
For example, if there are 80 mathematics and 40 statistics book . Then there are 80
+ 50 = 130 ways of selecting either a Mathematics or an English book,
The General form of this sum Rule can be stated as follows :
If there are n 1 ways of performing an event, n 2 ways of performing second event
and n r ways of doing rth event. Then either of these r-events can be performed in
(n1 + n 2 + ….. + nr) different ways.
2.4 The Product Rule
Suppose a procedure can be divided into a first step followed b y the second step
and that there are m-different ways of performing step-1 and n- different ways of
performing step-2, independent of the first step. Then a proced ure can be
accomplished in m u n ways.
For example, two dice are thrown, then there are 6 different ou tcomes of a given
dice. So there are 6 u 6 = 3 6 p o s s i b l e o u t c o m e s o f t h r o w i n g t w o d i c e , t h e
generalised form of the product rule can be stated as follows.
Suppose a procedure can be broken into r stages with n 1 outcomes in the first
stage, r 2 outcomes in the second stage, n r outcomes in the rth stages. If all these
outcomes at every stage are independent of each other then the procedure can be
performed in n1, n2, ….. n r different ways. For examples, if we are to decide how
many different 3-digit eve numbers are there, in writing such a number the first
digit can’t be zero, so there are 9 ways to choose the first digit, the second digit
can be zero, so there are 10 ways to form second digit and the last digit can be 0,
2, 4, 6 or 8, so thee are 5 choices for the third digit. Theref ore the product 9 u 10
u5 = 450 is the total number of 3-digit even numbers,
munotes.in

Page 48

48DISCRETE MATHEMATICSDefinition :-
A set x is said to be an n-set consisting of n number of elemen ts, if x has n
different objects.
For example, A = {1, 2, 3, 4, 5} is a 5-set consisting of 5-district objects.
B = {0, 1} is a 2-set consisting of 2-distinct elements.
One of the important question is to count the number of arrange ments of an n-set
x in order. For example, if three people Ms. Jordan, Mr. Harper and Ms. Gabler
are scheduled for job interviews. In how many different orders can they be
interviewed "
Let us list all possible orders, as follows :
1. Jordan, Harper, Gabler
2. Jordan, Gabler, Harper,
3. Harper, Jorden, Gabler
4. Harper, Gabler, Jordan
5. Gabler, Jordan, Harper
6. Gabler, Harper, Jordan
We can see that there are total 6 possible orders. Alternativel y, we can observe
that there are 3 choices for the first person being interviewed . For each of these 3
choices there are 2 remaining choices for second person. For ea ch of these
choices, there is only 1 choice remaining for third person. Hen ce by the product
rule, the number of possible order is 3 u 2 u 1 = 6.
If there are 5 people to be interviewed then there are 5 choice s possible for first
person, 4 choices for second and so on, resulting in 5 u 4 u 3 u 2 u 1 = 1 2 0
possible order in all.
The number of permutations of an n-set x is given by
n u (n – 1) u (n – 2) u … u 2 u 1 = n!
2.5 Double Counting / Two Way Counting
In combinatorics, two way counting is a proof technique for sho wing that two
expressions are equal by demonstrating that they are two ways o f counting the
size of one set, munotes.in

Page 49

49Chapter 2: Basic Principles of CountingFor example if ; is the collection of all committees that can b e formed from K
people. Then n
nX2 2 . . . . . 2 2 uu u

Alternatively, one may observe t hat the size of the committee m ust be some
number between 0 and n. For each possible size k, the number of ways, in which
a committee of k people can be formed from n people is the bino mial co-efficient n
k. Therefore the total number of possible committees is the sum of the
binomial co- efficients over k = 0, 1, 2, …, n. Equating the two expressions gives
the identity
nnn
k
k02
¦
Another way we can make use of double counting in proving Vande rmonde’s
Identity, that states that if m, n, r
+ ^0` then rmn n mr kr k
k0

¦
This identity can be formulated as a problem of forming a commi ttee of r senators
in the US senote consisting m Democrats and n Republicans. Then the number of
ways of forming a committee of r-senotors is mn
r
Now, every typical committee of r-senators contain K Democrats and
consequently r-k Republicans, so by the product rule the number of
subcommittees consisting k Democrats and r – k Republicans is n m
kr k .
Therefore there are rn m
kr k
k0
¦ distinct ways of forming a committee of r-
senotors. It implies that rmn n mr kr k
k0

¦
Next example, we wish to find the number of ways, we can select 3 students from
a student body of 3n, where n are singers, n are dancers, n are musicians " There
are two answers to this question. From the total group of 3n st udents, choose 3 in 3n
3 ways. munotes.in

Page 50

50DISCRETE MATHEMATICSCase 1 – Choose all 3 students from the same group we can choose the gr oup in 3
ways, then the students in n
3 ways.
By the multiplication principles, there are 33n
3 ways to do this.
Case 2 – Choose 2 groups, then 1 student from the first group and 2 stu dents from
the second group. Since order matters, there are 6 ways to choo se a ranked pair of
groups and n
1 and n
2 ways to choose the students fro those groups. Thus Case
2 is covered in 6nn
2 ways.
Case 3 – Choose 1 student from each group. By the multiplication princi ple the
product rule, this can be done in n
1n
1n
1 n3 w a y s . B y a b o v e t h e s e c a s e s ,
which are not occurring simultaneously.
3n n n 3
33 236 nn

2. r – Permutations :
Given an n-set x, suppose we wish to pick r elements and arrang e them in order
such on arrangement is called r-permutation of the n-set x. For e x a m p l e , t h e
number of three letter words without repeated letters can be ca lculated by noticing
that we want to choose three letters out of 26 and arrange them in order the first
letter of a three letter word can be chosen in 26 ways, having done this the second
letter has 26 – 1 = 25 choices left and consequently the third letter can be chosen
in 25 –1 = 24 ways. Hence by the product rule there are 26 u 25 u 24 different
three letter words without repetition. Let P(n, r) be the number of r-permutations
of an n-set X. Hence P(26, 3) = 26 u 25 u 24
Theorem : n t r then the number of r-permutations of an n-set x without
repeatition is given by
P(n, r) = n!
(n - r)!
Proof : Consider a typical r permutation of an n-set x,
b1b2 br–1 br munotes.in

Page 51

51Chapter 2: Basic Principles of CountingHere b 1 has n – choices hence b2 has n – 1 choices left, b3 can be chosen from n –
2 objects and so on b r–1 can be chosen from n–(r–2) objects and there fore there
are n –(r–1) choices left for br. Hence by the product rule, there are
n u (n – 1) u (n – 2) u … u(n – x) (n – (r – 1))
Such r - permutations of an n-set ;
p(n, r) = n(n – 1)(n – 2) (n – r) (n – r + 1)
If n > r this can be simplified as n(n - 1)n(-2).....(n - 2 + 2)(n - r +1)p(n, r) =1× 2× 3× ....×(n - r - 1)×(n - r) np(n, r) (n - r)
Subset of an n-set ; :-
Consider the set ^ a, b, c `. Let us ask how many subsets are there for this set. The
answer can be obtained by enumeration, and we find that these a re 8 such subsets:
, {a}, {b}, {0}, {a, b}, {a, c}, {b, c}, {a, b, c}
The answer can also be obtaine d using the product rule. We thin k of building up a
subset in steps, First, we think of either including element a or not. There are 2
choices. Then we either include element b or not. Thee are agai n 2 choice,
Finally, we either include element C or not. There are again 2 choices. The total
number of ways of building up the subset is, by the product rul e.
2 u 2 u 2 = 23 = 8
Similarly the number of subsets of a 4-set is 2 u 2 u 2 u 2 = 24 = 16 . Hence the
number of subsets of on n-set is n
nt i m e s22. . . . . . . .22uu u

2.7 Combinations
r-combinations :-
An r – combination of an n-set x is a selection of r-elements from th e set, which
means that order doesn’t matter, Thus, an r -combination is an r-element subset,
C(n, r) denotes the number of r-combinations of an n-set. For e xample the number
of ways to choose a committee of 3 from a set of 4 people is gi ven by C(4, 3) , If munotes.in

Page 52

52DISCRETE MATHEMATICSthe four people are Dewey, Evans, Grange and Howe, then the pos sible
committees are ^Dewey, Evans, Grange`, ^Howe, Evans, Grange`, ^ Dewey,
Howey, Grange`, ^Dewey, Evans, Howe`. Hence C(4, 3) = 4 Note that C(n, r)=0
if n < r , there are no r-combinations of an n-set in this case.
Theorem :
P(n, r) = C(n, r) u P(r, r)
Proof : An ordered arrangement of r-objects out of n can be obtained by first
choosing r-objects (this can be done in C(n, r) ways) and then ordering them (this
can be done in p(r, r) = r! ways)
Therefore by product rule, there are C(n, r) u P(r, r) such ordered arrangements of
r-objects out of n – objects
Corollary : n!C( n,r )r! (n r)!
Proof :- Since we know that
P(n, r) = C(n, r) u P(r, r) P( n, r ) p( n, r )C( n,r )p( n, r ) r !
But, we know that n!p( n, r )(n r) ! n!C( n,r )r! (n r)!
Corollary :- C(n, r) = C(n, n – r)
Proof :- n! n! n!
r! (n r)! (n r)!r! (n r)! [n (n r)]!
C(n, r) = C(n, n – r)
Note :- The number n!
r! (n r)! is often denoted by n
r and called the binomial
co-efficient
munotes.in

Page 53

53Chapter 2: Basic Principles of Counting2. Pascal’s Identity
C(n, r) = C(n – 1, r – 1) + C(n – 1, r)
Theorem :- n1 nn 1
rr 1 r

Proof :- Given an n-set X = {x1, x 2, …. xn}. Any r-combinations of this n-set ;
can be of either category.
1) containing x 1 as object or
2) not containing x 1, as object
There are n1
r1
r - c o m b i n a t i o n s o f n - e t ; c o n t a i n i n g x 1 and n1
r r -
combinations of n-set ;, not containing x 1.
Therefore by the sum rule, there are in all n1 n1
r1 r
r-combination of an
n-ser ;. n1 nn 1
rr 1 r

This is a combinatorial proof, relying on counting arguments. T his theorem can
also be proved by algebraic manipulation. Here is the proof. (n 1) ! (n 1) !C( n 1,r 1) (C( n 1,r )(r 1) ! [ (n 1) (r 1) ]! r! [ (n 1) r]! (n 1) ! (n 1) !
(r 1) ! (n r) ! r! (n r 1) ! r( n 1)! ( n r )( n 1)!
r! (n r)! r! (n r)! r( n 1)! ( n r )( n 1)!
r! (n r)! (n 1) ! (r n r)
r! (n r)! munotes.in

Page 54

54DISCRETE MATHEMATICSn( n 1 )! n!C( n,r )r! (n r)! r! (n r)!
A convenient method of computing the number C(n, r) is to use t he following
array

For example, C(5, 2) is given by summing the numbers 4 and 6. The above array
of binomial numbers is called as the Pascal’s triangle.
2. Binomial and Multinomial Coefficients
The number n!
r! (n r)! is denoted by n
r, which equals the number of r-
combinations of an n-set x. n
r n( n 1 )( n 2 )......( n r 1 )
r! i f r ! 0
1 if r ! 0
OCCUPANCY PROBLEM :
In the history of combinatorics and probability theory, problem s of placing balls
into cells or urns have played an important role such problems are called
occupancy problems. In this section, we consider the situation, w h e r e w e
distribute n-distinguishable balls into R-distinguishable cells . In particular, we
consider the situation where we distribute n 1 balls into the first cell, n 2 into the
second cell, nk into the kth cell. Let C(n, n 1, n2, , n k) denote the number of ways
this can be done. This number is also written as n
n, n, . . . . . . . , n12 k§·
¨¸©¹ and called the
multinational coefficient. Let us consider one example. The Uni versity Registrat’s
office is having a problem. It has 11 new students to squeeze i nto 4 sections of an
introductory course : 3 in the first, 4 in the second and third , and 0 in the forth. In munotes.in

Page 55

55Chapter 2: Basic Principles of Countinghow many ways this can be done " The answer is C(11, 3, 4, 4, 0) . Now there are 11
3 choices for the first section, for each of these choices there are 11 3 8
44
choices for the second section for each of these choices, ther e are 84
4 choices
for the third section and 0
0 choices for the fourth section. Hence, by the product
rule, the number of ways to assign section is
C(11, 3, 4, 4, 0) = C(11, 3) u C(8, 4) u C(4, 4) u C(0, 0)
= 11! 8! 4! 0!
3!8! 4!4! 4!0! 0!0!uuu
= 11!
3!4!4! (0! = 1)
Continuing with our example, suppose that suddenly, spaces in t he fourth section
become available. The registrar’s office now wishes to put 3 pe ople each into the
first, second and third sections and 2 into the fourth. In how many ways can this
be done " Of the 11 students, 3 must be chosen for the first se ction of the
remaining 8 student, 3 must be chosen for the second section, o f the remaining 5
students, 3 must be chosen for the third section finally, the remaining 2 must be
put into the fourth section. The total number of ways of making the assignments
is
C(11, 3, 3, 3, 2) = C(11, 3) u C(8, 3) u C(5, 3) u C(2, 2)
= 11! 8! 5! 2!
3!8! 3!5! 3!2! 2!0!uuu
C(11, 3, 3, 3, 2) = 11!
3!3!3!2!
Let us derive the formula for
C(n, n 1, n2, …, n k)
C(n, n 1, n2, …, n k)= C(n, n 1)u C(n – n1, n2) u C(n – n1 – n2, …, n k) u ……
u C(n – n1 – n2, …, n k–1,nk)
C(n, n 1, n2,…, n k) = 12 k 1
1k 1 k( n n n .... n )! n!.....n! ( n n ) n !( n n ... n )!
uuu
= 12 ! k 1 2 kn!
n !n !.....n !( n n n .....n )! munotes.in

Page 56

56DISCRETE MATHEMATICSTheorem
C(n, n 1, n2, …, n k) = 12 kn!
n! n! . . . . . n!
n = n 1 + n 2 + ...... +n k (0! = 1)
For example, an NHL hockey season consists of 82 games. The num ber of ways
the season can end in 41 wins, 27 losses and 14 ties is
C ( 8 2 , 4 1 , 2 7 , 1 4 ) 82!
41!27!14!
Note :- C(n, n 1, n2) = C(n, n 1)
The number of 5-digit numb ers consisting of two 2’s, two 3’s and one 1 is C(5, 2,
2, 1) 5!302!2!1!
2.10 Binomial and Multinomial Theorme :
In elementary algebra, the binomial theorem describes the algeb raic expansion of
powers of a binomial. According to the theorem, it is possible to expand the
power (x + y)n into a sum involving terms of the form axbyc, where the exponents
b, c are non negative integers with b + c n.
For example 44 3 2(x y) x 3x y 3x
x4 + 4x3y + 5x2y2 + 4xy3 + y4
The coefficient a in the term xbyc is known as the binomial coefficient n
b or n
c
Theorem :- (Binomial Expansion)
For n t 0
nnk n k
k0(x y) C (n ,k) x y
¦
nnk n k
k
k0xy
¦ munotes.in

Page 57

57Chapter 2: Basic Principles of CountingProof :-
n
nt i m e s(x y) (x y) (x y) (x y)

In multiplying out, we pick one term from each factor (x + y). Hence we only
obtain terms of the form xkyn–k. To find the coefficient of xkyn–k, to obtain xkyn–k,
we need to choose k of the terms from which we choose x. This c an be done in n
k ways.
In particular, we have
(x + y)2 22 2 22
012xx y y
x2 + 2xy + y2
(x + y)3 33 32 3 2 33
01 2 3xx y x yy
x3 + 3x2y + 3xy2 + y3
Let us give few of the applications of binomial theorem. The co efficient of x20 in
the expansion of (1 + x)30 is obtained by taking y 1 in the above theorem and n
30, we are looking for the coefficient of 110, x20, that is, 30 30
10 20C( 30,10 )
Theorem :- For n t 0, nn n n
01 n....... 2
Proof :- Note that 2n (1 + 1)n
Hence putting x y 1 in the binomial expansion we get
nnn k n k
k
k021 1
¦
nnn
k
k02
¦ munotes.in

Page 58

58DISCRETE MATHEMATICS nn n
01 n......
Theorem :- For n ! 0
nnn k n n n
012 k n...... ( 1) ..... ( 1) 0
Proof :-
nnn n k n k
k
k00( 1 1 ) ( 11 ) ( 1 ) 1
¦

nn n n
01 n0. . . . . ( 1 )
Corollary :- F o r n ! 0 nn nn
02 13..... .......
The interpretation of this corollary is that the number of ways to select on even
number of objects from n equals the number of ways to select an odd number.
The multinomial theorem says how to expand a power of a sum in terms of the
terms in the sum. It is the ge neralization of the Binomial expa nsion.
Theorem :- F o r a n y p o s i t i v e i n t e g e r m a n d a n y n o n - n e g a t i v e i n t e g e r n , t h e
multinomial formula tells us how a sum with m terms expands, wh en raised to an
arbitrary power n. k kk n n m 1212 m 12 m k, k, . . . . . . , k m12kk. . . k n12 m(x x . . . . . x ) x x x
§· ¨¸©¹¦
where n
k, k, . . . . . . , k m1212 mn!
k! k! . . . . . . . . . k !§· ¨¸©¹
Multinomial coefficient. The sum is taken over all combinations of nonnegative
integer.
In the case m 2, this statement reduces to that of Binomial t heorem.
For example, the third power of the trinomial x + y + z is give n by munotes.in

Page 59

59Chapter 2: Basic Principles of Counting(x + y + z)3 x3 + y3 + z3 + 3x2y + 3x2z + 3y2x + 3y2z + 3z2x + 3z2y + 6 xyz
x2y0x1 has coefficient 3
2,0,13!32!0!1!
x1y1x1 has coefficient 3
1,1,13!61! 1! 1!
Proof :-
This proof of the multinomial theorem uses the binomial theorem and induction
on m. For m 1, both sides equal n
1x.
Suppose the theorem hold for m. Then
(x1 + x 2 + ….. + x m + x m+1)n (x 1 + x 2 + ….. + x m + x m+1)n
k k nk 2 m1 1k, k, . . . . . . , k , k 1 2 m112 m 1kk. . . . k k n12 m 1xx x ¦
(By the Induction hypothesis)
Applying the Binomial theorem to the last factor, k kk m1 12xx x12 m 1 n
k, k, . . . . . . k , k12 m 1kk. . . . . k k n12 m r
¦
kkmm 1xxmm 1 k
k, kmm 1kk kmm 1
¦ kkk kk m1 m m1 12xx x x x12 m 1 m m 1 n
k, k, . . . k , k12 mm 1kk. . . k k n12 m rm 1
¦
The last step holds true, because nk n
k, k, . . . , k , k k , k k, k, . . . , k , k12 m 1 m m 1 12 m 1 m 1
In factorial notation, 12 m 1 mm 1 12 mm 1n! k! n!
k! k! . . . . k ! k !k ! k ! k! k! . . . . k ! k
Note :- The substitution of x 1 for all into munotes.in

Page 60

60DISCRETE MATHEMATICSk kk m 12xx . . . x12 m n
k, k, . . . . , k12 mkk. . . . k n12 m ¦
gives that n n
k, k, . . . . , k12 mkk. . . . k n12 m mt i m e s(1 1 ..... 1)
¦

mn
Let us see one of the applicati on of the multinomial theorem
Suppose that there are n objects,
n1 objects of type 1, n 2 objects of type 2, ….., n k objects of type k with
n1 + n 2 + ….. + n k n. Then the number of distinct permutations of these objects
is the multinomial co-efficient 12 k
12 kn!C( n,n ,n ,....n )n! n! . . . . . . n!
For instance, suppose that n = 3 and there are two type 1 objects, a and a and one
type 2 object b. Then there are 3! = 6 permutations of the three objects, but some
of these are indistinguishable.
ba, a 2 i s s a m e a s b a 2a1. Therefore there are only 3!32!1! distinguishable
permutations baa, aba aab, As an another example, there are 9!
3!1!1!2!1!1!
different words that can be formed using all letters of the wor d “excellent”.
2.11 Let Us Sum Up/Summary
1) The sum rate states that if thee are n, ways of performing t ask 1, n 2 ways of
performing task 2 and so on, nr ways of performing task r then either of these
r-tasks can be executed in n1 + n 2 + ….. + n r ways.
2) The product rule state that if there is procedure consisting o f p e r f o r m i n g r
different tasks together, if first task can be completed in n 1 ways, second task
can be completed in n 2 w a y s a n d s i m i l a r l y rth t a s k c a n b e c o m p l e t e d i n n r munotes.in

Page 61

61Chapter 2: Basic Principles of Countingways, all r-tasks are performed independent of each other. Then the procedure
can be performed in n1 u n2 u ….. u nr different ways.
3) Let n t r, then the number of r-permutations can be given by P(n, r)
n!P( n,r )(n r) !
4) The number of all subsets of an n-set ; is 2n.
5) The number of r – combinations of an n-set ; is given by C(n, r) and n!C( n,r )r! (n r)!
6) Pascal’s Identity :
nn 1n 1rr r1

7) Binomial co-efficient is denoted by nrn!C( n,r )r! (n r)! and multinomial
coefficient is denoted by C(n, n 1, n2,…n k)
n
12 k n, n, . . . . . . n12 k12 kn!C( n,n ,n ,....n )n! n! . . . . . . n!
8) Binomial Expansion :-
For n t 0
knk n xyn n
k
k0xy
¦
9) Multinomial Expansion
k kk m 12xx x12 m n n12 m k, k, . . . . , k12 mkk. . . . k n12 m(x x . . . . . x )
¦
10) The number of permutations of an n-number of objects with n 1 objects of type
1, n 2 objects of type 2, and n k objects of type k (n 1 + n 2 + …. + n k n) is
given by the multinomial co-efficient
12 k
12 kn!C( n,n ,n ,....n )n! n! . . . . . . n! munotes.in

Page 62

62DISCRETE MATHEMATICS2.12 Solved Numericals
1) There are 80 mathematics and 50 statistics books. How many w ays we can
pick either type of book "
S o l u t i o n : - One book, either of mathematics or statistics can be selected in 80
+ 50 = 130 ways (by the sum rule)
2) How many ways, we can select either a Heart card or a diamon d card from 52
playing cards "
Solution :- There are 13 Heart cards and 13 diamond cards. Therefore there
are 13 + 13 = 26 ways to pick a card of Heart or diamond. (by the sum rule)
3) At one time, a local telephone number was given by a sequenc e of two letters
followed by five numbers. How many different telephone numbers were
there"
Solution : - Using the product rule, there are 26 u 26 u 10 u 10 u 10 u 10 u 10
= 262 u 105 different telephone numbers available.
4) Show that in a graph G, the sum of degrees over all vertices is even.
Solution :- We count all the incidences between vertices are edges in two
ways. The number of edges incident with a vertex Q i s t h e d e g r e e o f Q,
denoted by d( Q). So basically, we want to know parity of ¦ d(Q). Since every
edge is incident with exactly two vertices, the sum of all degr ees is same as
twice the number if edges, Hence ¦ d(Q) is always an even number.
5) Let A, B be two finite nonempty sets then show that
AB A B AB
Solution :- Let A = {a 1, a2, ….., a m}
B = {b 1, b2, ….., b n} and ABr
exactly r of the ai’s and bj’s are same. Assume that
a 1 b 1, a2 b 2, ar b r
ABm n r
Am , Bn? & ABr
AB A B AB? munotes.in

Page 63

63Chapter 2: Basic Principles of Counting6) Find the total number of signals that can be made by five fl ags of different
color, when any number of them may be used in any signal.
Solution :-
Case 1 – When only one flag is used
N o . o f s i g n a l s m a d e 5p1 = 5
Case 2 – When only two flags are used
N o . o f s i g n a l s m a d e 5p2 = 5 u 4 = 20
Case 3 – When only three flags are used
N o . o f s i g n a l s m a d e 5p3 = 5 u 4 u 3 = 60
Case 4 – When only four flags are used
N o . o f s i g n a l s m a d e 5p4 = 120
Case 5 – When only five flags are used
N o . o f s i g n a l s m a d e 5p5 = 5! = 120
Hence, by the sum rule, the required number is
5 + 20 + 60 + 120 + 120 = 325
7) If there are 5 men and 6 women in how many ways a committee consisting of
four persons can be formed such that it contains atleast one wo man "
Solution :- A typical committee of four persons consisting of atleast one
woman will look like
1) one women, three men
2) two women, two men
3) three women, one man
4) All four women
T h e r e a r e 6C1 u 5C3 to form committee, of case 1 There are 6C2 u 5C2 ways to
form committee of Case 2, there are 6C3 u 5C1 ways to form committee of
Case 3 and 6C4 u 5C0 ways to form a committee of case 4. Therefore by the
sum rule, there are
6C1 u 5C3 + 6C2 u 5C2 + 6C3 u 5C1 + 6C4 u 5C0
D i f f e r e n t w a y s t o f o r m a c o m m i t t e e o f f o u r p e r s o n s c o n s i s t i n g of atleast one
women. munotes.in

Page 64

64DISCRETE MATHEMATICS8) Find nn
k
k1k
¦
Solution :- By Binomial theorem, we know that
nnn k n kk
k1(x 1) C x 1
¦
?? Differentiating with respect to x, we get
nn1 n k1k
k1n( x 1 ) C k x
¦
P u t t i n g x 1
nn1 nk
k1n( 1 1 ) k C
¦
T h e r e f o r e
n n1n2
k
k1kn
¦
9) What is the co-efficient of a3bc2 in the expansion of (a + b + c)6 "
S o l u t i o n : - By multinomial theorem, the coefficient of a3b1c2 in the expansion
of (a + b + c)6 is the multinomial coefficient
6
3,1,26!C(6,3,1,2 )3!1!2!
6 0
10) In a kennel that is short of space, 12 dogs must be put int o 3 cages, 4 in cage
1, 5 in cage 2 and 3 in cage 3. In how many ways can this be do ne"
Solution :- n 12, with n 1 4, n 2 5, n 3 3, n 1 dogs are of the same type, n 2
objects are of the same type and n 3 objects are of the same type. So, there are
12!C(12,4,5,3 )4!5!3! ways to put dogs into 3 cages.
munotes.in

Page 65

65Chapter 2: Basic Principles of Counting2.13 Unit end Excercises
1) How many bit strings have length 3, 4 or 5
(Hints :- Use sum rule, A bit string is made up of 0’s and 1’s)
2) In how many ways we can get a sum of 3 or a sum of 4, when t wo dice are
rolled" (Use sum rule).
3) How many ways are these to rank five potential basketball re cruits of different
heights if the tallest one must be ranked first and the shortes t one last"
4) A value function on a set A assigns 0 or 1 to each subset of A.
a) If A has 3 elements, how many different value functions are there on A"
b) What if A has n elements"
5) A company is considering 6 possible new computer systems and it ’s system
manager would like to try out at most 3 of them. In how many wa ys can the
systems manager choose the systems to be tried out"
6) Show that
nm m nm n nmro r r o 1r 1.....

7) How many different 11- letters words can be made from the le tters of the
word ABRACADABRA"
(Use multinomial theorem)
8) Find the co-efficient of a3bc4d2 in the expansion of (a + b + c + d)10. (Use
multinomial theorem)
9) Suppose there are 6 candidates for job interviews, how many different ways
are there for 2 of them to be interviewed on Monday, 2 on Wedne sday, and 2
on Saturday"
(Use multinomial theorem)

munotes.in

Page 66

66DISCRETE MATHEMATICS10) Let P n(k) denotes the number of permutations of the set {1, 2, …, n}, which
fixes exactly k numbers. Prove that
n
n
k0kP ( k ) n!
¦
(Hint - The LHS is the total number of fixed points in all nt i m e s( n! ( n 1)! ( n 1)! ..... ( n 1)! )
permutations of {1, 2, …, n}

munotes.in

Page 67

3
ADVANCE COUNTIN*
Unit Structure :
3.0 Objective
3.1 Introduction
3.2 Occupancy problems
3.3 Basic Combinatorial Numbers
3.4 Permutations of Sets with Indistinguishable Objects
3.5 Counting combinations with repetitions allowed
3.6 Partition of the integer
3.7 Summary
3.8 Unit end exercise
3.0 ObMective
After going through this chapter you can able to known that
x Different methods of counting problems.
x Occupancy problems.
x Different types of occupancy problems.
x Number of solutions of equation by using occupancy problems.
3.1 Introduction:
Combinatorics, which is also refer as combinatorial mathematics is the field of
mathematics consent with problems of selections, arrangement an d operation with
a finite or discrete system. Its objective is how to count with out ordinary
counting.one of the basic problem of Combinatorics is to determ ine the number of
possible configurations of objects of a given type. This chapte r includes 67Unit 1
munotes.in

Page 68

68DISCRETE MATHEMATICSnumerous quite elementary topics s uch as enumerating all permut ation or
combination of a finite set.
There are three essential problems in combinatorics. These are the existence
problem, the counting problem, and the optimization problem. Th is course deals
primarily with the first two in reverse order.
3.2 Occupancy problems:
The purpose of this ultimate section is to show that some basic counting exercises
can be re-phrased as so-called occupancy problems. A consequenc e will be that
we can easily introduce occupancy problems which are not amenab le to the
elementary tactics we have dealt with so far.
The basic occupancy problem has us placing n objects into k containers boxes.
To classify the type of occupancy problem we have, we must answ er three yesno
questions. There will therefore be 8
basic occupancy problems. The three
questions are:
1) Are the objects distinguishable from one another"
2) Are the boxes distinguishable from one another"
3) Can a box remain unoccupied"
If the answer to all three quest ions is yes, then the number of ways to place the n
objects in to the k boxes is clearly the number of functions from an n-set to a k-
set, which is
.
If, on the other hand the answer to the first question is no, b ut the other two
answers
are yes, then we have the ba sic donut Shoppe problem. So the nu mber of ways to
distribute n identical objects among k distinguishable boxes is the number of
solutions in non-negative whole numbers to

where
is the number of objects placed in the ith box.
If we change the answer to the third question to no, then we ha ve the more
realistic donut Shoppe problem. Now we need the number of solut ions in positive
integers to
o r e q u i v a l e n t l y t h e n u m b e r o f
solutions in non-negative integers to
. T h i s i s
C((n − k) + k − 1, n − k) C(n − 1, n − k) C(n − 1, k − 1). munotes.in

Page 69

69Chapter 3: Advance CountingSo it might appear that there is nothing really new here. That every one of our
occupancy problems can be solved by an elementary counting tech nique.
However if we define S(n, k) to be the number of ways to distribute n
distinguishable objects into k indistinguishable boxes we will defining 01(, ) (1 ) ( )k
in
ikSnk k ii k §·¨¸©¹¦
Upon making this definition we can answer three more of our eig ht basic
occupancy
problems. This is summarized in the table. ObMects
distinguished Box distinguished Empty box
allowed Number of ways
to complete <

<

N

N

<

< <

<

<

<

N

N <

N

<

N

<

N

The numbers S(n, k) are called the Stirling numbers of the second kind. The table
indicates their relative importan ce for counting solutions to o ccupancy problems.
3.3 Basic Combinatorial Numbers:
Let throughout this this chapter X stand for the n- set {1, 2, 3, ….., n } and A stand
for the m-set ^
`. Let X stands for a set of n distinct objects to be
distributed or sorted into the m boxes. Consider a map
. There are

such possible maps. Every such map allows several interpretatio ns. We can think
as munotes.in

Page 70

70DISCRETE MATHEMATICS 1 2 3 .................. (1) (2) (3) .................. ( )n
n II I I§·
¨¸©¹.
describes a way of sorting the n objects into the m boxes. Wit h this
interpretation, we says that the object j goes into the box
. This way of sorting
shall be called as combinatorial distribution or simply distrib ution.
General guideline for modeli ng distribution problems are:
Distributions of distinct objec ts are equivalent to arrangement s and distributions
of identical objects are equivalent to selections.
3.3.1 Basic Modals for distribution:
The distribution of n distinct objects into m distinct boxes an d the distribution of
n identical objects into m distinct boxes are the two basic mod als for distribution.
There are
distributions of the n distinct objects in m distinct boxes. a nd
distributions of the n-identical objects in m distinct boxes.
Theorem: Let M and N be two sets such that
and
. Then the
total number of function
equals

Proof: Let
and
.
Since the function is determined as soon as we know the value o f
for
a function
has the from 12 3
12 3 . . . . . . . . . . . . . . . . . . () () () . . . . . . . . . . . . . . . . . . ( )m
maa a a
fa fa fa fa§·
¨¸
©¹
Where ^`12 () , , . . . . . . ,infa bb b for 1imdd. As there is no restriction on the
function f, 1()fa has n choices 12,, . . . . . . ,n bb b.
Similarly 2()fa has n choices 12,, . . . . . . ,n bb b and so on. Thus the total number of
function

is ..........
nnn n m
mt i m e snuuu u o .
Example 1: How many ways are there to distribute four identical balls an d six
distinct balls into five distinct boxes" munotes.in

Page 71

71Chapter 3: Advance CountingSolution: There are
ways to distribute four identical balls
into five distinct boxes and
ways to put six distinct balls in five
distinct boxes. These processes are disjoint, and so there are
ways to distribute the four identical and six distinct
balls.
Example 2: H o w m a n y s o l u t i o n d o e s t h e f o l l o w i n g e q u a t i o n
have,
and
are non-negative integers"
Solution: We assume we have four types labeled
and
. There are
15 items or units (since we are looking for an integer solution ). Every time an
item (unit) is selected it adds one to the type it picked it up . Observe that a
solution corresponds to a way of selecting 15 items (units) fro m a set of four
elements. Therefore, it is equal to 1combinations with repetiti on allowed from a
set with four elements. we have

Example 3: How many different ways can we distribute n indistinguishable balls
into
k distinguishable boxes"
Solution: Every distribution of balls can be represented as a sequence o f bullets
and lines.
• • | • • • | • | • •
• • | • • • | | • ••
• • • • • • • • | | |
So putting n balls in to k boxes boils down placing k -1 vertical lines in a line of
n bullets.
There are total of n+k- 1 possible positions for the bars.
Hence there are 11
1nk nk
kn §· §· ¨¸ ¨¸©¹ ©¹ways of selecting k-1 positions.
So it can be done by 1 nk
n§·
¨¸©¹. munotes.in

Page 72

72DISCRETE MATHEMATICSThe number of ways to place n indistinguishable objects into k indistinguishable
boxes if no box is empty is the number of partitions of n into exactly k parts. If we
denote this by
, then we see that
2. Also
for all
positive integers n.
Meanwhile
is k > n . Finally
.
The final occupancy problem is to place n indistinguishable objects into k
indistinguishable boxes if some boxes may be empty. The number of ways this
can be done by

This is the number of partitions of n into k or fewer parts.
Example 4: D e t e r m i n e t h e n u m b e r o f w a y s o f p u t t i n g k indistinguishable balls
into n indistinguishable boxes with the restriction that no box is empty"
Solution: Since the balls are indistinguishable balls, the problem reduc es to
counting the number of balls in each box with the condition tha t no box is empty.
As the boxes are also indistinguishable, they can be arranged i n such a way that
the number of balls inside them are in non-increasing order. He nce, we have the
answer as S(k, n).
Example 5: Determine the number of ways to put k indistinguishable balls into n
indistinguishable boxes.
Solution: The problem can be rephrased as follows: “suppose that each box
already has 1 ball, i.e., initially, each of the n boxes are non-empty. Now let us
determine the number of ways of putting k i n d i s t i n g u i s h a b l e b a l l s i n t o t h e n
indistinguishable boxes that are already non- empty.” This new problem is same
as “in how many ways can k + n indistinguishable balls be put into n
indistinguishable boxes with the restriction that no box is empty”. Therefore, the
answer to our problem reduces to computing S(m + n, n ).
3.3 INDISTIN*UISHABLE BALLS IN INDISTIN*UISHABLE BO;ES:
Till now, we have been looking at problems that required arrang ing the objects
into a row. munotes.in

Page 73

73Chapter 3: Advance CountingThat is, we differentiated between the arrangements ABCD and BC DA. In this
section, we briefly study the problem of arranging the objects into a circular
fashion. That is, if we are arranging the four distinct chairs, named A,B,C and D,
at a round table then the arrangements ABCD and the arrangement BCDA are the
same. That is, the main problem that we come across circular ar rangements as
compared to problems in the previous sections is “there is no object that can truly
be said to be pla ced at the number 1 position”.
So, to get distinct arrangements at a round table, we need to f ix an object and
assign it the number 1 position and study the distinct arrangem ent of the other n −
1 objects relative to the object which has been assigned positi on 1. We will look
at two examples to understand this idea.
Example : Determine the number of ways to sit 8 persons at a round table .
Solution: Let us number the chairs as 1, 2, . . . , 8. Then, we can pick one of the
person and ask himher to sit on the chair that has been number ed 1. Then relative
to this person, the other persons (7 of them) can be arranged i n 7 ways. So, the
total number of arrangements is 7.
Example 7: Suppose we are now interested in making the 4 couples sit in a round
table.
Find the number of seating arrangements.
Solution: The 4 cohesive units can be arranged in 3 ways. But we can st ill have
the couples to sit either as “wife and husband” or “husband and wife’. He nce, the
required answer is 24. 3.
3.4 Permutations of Sets with Indistinguishable ObMects:
Let us now generalized the above example. Assume there are
objects with

indistinguishable objects of type 1,
objects of type 2
indistinguishable
objects of type
. The number of different permutations are

There are many ways to prove this result. For example, we know that there

permutations, but many of these permutations are the same since we have
munotes.in

Page 74

74DISCRETE MATHEMATICSclasses of indistinguishable objects. How many permutations are the same due to
indistinguishable objects. Obviously, there are
uch permutations of type
1,
of type 2,…..
of type
. Thus the result follows.
Balls-and-Urns Model
Finally, we consider throwing
distinguishable balls (objects) into

distinguishable urns (boxes).
Consider the following example. There are
balls, and three boxes. We want to
know in how many ways we can throw these
balls such that there are
balls in
the first box,
in the second box, and
balls in the third box. Of course, there
are
of ways putting
balls from a set of
balls into the first box. For
every such an arrangement, the remaining
balls can be thrown in
ways into the second box so that it contains
balls. Finally, the
last box will have
balls on
ways. Therefore, by the
multiplication rule we have
.
In general, let
distinguishable objects be thrown into
distinguishable boxes
with
objects in the ii th box,
Then, generalizing our example, we
obtain

ways to distribute these
n
objects among
k boxes.
Example : In how many ways we can distribute hands of 55 cards to each of
four players from the deck of 52 2 cards"
Solution: We may represent this problem as throwing 52 52 objects into four
boxes each containing 5 cards. since every hand has 4 cards, an d after the
distribution of 4.5 20 5 cards there remain 32 cards.
Thus the solution is
.
munotes.in

Page 75

75Chapter 3: Advance Counting3.5 Counting combinations with repetitions allowed:
There exists a bijection between any two of the following sets:
a. The set of increasing words of length n on m ordered letters,
b. The set of distributions of n non- distinct objects in to m dist inct boxes,
c. The set of combinations of m symbols taken n at a time, with re petitions
permitted.
The cardinality of each of these sets is
. The number is
taken to be 1 if either
m 1 or n 0.
Proof: Let
Be an increasing word of length n on m
ordered letters. In
repeated
times,
repeated
times, and so on. Now put
of the objects into the first box,
of the objects into the second box, and so on.
This process and its inverse give a bijection between the sets (a) and (b) of the
proposition. Since the word itself is a combination of the m sy mbols with
repetitions permitted according to a partition
of n , bijection
between (a) and (c) is established.
To calculate the number required, note that each distribution o f the n non-distinct
objects into the boxes according to a partition
of n , gives
n distributions of n-labeled objects into the boxes with the s ame partition.
Example : The Reserve bank of India print currency notes in denominatio ns of
Five Rupees, Ten Rupees, Twenty Rupees, Fifty Rupees, One Hun dred Rupees,
Five Hundred rupees and One Thousand Rupees. In how many ways a n it display
ten currency notes not necessarily denominations"
Solution: This problem is same as counting the combinations when repetit ions
are allowed. We need to find the number of 10 combinations of t he seven
denominations, with repetitions permitted. Hence the number of ways

munotes.in

Page 76

76DISCRETE MATHEMATICS3. Partition of the integer:
What remains now, is the distribut ion of n non-distinct objects into m non-distinct
boxes, with or without exclusion principle. With each such dist ribution for which
no box is empty, we can associate the m-tuple (
) satisfying
,
.
Such an m-tuple is called a partition of the integer n.
Notation: The number of partitions of the integer n into exactl y m classes is
denoted by

The partition above is usually written it as
without commas and
parentheses.
If
is a partition of n then we write it as
.

may be written as

Where
is the number of parts equal to
in ,
varying in {1, 2, 3,……}. This is
explained below, the partition, 4+3+3+2+2+1 of 15 may be writte n as 433221 or

Hence the number of distributions of n non-distinct objects in m identical boxes (
boxes could be empty or with more than one object) is
.
This is the total number of partitions of n into m or fewer par ts. If m n, this
number is denoted by
, the number of all partitions of the integer n.
Example 10: How many distinct partitions 7 into 4 parts"
Solution: The distinct partitions 7 into 4 parts are given by 4+1+1+1, 2+3+1+1,
2+2+2+1.
Hence
3.
Note: By convention, we let
and
0 whenever n ! m.
Example 11: Determine the number of ways of putting m indistinguishable b alls
into n indistinguishable boxes with the restriction that no box is empty" munotes.in

Page 77

77Chapter 3: Advance CountingSolution: Since the balls are indistinguishable balls, the problem reduc es to
counting the number of balls in each box with the condition tha t no box is empty.
As the boxes are also indistinguishable, they can be arranged i n such a way that
the number of balls inside them are in non-increasing order. He nce, we have the
answer as
.
Example 12: Determine the number of ways to put m indistinguishable balls into
indistinguishable boxes.
Solution: The problem can be rephrased as follows: “suppose that each box
already has 1 ball, i.e., initially, each of the n boxes are no n-empty. Now let us
determine the number of ways of putting m indistinguishable bal ls into the n
indistinguishable boxes that are already non- empty.” This new problem is same
as “in how many ways can m + n indistinguishable balls be put into n
indistinguishable boxes with the restriction that no box is empty”. Therefore, the
answer to our problem reduces to computing P(m + n, n).
3.7 Summary:
x There are three essential problems in Combinatorics.
x This is summarized in the table. ObMects
distinguished Box distinguished Empty box
allowed Number of
ways to
complete <

<

N

N

<

< <

<

<

<

N

N <

N

<

N

<

N

munotes.in

Page 78

78DISCRETE MATHEMATICS3. Unit end exercise:
1. Determine the number of ways of selecting r distinguishable obj ects from n
distinguishable objects when n ≥ r"
2. How many ways are there to distribute 20 distinguishable toys among 4
children so that each children gets the same number of toys"
3. In how many ways can m distinguishable balls be put into n
indistinguishable boxes, such that NO box is empty"
4. In how many ways can m distinguishable balls be put into n
indistinguishable boxes"
5. How many ways are there to distribute 8 balls into 6 boxes with the first 2
boxes collectively having at most 4 ball if:
a. The balls are identical.
b. The balls are distinct.
6. How many distinct ways are there to make a 5 letter word us ing the
ENGLISH alphabet
a. With ONL< consonants"
b. With ONL< vowels"
c. With a consonant as the first letter and a vo wel as the second letter"
d. If the vowels appear only at odd positions"
7. How many ways are there to distribute 20 distinguishable t oys among 4
children so that each childre n gets the same number of toys"
8. In how many ways can m distinguishable balls be put into n
indistinguishable boxes"
9. How many nonnegative integer sol utions are there to the equa tion

"
10. With repetition allowed and order counting, how many ways are there to
select r things from n distinguishable things"
munotes.in

Page 79

79Chapter 3: Advance Counting11. Determine the number of ways to sit 5 men and 7 women at a round table
with NO 2 men sitting next to each other"
12. Determine the number of ways to sit 8 persons, including R am and Shyam, at
a round table with Ram and Shyam NOT sitting diametrically oppo site to
each other"
13. Determine the number of ways to select 6 men from 25 men w ho are sitting
at a round table if NO adjacent men are to be chosen"
14. Find all partitions of 8 into four or fewer parts.
15. How many solutions in non-negative integers are there to x1 + x2 + x3 + x4
18 which satisfy 1 ≤ xi ≤ 8 for i 1, 2, 3, 4"

munotes.in

Page 80

4
ADVANCED COUNTIN* - II
Unit Structure :
4.1 Introduction
4.2 Objectives
4.3 Stirling
s number
4.3.1 Stirling
s number of second kind
4.3.2 Stirling
s number of first kind
4.4 Principle of Inclusion-Exclusion
4.4.1 Application to Derangement problems
4.5 Let Us Sum Up
4.6 Unit End Exercises
4.0 ObMectives
After going through this chapter you will be able to:
x define Stirling
s number of first and second kind
x solve problems based on Stirling
s numbers
x define the statement of Principle of inclusion-exclusion
x use inclusion-exclusion princip le to solve derangement problems
4.1 INTRODUCTION
In the previous chapter we have studied about distinguishable b alls put into
distinguishableindistinguishable boxes. Let :fX Y osuch that _;_ n and _ Y_
k.
Consider the problem of determining the number of ways of putti ng n
distinguishable balls into k indistinguishable boxes, w ith the condition that no box 80Unit 2
munotes.in

Page 81

81Chapter 4: Advanced Counting - IIremains empty. Let ; ^123,,,,n xxxx }` be the set of n balls. Since the boxes
are indistinguishable, we can assume that the number of balls i n each of the boxes
is in a non-increasing order. Let iXdenote the set of balls in the i-th box, 1ikdd. Then 12__ __ __k XX Xtt } tand 1k
i
iXX

. Since each box is non-
empty, ,f o r a l l 1iXi k Izd d. Thus, we have obtained a partition of the set ;,
consisting of n e l e m e n t s , i n t o k-parts, 12,, ,k XX X }. The number of required
ways here, is given by S(n, k), that is the Stirling number of second kind. We shall
see the formal definition i n the following section.
4.3 Stirling
s number
Let us recollect first the definition of a partition of a set. Let X be a non-empty
set. Then a partition 3 of X into k parts, is a collection of non-empty subsets X1,
X2,…,Xk , of X such that :
(i) I
ijXX
(ii) 1
k
iiXX
4.3.1 Stirling number of second kind:
Let __Xn . The number of partitions of the set X into k-parts is denoted by S(n,
k) and is called as Stirling number of the second kind .
Remark:
1. The number of partitions of a n-set into n-parts is 1.
2. The number of partitions of a n-set into 0 parts is 0.
3. The number of partitions of a n-set into k-parts with k ! n is also 0.
4. The above three can be summed as follows: 1i f
(, ) 0 i f 0
0i fnk
Snk k
kn
° ®
°! ¯ munotes.in

Page 82

82DISCRETE MATHEMATICSLemma: Let X and Y be two finite sets with _ X_ m and _ Y_ n. Then the total
number of onto functions f : X → Y is nS(m, n).
4.3.2 Stirling
s number of first kind
Definition : The Stirling number of first kind, denoted by s(n, k) is the number of
permutations of an n-set with precisely k cycles.
We define s(0, 0) 1 and s(0, k) 0 for k ! 0.
Several different notations for the Stirling numbers are in use . Stirling numbers of
the first kind are denoted with a small s, and those of the second kind with a
capital S. The Stirling numbers of the second kind are never negative, b ut those of
the first kind can be negative hence, there is a separate nota tion for the unsigned
Stirling numbers of the first kind.
4.4 Principle of Inclusion-Exclusion
Example 1: In a set S = {1, 2, 3, …, 100}, one out of every 7 is a multiple of 7,
so that the total number of multiples of 7 in S is 100
7ªº
«»¬¼ 14 (> x@ means the integer
part of x). Similarly, the total number of multiples of 3 in S is 100
3ªº
«»¬¼ 33.
The question now is, how many are multiples of 7 or 3"
Is the answer 14 + 33 47" Well, no. The reason is that 14 + 3 3 counts those
numbers twice which are multiples of 7 as well as of 3, for e.g. 21. How many
such numbers are there in S which are multiples of 7 and 3" They are 100
21ªº
«»¬¼ 4.
Hence the correct answer to the above question is 14 + 33 – 4 43.
Now, if we want to know how many numbers in S are not multiples of 7 or 3,
then we need to just subtract 43 from 100, i.e. 100 – 43 47 numbers in S are not
multiples of either 7 or 3.
Example 2: Let us consider another examp le. In a College there are:
x 28 students in Mathematics
x 30 students in Physics
x 24 students in Statistics munotes.in

Page 83

83Chapter 4: Advanced Counting - IIx 8 students in both Mathematics and Physics
x 16 students in both Physics and Statistics
x 5 students in both Mathematics and Statistics
x And 55 students in either Mathematics, Physics or Statistics
How many students are there in all three subjects in the Colleg e"

Such problems can be solved using the principle of Inclusion an d Exclusion
stated below:
Statement: Consider a set o f N o b j e c t s a n d a s e t o f n p r o p e r t i e s 12,, ,n DD} D.
Some of the N objects may have none of these properties. Some may have more
than one of these. Let 12()n NDD}Ddenote the number of objects having any of
the properties 12,, ,n DD} D and 12()n N ccD} D cDdenote the number of objects
having none of the properties 12,, ,n DD} D then, 12()n N ccD} D cD N – 12)( ) ( )(n N NND D } D + 12 3 11 )( () ( )nn NN N DD DD } D D
123 124 2 1() )( ) (nn n NN N DDD DDD } D D D
+ …
+ 12 (1 ) ( )n
n NDD}D
Thus, the solution to the Example 2 is
munotes.in

Page 84

84DISCRETE MATHEMATICS)( )( )( )( )( ) ) (( ) ( BC N A N B N C N AB N AC N BC N ABC NA
55 28 + 30 + 24 – 8 – 16 – 5 + ()NA B C ()NA B C 55 – 53 2
Remark: The proof of the principle of inclusion and exclusion can be do ne using
principle of mathematical induction on n.
Example 3 : In a sports club with 54 members, 34 members play cricket, 22 play
squash and 11 play chess. Of these 10 play cricket and squash, 6 play cricket and
chess and 4 play squash and chess. If 2 members play all the ga mes, find how
many play none of the games"
Solution: Let A: member playing cricket, B: member playing squash and C :
member playing chess.
We are given that, N 54, N(A) 34, N(B) 22, N(C) 11, N(A B) 10, N(AC)
6,
N(BC) 4 and N(ABC) 2.
We want to find ()NA B Cccc.
Now ()NA B Cccc N – N ( A ) – N(B) – N ( C ) + N ( A B ) + N ( A C ) + N ( B C ) –
N(ABC)
5 4 – 34 – 22 – 11 + 10 + 6 + 4 – 2
Thus ()NA B Cccc 5
Check your progress
1. Find the number of integers between 1 and 250, that are not div isible by 2, 3
and 5.
2. In a survey of students it was found that 80 students knew Mara thi, 60 knew
English, 50 knew Sanskrit, 30 knew Marathi and English, 20 knew English
and Sanskrit, 15 knew Marathi and Sanskrit and 10 knew all the three
languages. How many students knew:
(i) At least one language
(ii) Marathi only
(iii)English and one but not both English and Sanskrit munotes.in

Page 85

85Chapter 4: Advanced Counting - II3. Determine the number of primes not exceeding 100. (Hint: Observ e that
primes not exceeding 100 are those positive integers greater th an 1 and not
exceeding 100 which are not divisible by 2, 3, 5 or 7)
4.4.1 Application to Derangement problems
Definition : A derangement is a permutation of objects th at leaves no object in its
original position.
As an application of the principle of inclusion and exclusion, we will find a
formula for derangements of n s y m b o l s . L e t D n denote the number of
derangements on n symbols.
Theorem : The number of derangements of a set of n elements is :
1111 . . . ( 1 )1 2 31
n
nDnnªº «»¬¼
Proof: The total number of permutations on n symbols is n. So let N n.
For i = 1, 2, 3, …, n, let iDdenote the property that i occurs in its original place in
a permutation.
Thus, by definition of derangement and by principle of inclusio n-exclusion, we
have, 12()nnN D D D } Dcc c N – 12)( ) ( )(n N NND D } D + 12 3 11 )( () ( )nn NN N DD DD } D D
123 124 2 1() )( ) (nn n NN N DDD DDD } D D D
+ …+ 12 (1 ) ( )n
n NDD}D
( )
Now, N n 1()ND number of permutations in which 1Dis in its original place
n u m b e r o f p e r m u t a t i o n s i n w h i c h 1D is fixed
n u m b e r o f p e r m u t a t i o n s o n ( n – 1) symbols
( n – 1) munotes.in

Page 86

86DISCRETE MATHEMATICSThus, )( 1 )(i n N D for each i = 1, 2, 3, …, n.
Each such iDcan be selected from 123,,, ,n DDD} Din 1nCways.
Thus, 123)( )( ) ( )(n NN NNDDD } D 1nC(n – 1)
1n
Similarly, 12) (NDD number of permutations in which 1Dand 2D are fixed.
n u m b e r o f p e r m u t a t i o n s o n n – 2 symbols
Thus 12) (NDD (n – 2)
Each such pair can be selected from 123,,, ,n DDD} Din 2nC ways.
Thus, 12 3 1 1 (( )( ) )nn NN N DD DD } D D 2(2 ) nCn
2n
On the same lines we have, 123 4 12 12 (( )( ) )nn n N NN DDD DDD } D D D 3(3 ) 3n nCn
Substituting all such values in ( ), we get,
nD n –
1n +
2n –
3n + …+(1 )nn
n
Thus, Dn n111 11. . . ( 1 )1 2 3 n
nªº «»¬¼
Check your progress
A new employee checks the hats of n people visiting a restaurant, forgetting to
put claim check numbers on the hats. When customers return for their hats, the
checker gives them back hast chosen at random from the remainin g hats. What is
the probability that no one receives the correct hat" What is t he probability as n
tends to infinity" munotes.in

Page 87

87Chapter 4: Advanced Counting - II4.5 Let Us Sum Up
In this chapter we have seen learned about Stirling number of f irst and second
kind. Also we have seen principle of inclusion-exclusion and it s application to
derangement problems.
4. Unit End Exercises
1. In a class of 150 students 70 have opted Maths, 80 have opted P hysics and 90
have opted Stats. Of these
2. In how many ways can the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 be arranged so that
no even digit is in its original position"
3. How many derangements of ^1, 2, 3, 4, 5, 6` begin with the inte gers 1, 2, and
3 in some order"
4. n persons pick up their hats at random in a club. Show that the probability that
no one gets a right hat is 1 e as n tends to infinity.

munotes.in

Page 88

5
PI*EON-HOLE PRINCIPLE
Unit Structure :
5.1 Objectives
5.2 Introduction
5.3 Pigeon-hole Principle
5 . 3 . 1 T h e e x t e n d e d p i g e o n h o l e p r i n c i p l e
5.4 Strong form of pegionhole principle
5.5 Erdos-Szekeres theorem
5.6 Ramsey number
5 . 6 . 1 R a m s e y p a r t y p r o b l e m
5.7 Summary
5.8 Chapter End Exercise
5.9 References
5.1 ObMectives
After going through this chapter you will be able to:
x Pigeon-hole principle and its generalised.
x Application of pigeon-hole principle.
x Monotone subsequences and Erdos-Szekers theorem.
x Remsay number and its application.
5.2 Introduction
The pigeonhole principle is one of the most used tools in combi natorics, and one
of the simplest ones. It is applied frequently in graph theory, enumerative
combinatorics and combinatorial geometry. The pigeonhole princi ple seems
trivial and in some ways it is. So it’s astonishing that it can be used to solve such
a wide variety of interesting problems. This week we will focus on these kinds of 88Unit 2
munotes.in

Page 89

89Chapter 5: Pigeon-Hole Principleproblems. In practice, it is often quite easy to identify a pro blem as one requiring
the use of the pigeon hole principle. But it is often challengi ng to determine what
part of the problem should play the role of the pigeons and wha t should play the
role of the holes. here we are going to learn few application o f pegionhole
principle like Monotone subsequenc es in Erdos-Szekers theorem. and ramsey
number.
5.3 Pigeon-Hole Principle
We represent the basic principle of counting which is easily de rived and
extremely useful.
Statement:
If there n-pigeons to be placed in m-pigeonhole where mnd
. Then there is at
least one pigeonhole which receives more then one pigeon. Here is a simple
consequence of the pigeonhole principle.
In one set 13 or more people there are at least two whose birth days fall in the
same month. In this case we have to think of putting the people in to pigeonhole.
It can be January, February, March, and so no. Since there are 13 people and only
12 months (i.e. pigeonhole) one of the pigeonholes must contain at least two
people.
Theorem 5.3.1 :
Suppose n pigeons are placed into k holes. If nkG
then some hole contains more
than one pigeon.
Proof :
We prove the contra positive. Assume no hole contains more than one pigeon. Let 12 ka, a, . . . . , a
be the number of objects in each class. then 12 ka1 , a 2 , . . . . . , a 1dd d
.
Thus, the total number of objects, k
i12 k
i1na a a . . . . a 1 1 . . . . . 1 k
d ¦
.
Hence nik our assumption is wrong some hole contains more than one pigeon.
Note : The pigeonhole principle is also called the Dirichlet drawer p rinciple.
Example 1 :
If eight people are chosen in any way then show that atleast tw o of them are born
on the same day of a week. munotes.in

Page 90

90DISCRETE MATHEMATICSSolution:
Here each person (pigeon) is assigned the day of the week (pige onhole) on which
he and she was born since there are eight people and only seven days of the week,
the pigeonhole principal tells us that atleast two people must be assigned to the
same day.
Example 2 :
Consider the area shown it is bounded by a regular hexagon. Who se sides have
length 1 units" Show that if any seven points are chosen with i n this area then two
of them must be on further apart then 1 unit.
Solution:
Suppose that the area is divided in to six equilateral triangle s as shown in figure
1:1 If seven points are chosen we can assigned each one to a tr iangle that contains
it. If the point belongs to several triangles, assigns it arbit rarily to one of them.
The seven points one assigned to six triangles so by pigeonhole principal, at least
two points must belong to same triangle. These two can not be m ore then 1 unit
apart.
Example 3 :
Five points are located inside a square whose sides are of leng th 2 show that two
of the points are within a distance of each other.
Solution:
Divide up the square into four s quare regions of area 1 unit. A s indicated in figure
1.2. By pigeonhole principal, it follows that at least one of t his regions will
contain at least two points. The result now follows since two p oints in a square of
radius 1. Can not be further apart then length of the diagonal of the square is
which (by Pythagoras theorem).
Example 4 :
If any five numbers from 1 to 8 are chosen, then show that two of them will add
to 9.
Solution:
Constructs four different sets each contains two numbers that 8 to 9, as follows
A1 1, 8, A2 2, 7, A3 3, 6, A4 4, 5. Each of the five nu mbers chosen will munotes.in

Page 91

91Chapter 5: Pigeon-Hole Principlebe assigned to the set that contains it. Since there are only f our sets. The
pigeonhole principal tells that two of the chosen numbers will be assigned to the
same sets. These two numbers will add to 9.
Example 5 :
Fifteen children together 100 nuts. Prove that some pairs of ch ildren gathered the
same number of nuts.
Solution:
Now to prove that we use method of contradiction. Suppose all t he children
gathered a different number of nuts. Then the fewest total numb er is 0 + 1 + 2 + 3
+ 4 + 5 … + 14 = 105 but this is more then 100. Which is contradiction to our
assumption.
There for at least pair of children gathered same number of nut s.
Example :
Show that in any set of 10 integers there are at least pair of integers who have
same remainder when divided by 9.
Solution:
Set of 10 integers , when it divided by 9,lie in the same resid ue classes of modulo
9.i.e. the remainder is 0,1,2,3,4,5,6,7,8. Here there will be 9 remainder and 10
integers. There fore by pigeonhole principal, at least one inte ger has same
remainder.
Check Your Progress :
1. Show that for every integer n the re is a multiple of n that has only 0s and 1s in
its decimal expansion.
2. Show that if there are 30 students in a class, then at least tw o have last names
that begin with the same letter.
3. Show that among any group of five integers, there are two with the same
remainder when divided by 4.
4. Let T be an equilateral triangle whos e sides has length 1 unit. Show that if any
five points are chosen lying on insides T, then two of them wil l be more then1
2 unit apart.
5. Write the statement of pigeonhole principle and explain with on e example. munotes.in

Page 92

92DISCRETE MATHEMATICS6. There are n married couples. Out of the 2n people, how many hav e to be
chosen so that we choose a married couple"
7. In any group of n people there are at least two persons having the same
number friends.
5.3.1 The extended pigeonhole principle :
Theorem 5.3.2 :
If there are n pigeons assigned to m pigeonholes, then one of t he pigeon-hole
must contain at least n11mªº«»¬¼
pigeons.
Proof :
If each contain number more then n1
m pigeons, then there are at most n1 n1mn 1mmd
. A pigeon in all this contradicts our assumption. so one of
the pigeonholes must contain at least n11mªº«»¬¼
pigeond.
Example 7 :
Show that if 30 dictionaries in a library contains a total of 6 1,327 pages, then one
of the dictionaries must have at least 2045 pages.
Solution:
Let the pages be the pigeons and the dictionaries are te pigeon holes. Assigns each
to the dictionaries in which it appears then by the extended pi geonhole principle
are dictionaries must contain at least n1 6 1 , 3 2 7111 2 0 4 5m3 0ªº «»
¬¼
pages.
Example :
Show that if any 29 people are selected then one may choose sub set of 5. So that
all 5 were born on the same day of the week.
Solution:
Assign each person to the day of week on which ha and she was b orn. Then n
29 persons are being assigned to m 7 pigeonholes. By the exte nded pigeonholes
principle at least n1 2 9111 5m7
persons. munotes.in

Page 93

93Chapter 5: Pigeon-Hole PrincipleCheck Your Progress :
1. Show that if seven colours are used to paint 50 bicycles at lea st eight bicycles
must have the same colours.
2. In any group of 1500 people, Show that there are at least 5 per sons having the
same birthday.
3. There are 50 baskets of apple, Each baskets contain no more tha n 24 apples.
Show that there are at least 3 baskets containing the same numb er of apples.
4. 15 boys gathered 100 nuts. Prove that two of them gathered same number of
nuts.
5. Show that there must be atleast 90 ways t choose six integers f rom 1 to 15 so
that all the choices have the same sum.
6. How many friends must you have to guarantee atleast five of the m will have
birthdays in the same months"
5.4 Strong form of Pegionhole Principle
Theorem 5.4.1 :
Let 12 nq, q, . . . q
be a positive integers. If 12 nqq . . . q n 1
objects are put in
to the n-boxes, then either 1st box contain at least q 1 objects, 2nd box contain at
least q 2 objects , … , the nth box contain at least q n objects.
Proof :
Suppose it is not true that is, the ith box contain at most iq1
o b j e c t s , i1 , 2 , . . . . n
then the total number of objects contain in n boxes can be at m ost 12 n 1 2 nq1 q1. . .q 1qq . . . q n
. Which is one less then the
number of object distributed. This is a contradiction. The simp le from of
pigeonhole principle is obtai ned from the strong from by
taking12 nqq. . . q 2
. Then 123 nqqq. . . q n 1 2 n n 1 n 1
.
In elementary mathematics the strong from of pigeonhole princip le is most often
applied in the special case when 12 nqq. . . q r
. In this case pigeonholes
principle becomes : note :
x If n (r - 1) + 1 objects are put into n boxes, then at least on e box contain r or
more then r objects. munotes.in

Page 94

94DISCRETE MATHEMATICSx If the averages of n non-negative integers, 12 na .a ....a
is greater then r - 1
objects, then at least one of integer is greater then or equal to r.
Theorem 5.4.2 :
Given n integers 12 na .a ....a
not necessarily distinct, there crist integers k and l
with 0k1ndd
such that the sum k1 k2 1aa. . . . a
is multiple of n.
Proof :
Consider the n integers 11 21 2 3 1 2 na, a a, a a a, . . . . a a . . . . a
. Dividing these
integers by n we get 12 ii iaa. . . aq n r
where i0r n1 , i1 , 2 , 3 , . . . . ndd
. If
one of the remainder 12 nr,r,. . .r
i s z e r o , s a y kr0
i s m u l t i p l e o f n . I f n o n e o f 12 nr,r,. . .r
is zero, then two of them must have same say ktrr
w i t h kl
. This
means 12 kaa. . . a
and 12 taa. . . a
have the same remainder. Thus k1 k2 1aa. . . . a
is multiple of n.
Example
Show that among any n +1 numbers one can find two members so th at their
difference is divisible by n.
Solution:
Here, since there are only n possible remainder on divisible by n, and we have
n +1 member, by pigeonhole principal some two of them have same
remainder on division by n. Thus we can write this two as 11n nk r
and 22nn kr
where r is the remainder when division by n. 12 1 2 1 2 12nn n kr n krn kr n kr n kk
w h i c h i s d i v i s i b l e
by n.
Theorem 5.4.3 :
Let m and n be relative prime pos itive integer. then the system this xa m o d m{

and xb m o d n{
has a solution.
Proof :
We may assume that 0amd
and 0bnd
. Let us consider the n integers a, m a , 2m a , a, 3m a ,....
n 1 m a
. Each of these integers has munotes.in

Page 95

95Chapter 5: Pigeon-Hole Principleremainder a when divide by m. Suppose that two of them has same remainder r
when divide by n. Let the two number be im + a and jm + a where 0i j n1dd
. Then there are integers q j and q j such that im + a q jn + r and
jm + a q jn + r. Subtracting the first equation from the second, we get ( j - i) m
(qj - q i)n. Since the gcd (m, n) 1, we conclude that nji
. Npte that 0i j n1dd
. This is a contradiction. Thus the n integers a, (m a), (2m a), (3m a),....
(n 1) m a
have distinct remainder when
divide by n. That is each of the n numbers 0, 1, 2, 3, …, (n - 1) occur as a
remainder. In particular, the number b does. Let p be the integ er with 0 p (n 1)dd
such that the number x pm + a has remainder b when divide by n.
Then for some integer q, x qn + b. So x pm + a qn + b a nd x has the
required property.
Example 10. :
51 points are placed in an arbitr ary way, into a square of side 1. Prove that some 3
of these points can be covered by a circle of radius 1
7.
Solution:
Divide the square into 25 smaller squares of the side 1
5 then at least one of the
small square would contain at least 3 points. Indeed, if this i s not true then every
small square contains 2 points or less but the total number of points can not be
more then 2 x 25 50. This contradicts to the assumption that we have 51 points.
Now the circle circumvented around the square with the 3 points i n s i d e a l s o
contains these 3 points and has radius, 2 211 2 1 1 1r10 10 100 50 49 7§· ¨¸©¹
.
Check Your Progress :
1. Show that among any n + 1 positive integers not exceeding 2n th ere must be
an integer that divides on e of the other integers.
2. Prove that among any 52 integers, two can always be found such that the
difference of their squares is divisible by 100.
3. Prove that, given any 12 natural numbers, we can choose two of them and
such that their difference is divisible by 11. munotes.in

Page 96

96DISCRETE MATHEMATICS4. 2001 flies are inside the cube of side 1. Prove that 3 of them are within the
sphere of radius.
5. Show that among any 4 numbers one can find 2 numbers so tha t their
difference is divisible by 3.
5.5 Erdos-Szekeres Theorem
Let assume we have m people standing in a line. We want to ask u of them to
stand forward, such that, in the new line, if we look at them f rom left to right,
their height is monotone increasing. Namely, every person is ta ller than the
person to their left, and lower to the person to their right. O r alternatively, their
heights are monotonically decreasing, namely, every person is s horter than the
person to their left, and taller than to the person to their ri ght. What is the largest
u that we can nd such a subsequence"
Definition 1 :
Subsequence: A subsequence of a sequence of numbers 12 ma, a, . . . . , a
is a
sequence formed by selecting some of the elements of the sequen ce in the same
order as the original sequence. Formally, we have indices 12 k1i i . . .i m ,dd
and the subsequence is i1 i2 ika, a, . . . a
.
Definition 2 :
Monotone sequence: A sequence of numbers a 1, a 2, a 3, is monotonically
increasing if ii 1aad
for all i. Similarly, it is monotonically decreasing if ii 1aat
for all i. A sequence which is either monotonically decreasing or
monotonically increasing is ca lled a monotone sequence.
Theorem 5.5.1 :
Every sequence 2 123 n1a , a , a , ... a
of 2n1 real numbers contains either an
increasing subsequence of length n + 1 or a decreasing subseque nce of length n +
1.
Proof :
If 12 mb,b, . . . ,b
is a sequence, then i1 i2 ikb, b, . . . , b
is a subsequence, provided that 12 k1i i . . .i md
. Thus 2456b, b, b, b
i s a s u b s e q u e n c e o f 12 8b , b ,..., b
b u t munotes.in

Page 97

97Chapter 5: Pigeon-Hole Principle265b, b, b
i s n o t . T h e s u b s e q u e n c e i1 i2 ikb, b, . . . , b
i s i n c r e a s i n g i1 i2 ikb, b, . . . , b
and
decreasing if i1 i2 ikb, b, . . . , b
. Using contradiction method, we assume that there is
no increasing subsequence of length n + 1 and show that there m ust be a
decreasing subsequence of length n + 1. For each2k1 , 2 . . . . , n 1
, let kmbe the
length of the longest increasing subsequence that being with a k. Suppose kmnd

for each2k1 , 2 . . . . , n 1
, let km, so that there is no increasing subsequence of
length n + 1. Since km1t
for each 2k1 , 2 . . . . , n 1
, let km, the numbers 2 123 n1m, m, m, m
are 2n1
integers each between 1 and n. By the strong from of
the pigeonhole principle n + 1 of the number 2 12 n1m, m, m
are equal. Let mm. . . . mk1 k2 kn1

, where 2
12 n 1kk n 1 1k dd
. Suppose that for
some ki i 1 i1 , 2 , . . n , a a k
. Then, sinceii 1kK
w e c o u l d t a k e a l o n g e s t
increasing subsequence beginning with ki 1a. Since this implies that ki i 1mm k
,
we conclude that ki i 1aa k!
. Since this is true for each i1 , 2 , . . . . , n
, we have n1 ki i2 ka a ..... a
ttt
, and we conclude that n1 k1 k2 ka a ..... a
t
is a decreasing
subsequence of length n + 1.
Example 11 :
A Chess master who has 11 weeks to prepare for a tournament dec ides to play at
least one game every day but, order not to tire himself, he dec ides not to play
more than 12 games during any calendar weeks. Show that there e xist a
succession of consecutive days during which the chess master wi ll have played
exactly 21 games.
Solution :
Let a 1 be the number of games played on the first day, a 2 the total number of
games played on the firs t and the second day, a 3 the total number of games played
on first, second and the third day, and so on. Since at least o ne game is played in
each day, the sequence of numbers 123 7a, a, a, . . . a 7
is strictly increasing, that is 123 7aaa. . . a 7
. Moreover 1a1 :t
and since at most 12 games are played
during any one week there for 1a7 1 2 1 1 1 3 2t
. Thus 12 11a a . . .a 71 3 2d d
. Note that sequence 12 7a2 1 , a2 1 , . . . . . . a 7 2 1
is also
strictly increasing, and 12 7 12 1a 2 1a 2 1. . . .a 72 1d
each of these
between 1 to 153. It follows that two of them must be equal. Si nce munotes.in

Page 98

98DISCRETE MATHEMATICS12 7a, a, . . . . a7
are distinct and 12 7a2 1 , a2 1 , . . . . , a 7 2 1
a r e a l s o d i s t i n c t , t h e n
two equal member of must be from ia and ja 21
. Since the number of games
played on tihday is ijaa2 1
we conclude that on the day j + 1, j + 2, ….i the
chess master played total of 21 games.
5. Ramsey Number
Definition 3 :
The Ramsey number R(m, n) gives the solution to party problem, which asks the
minimum number of guests R(m, n) that must be invited so that a t least m will
know each other or at least n will not know each other.
By symmetry, it is true that R(m, n) R(n, m). It also must be true that R(m, 2)
m. A generalized Ramsey number is written 123 k Rm , m , m , . . . . , m n
and is the
smallest integer r such that, no matter how each n-element subs et of an r-element
set is colored with k colors, there exists an i such that there is a subset of sizein,
all of whose n-element subsets arei color. The usual Ramsey num bers are then
equivalent to R(m, n) R(m, n 2).
5..1 Ramsey party problem :
Given K there is n so large that is any party of at least n peo ple there is either a
set of K mutual friends or K mutual enemies. Of course we canno t know which
option will pertain since for some parties all might be friends or other might be
enemies. The statement above rather unwieldy, so we shall intro duce some
notation in our discussion we will write 12 nk , ko
. If n has the property that it
is so large that in any party of n people there are either k 1 mutual friends or k 2
mutual enemies.
Example 12 :
Assume that in a group of 6 people, each pair of individuals co nsists of two
friends or two enemies. Show that there are either 3 mutual fri ends or 3 mutual
enemies in the group.
Solution :
Let a be a any person. By the pigionhole principle, of the rema ining 5 persons,
either 3 or more are friends of a or 3 or more are enemies of a . When 5 object are
divided into two sets, therefore by generalization of pegionhol e principle, one of munotes.in

Page 99

99Chapter 5: Pigeon-Hole Principlethe set containedat least 532§· ¨¸©¹
elements. Suppose first that b, c and d are friends
of a. If any 2 of these persons are friends, these 2 and a from a group of 3 mutual
friends. If none of b, c and d are friends, then b, c and d fro m a group of mutual
enemies. The argument is similar if we suppose that b, c and d are enemies odf a.
5.7 Summary
Pegionhole principle: n pigeons are placed into k holes. If nkG
then some hole
contains more than one pigeon.
The extended pigeonhole principle: If there are n pigeons assig ned to m
pigeonholes, then one of the pigeonhole must contain at least n11mªº«»¬¼
pigeons.
Strong from of pegionhole principle: Let q 1, q2, ...q n be a positive integers. If q 1 +
q2.... + q n - n + 1 objects are put in to the n-boxes, then either 1st box contain at
least q 1 objects, 2nd box contain at least q 2 objects , …., the nth box contain at least
qn objects.
Erdos-Szekeres theorem and its application.
Ramsey number and its application in pegionhole principle.
5. Chapter End Exercise
1. 7.Given 8 different natural numbers, none greater than 15, show that at least
three pairs of them have t he same positive difference.
2. Show that every sequence of n2 + 1 distinct real numbers contains a
subsequence of length n + 1 that is either strictly increasing or decreasing.
3. During a month with 30 days a baseball team plays at least one 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.
4. Show that among any n +1 positive integers not exactly 2n there must be an
integers that divides one of the other integer.
5. Show hat given any set of 5 numbers, there are 3 numbers in the set whose
sum is divisible by 3. munotes.in

Page 100

100DISCRETE MATHEMATICS6. Prove that of any 10 point chosen within an equilateral triangl e of side length
1, there are two points whose distance apart is at mos t 1.3
7. Show that in a group of 10 people there are either a set of 3 m utual strangers
or a set of 4 mutual friends.
8. Prove that any 11 integers selected from the set 1, 2, …. , 100 there are at
least 2 integers say x and y that 0xy 1
.
9. Fifty-one points are scattered inside a square with a side of 1 meter. Prove that
some set of three of these points can be covered by a square wi th side length
equal to 20 centimeters.
10. Prove that among 52 natural numbers, one can find two numbers m and n
such that either the sum m + n or d ifference m n is divisible b y 100.
11. The digits 1, 2, …., 9 are divided in three groups. Prove that product of the
numbers in one of the groups must exceed 71.
12. Show that in a party there are always two persons who have shak en hands
with the same number of persons.
13. Show that if 6 points are placed in the plane and they are join ed with blue or
green segments, then at least two monochromatic triangles are f ormed with
vertices in the 6 points.
14. A class of 32 students is organized in 33 teams. Every team con sists of three
students and there are no identical teams. Show that there are two teams with
exactly one common student.
15. Give any sequence of mn + 1 distinct real numbers then prove th at there exist
either an increasing sequence of length m + 1 or decreasing seq uence of
length n + 1 or both.
16. Give any six integers in 1, 2,...., 10 prove that there exist a tleast two that adds
upto 11.
17. If (n + 1) numbers are picked from a1 , . . . . a2 n n , aF
then prove that
there are two numbers which are co-prime.
munotes.in

Page 101

101Chapter 5: Pigeon-Hole Principle18. There are 280 students in the class. Without knowing anybody’s b i r t h d a y ,
what is the largest value of n for which we can prove that at l east n students
must have been born in the same month"
19. From the integers 1, 2, 200, we choose 101 integers. Show that among the
integers chosen there are tw o such that one of them is divisibl e by the other.
20. Basket of fruit is being arranged out of apples, bananas, and o ranges. What is
the smallest number of pieces of fruits that should be put in t he basket in order
to guarantee that either there are at least 8 apples or at leas t 6 bananas or at
least 9 oranges"
5. References
V. Krishnamurthy: Combinatorics Theory and application, Affilia ted East-West
Press. Richard A. Brualdi: Introductory Combinatorics, John Wil ey and son.
A. Tucker: Applied Combinatorics, Oxford University press.
Kenneth Rosen : Discrete Mathematics and its application, Tata McGraw Hills.

munotes.in

Page 102

*ENERATIN* )UNCTION
Unit Structure:
6.1 Objectives
6.2 Introduction
6.3 Generating function
6.4 Exponential Generating Function
6.5 Use of generating functions for Solving homogeneous and No n-
homogeneous recurrence relations
6.6 Lets sum up
6.7 Unit End exercise
6.8 Refrence
.1 ObMectives
After going through this chapter students will be able to under stand:
x Ordinary generating Functions algebraic manipulations with powe r series
x Exponential Generating Functions algebraic manipulations with p ower
series
x Generating functions for counting combinations with and without
repetitions.
x Applications to counting, use of generating functions for solvi ng
homogeneous and non-homogeneous recurrence relations.
.2 Introduction
The concept of a generating function is one of the most useful and basic concepts
in the theory of combinatorial enumeration. The power of the ge nerating function
rests upon its ability not only to solve the kinds of problem w e have considered so 102Unit 3
munotes.in

Page 103

103Chapter 6: Generating Functionfar but also to aid us in new situa tions where additional restr ictions may be
involved.
Now we see some important polynomial expansions, which are ofte n used in this
chapter. Polynomial Identities:
i) ଵି௫೙శభ
ଵି௫ൌͳ൅ݔ൅ݔଶ൅ݔଷ൅ڮǥǥ൅ݔ௡
ii) ଵ
ଵି௫ൌͳ൅ݔ൅ݔଶ൅ݔଷ൅ڮǥǥǤ
iii) ሺͳ൅൅ݔሻ௡ൌͳ൅ቀ݊
ͳቁݔ൅ቀ݊
ʹቁݔଶ൅ڮǥǥǤ൅ቀ݊
݊ቁݔ௡
iv) ሺͳെݔ௠ሻ௡ൌ ͳെቀ݊
ͳቁݔ௠൅ቀ݊
ʹቁݔଶ௠െڮǥǥǤ൅ሺെͳሻ௡ቀ݊
݊ቁݔ௡௠
v) ଵ
ሺଵି௫ሻ೙ൌͳ൅ቀͳ൅݊െͳ
ͳቁݔ൅ቀʹ൅݊െͳ
ʹቁݔଶ൅
ڮǥǥǤǤ൅ቀݎ൅݊െͳ
ݎቁݔ௥൅ڮ
vi) If ݄ሺݔሻൌ݂ሺݔሻ݃ሺݔሻ where ݂ሺݔሻൌܽ଴൅ܽଵݔ൅ܽଶݔଶ൅ڮǥ and
݃ሺݔሻൌܾ଴൅ܾଵݔ൅ܾଶݔଶ൅ڮǥ then
݄ሺݔሻൌܽ଴ܾ଴൅ሺܽଵܾ଴൅ܽ଴ܾଵሻݔ൅ሺܽଶܾ଴൅ܽଵܾଵ൅ܽ଴ܾଶሻݔଶ൅ڮǥǥ൅
ሺܽ௥ܾ଴൅ܽ௥ିଵܾଵ൅ǥǥ൅ܽ ଴ܾ௥ሻݔ௥൅ڮǤ
.3 *enerating function
Letܽ଴ǡܽଵǡܽଶǡǥǥǥ be a sequence of real numbers. The function
݃ሺݔሻൌܽ଴൅ܽଵݔ൅ܽଶݔଶ൅ڮǥǥൌ σܽ௜ݔ௜ ஶ
௜ୀ଴
is called the ordinary generating function or generating functi on for the given
sequence.
Example 1: Generating function for the binomial theorem.
Solution: For any ܼא݊ାǡ
ሺͳ൅ݔሻ௡ൌቀ݊
Ͳቁ൅ቀ݊
ͳቁݔ൅ቀ݊
ʹቁݔଶ൅ڮǥǤ൅ቀ݊
݊ቁݔ௡ǡ
So ሺͳ൅ݔሻ௡ is the generating function for the sequence
ቀ݊
Ͳቁǡቀ݊
ͳቁǡቀ݊
ʹቁǡǥǥǤǤǡቀ݊
݊ቁǡͲǡͲǡͲǡǤǤǤ
݂ሺݔሻൌ ሺͳ൅ݔሻ௡ is the generating function for ܽ௥ൌܥሺ݊ǡݎሻǡ the number of ways
to select an r-subset from an n-set. munotes.in

Page 104

104DISCRETE MATHEMATICSExample 2: Generating function for Maclaurian series.
Solution: For any ܼא݊ାǡ the Maclaurin series expansion for ሺͳ൅ݔሻି௡ is given
by
ሺͳ൅ݔሻି௡ൌͳ൅ሺെ݊ሻݔ൅ሺെ݊ሻሺെ݊െͳሻݔଶ
ʹǨ൅ڮǥǤǤ
ൌͳ൅෍െ݊ሺെ݊െͳሻሺെ݊െʹሻǥǤሺെ݊െݎ൅ͳ ሻ
ݎǨݔ௥ஶ
௥ୀଵ
ൌ ෍ሺെͳሻ௡ቀ݊൅ݎെͳ
ݎቁݔ௥ஶ
௥ୀ଴
Hence ሺͳ൅ݔሻି௡ൌቀെ݊
Ͳቁ൅ቀെ݊
ͳቁݔ൅ቀെ݊
ʹቁݔଶ൅ڮǥǤǤൌ σቀെ݊
ݎቁݔ௥ ஶ
௥ୀ଴ .
This generalizes the binomial theorem and shaws that ሺͳ൅ݔሻି௡ is the generating
function for the sequence ቀെ݊
Ͳቁǡቀെ݊
ͳቁǡቀെ݊
ʹቁǡǥǥǤ
Example 3 : Generating function for a sequence.
Solution: For any ܼא݊ା, ሺͳെݔ௡ାଵሻൌሺͳെݔሻሺͳ൅ݔ൅ݔଶ൅ڮǥǥ൅ݔ௡ሻǤ
So ൫ଵି௫೙శభ൯
ሺଵି௫ሻൌሺͳ൅ݔ൅ݔଶ൅ڮǥǥ൅ݔ௡ሻǡ and ൫ଵି௫೙శభ൯
ሺଵି௫ሻ i s t h e g e n e r a t i n g
function for the sequence 1,1,1,…….,0,0,0……, where the first n+1 terms are 1.
Extending the above example we find that ͳൌሺͳെݔሻሺͳ൅ݔ൅ݔଶ൅ڮǥǥ൅
ݔ௡ሻǡ
So ଵ
ሺଵି௫ሻ , is the generating function for the sequence 1,1,1,…..
Note: ଵ
ሺଵି௫ሻൌͳ൅ݔ൅ݔଶ൅ڮǥǥ is valid for all real x where ȁݔȁ൏ͳ Ǣ it is for
this range of values that the geometric series ͳ൅ݔ൅ݔଶ൅ڮǥǥ c o n v e r g e s .
However convergence is not the main idea of this concept.
Consider the formal expansion of ሺͳ൅ݔሻଷൌሺͳ൅ݔሻሺͳ൅ݔሻሺͳ൅ݔሻ

ൌͳ ͳ ͳ൅ͳ ͳ ݔ൅ͳ ݔ ͳ൅ͳ ݔݔ ൅ݔ ͳ ͳ൅ݔ ͳ ݔ൅ݔݔ ͳ൅ݔݔݔ
This formal expansion lists all ways of multiplying a term in t he first factor times
a term in the second factor times a term in the third factor. munotes.in

Page 105

105Chapter 6: Generating FunctionThe problem of determining the coefficient of ݔ௥ in ሺͳ൅ݔሻଷ, and more generally
in ሺͳ൅ݔሻ௡ǡ reduce to the problem of counting the number of different form al
products with exactly ݔݎ’s and ሺ݊െݎሻ 1’s. So the coefficient of ݔ௥ in ሺͳ൅ݔሻଷ
is ܥሺ͵ǡݎሻǡ and in ሺͳ൅ݔሻ௡ is ܥሺ݊ǡݎሻǤ
The following examples illustrate the use and efficiency of gen erating functions
to solve combinatorial problems.
Example 4 : Determine the number of ways to select 4-letter combination f rom
the set ^ A,B,C` if A can be included at most once, B at most t wice, and C at
most three times.
Solution: The list of all possible combinations is:
^C.B,B,A`, ^C,C,B,B`, ^C,C,B,A`, ^C,C,C,A`, ^C,C,C,A`
This situation can be modeled with a generating function by exp ressing each
letter’s possibilities with a polynomial.
(1+A) represents A occurring 0 times or 1 time. ሺͳ൅ܤ൅ܤଶሻ represents B
occurring 0,1, or 2 times. ሺͳ൅ܥ൅ܥଶ൅ܥଷሻ represents C occurring 0, 1, 2, or 3
times.
Then the expansion ሺͳ൅ܣሻሺͳ൅ܤ൅ܤଶሻሺͳ൅ܥ൅ܥଶ൅ܥଷሻ w i l l l i s t a l l t h e
ways to create
K-element sets with A or B or C with the constraints of the pr oblem.
Since the problem does not require all the possibilities, we us e the generating
function ሺͳ൅ݔሻሺͳ൅ݔ ൅ݔଶሻሺͳ൅ݔ൅ݔଶ൅ݔଷሻ to find the number of ways to
select a 4-letter combination. Expanding the above product, we get ͳ൅͵ݔ൅
ͷݔଶ൅͸ݔଷ൅ͷݔସ൅͵ݔହ൅ݔ଺. The coefficient of the term ݔସǡ 5 represents the
number of ways to select 4- element set under the given conditi on of the problem.
Example 5: Using a generating function modal the problem of counting all
selections of six objects chosen from three types of objects wi th repetition of upto
four objects of each type.
Solution: This problem can be modeled as the number of integer solution to
݁ଵ൅݁ଶ൅݁ଷൌ͸ ǡ Ͳ൑݁ ௜൑Ͷ Ǥ
This problem does not ask for the general solution of the ways to select ݎ objects.
This problem requires the coefficient of ݔ଺, that is the ways of ݔ௘భݔ௘మݔ௘యcan
equal ݔ଺. munotes.in

Page 106

106DISCRETE MATHEMATICSThus the desired generating function is ሺͳ൅ݔ ൅ݔଶ൅ݔଷ൅ݔସሻଷ a n d t h e
coefficient of ݔ଺ in the expansion gives the required result.
Example : In how many ways 25 identical pens can be distributed among f our
children.
Solution: We can model the above problem as the number of integer soluti ons for
the equation ܿଵ൅ܿଶ൅ܿଷ൅ܿସൌʹ ͷ if Ͳ൑ܿ௜ for all ͳ൑݅൑Ͷ ǫ
For each child the possibilities can be described by the polyno mial ͳ൅ݔ൅ݔଶ൅
ڮǥǤǤ൅ݔଶହǤ T h e n t h e a n s w e r t o t h i s p r o b l e m i s t h e c o e f f i c i e n t o f ݔଶହ i n t h e
generating function
݂ሺݔሻൌ ሺͳ൅ݔ ൅ݔଶ൅ڮǤ൅ݔଶହሻସǤ
The answer can also be obtained as the coefficient of ݔଶହ in the generating
function
݂ሺݔሻൌ ሺͳ൅ݔ ൅ݔଶ൅ڮǤ൅ݔଶହ൅ݔଶ଺൅ڮǤǤሻସ
Note that if the distribution is to only one child then the gen erating function is
݂ሺݔሻ ൌ ͳ൅ݔ ൅ݔଶ൅ڮǤ൅ݔଶହ.
Example 7: At a small shop, pencils sell for Rs. 2 and pen for Rs. 3. For r rupees,
how many different ways can pens and pencils be ordered"
Solution: For 8 rupees, we note that there are two orders that can be pl aced:
i) One pencil and two pens or
ii) Four pencil and no pen
A generating function that provides a solution is
ሺͳ൅ݔଶ൅ݔସ൅ݔ଺൅ڮǥǤǤሻሺͳ൅ݔଷ൅ݔ଺൅ݔଽ൅ڮǥǥǤሻ
Whose expansion is
ͳ൅ݔଶ൅ݔଷ൅ݔସ൅ݔହ൅ʹݔ଺൅ʹݔ଻൅ʹݔ଼൅ʹݔଽ൅ʹݔଵ଴൅ʹݔଵଵ൅͵ݔଵଶ൅
ʹݔଵଷ൅͵ݔଵସ൅͵ݔଵହ൅ڮǥǥǤǤ
The coefficient of ݔ௥ i n t h e a b o v e e x p a n s i o n g i v e s t h e n u m b e r o f o r d e r s f o r r
rupees.
munotes.in

Page 107

107Chapter 6: Generating Function.3.1Calculating coefficients of generating functions:
When determining the sequence generated by a generating functio n, you will
want to get a formula for the ݊௧௛ term (that is, for the coefficient of ݔ௡), rather
than just computing numerical v alues for the first few coeffici ents.
ሺͳ൅ݔሻିଵൌͳ൅ݔ൅ݔଶ൅ݔଷ൅ڮǥǥǥ
The second fact above says that ଵ
ଵି௫ is the generating function for the sequence 1,
1, 1, 1,.... It also lets you determine the sequence gen erated by many other
functions.
Theorem : The coefficient of ݔ௥ in the power series ଵ
ሺଵା௫ሻ೙ is ሺെͳሻ௥ቀ݊൅ݎെͳ
ݎቁ.
Proof: G i v e n p o w e r s e r i e s ଵ
ሺଵା௫ሻ೙can be written as ሺͳ൅ݔሻି௡. To avoid the
minus signs we shall consider ሺͳെݔሻି௡Ǥ
ሺͳ൅ݔሻିଵൌͳ൅ݔ൅ݔଶ൅ݔଷ൅ڮǥǥǥ
It follows that ሺͳ൅ݔሻି௡ is the product of n factors,
ሺͳ൅ݔሻି௡ൌ ሺͳ൅ݔ ൅ݔଶ൅൅ڮሻ(ͳ൅ݔ൅ݔଶ൅ݔଷ൅ڮሻǥሺͳ൅ݔ ൅ݔଶ൅ݔଷ൅
ڮǤሻ݊times.
Now we have to show that the coefficient of ݔ௥ in the product of these n factors
is equal to the number of un-order selections of r of n factors, with repetition
allowed.
Suppose that each factor has a Marker, initially positioned at the term 1, and that
we make an un-order selection, with repetition, of size r from the n factors.
Each time a particular factor is selected we move its marker to the next term, So
that if that factor is selected i times in all the marker will finish up at ݔ௜Ǥ
Thus for each one of the ቀ݊൅ݎെͳ
ݎቁ p o s s i b l e s e l e c t i o n s w e o b t a i n a s e t o f
marked terms, one from each factor, with total exponent n.
So the coefficient of ݔ௥ is ቀ݊൅ݎെͳ
ݎቁǤ
Replacing x by –x we get,
The coefficient of ݔ௥ in the power series ଵ
ሺଵା௫ሻ೙ is ሺെͳሻ௥ቀ݊൅ݎെͳ
ݎቁ. munotes.in

Page 108

108DISCRETE MATHEMATICSExample : Find the coefficient of ݔହ in ሺͳെʹݔሻି଻Ǥ
Solution: Using generating function for Maclaurin series, we write
ሺͳെʹݔሻି଻ൌሺ ͳ൅ݕ ሻି଻ൌσቀെ͹
ݎቁሺെʹݔሻ௥ ஶ
௥ୀ଴ where ݕൌെ ʹ ݔ Ǥ
Consequently, the coefficient of ݔହ is
ቀെ͹
ͷቁሺെʹݔሻହൌሺെͳሻହቀ͹൅ͷെͳ
ͷቁሺെ͵ʹሻൌ͵ ʹቀͳͳ
ͷቁൌͳ Ͷ ǡ ͹ ͺ Ͷ Ǥ
Example : Find the coefficient of ݔଵ଺ in ሺݔଶ൅ݔଷ൅ݔସ൅ڮǤሻହǤAlso find the
general coefficient . i.e. the coefficient of ݔ௥Ǥ
Solution: To simplify the expression, we extract ݔଶ from each polynomial factor
and then apply the polynomial identity.
ሺݔଶ൅ݔଷ൅ݔସ൅ڮǤሻହൌሾݔଶሺͳ൅ݔ൅ݔଶ൅ڮǤǤሻሿହ
ൌሾݔଵ଴ሺͳ൅ݔ൅ݔଶ൅ڮǤǤሻହሿൌݔଵ଴ଵ
ሺଵି௫ሻఱ
Thus the coefficient of ݔଵ଺ in ሺݔଶ൅ݔଷ൅ݔସ൅ڮǤሻହ i s t h e c o e f f i c i e n t o f ݔଵ଺
inݔଵ଴ሺͳെݔሻିହ .
But the coefficient of ݔଵ଺ in this letter expression will be the coefficient of ݔ଺ in
ሺͳെݔሻିହǤ i.e. the ݔ଺ term in ሺͳെݔሻିହ is multiply by ݔଵ଴ to become the ݔଵ଺
term in ݔଵ଴ሺͳെݔሻିହ.
From the polynomial identity
ଵ
ሺଵି௫ሻ೙ൌͳ൅ቀͳ൅݊െͳ
ͳቁݔ൅ቀʹ൅݊െͳ
ʹቁݔଶ൅
ڮǥǥǤǤ൅ቀݎ൅݊െͳ
ݎቁݔ௥൅ڮ
We see that the coefficient of ݔ଺ in ሺͳെݔሻିହൌቀ͸൅ͷെͳ
͸ቁൌʹ ͳ Ͳ Ǥ
More generally, the coefficient of ݔ௥ i nݔଵ଴ሺͳെݔሻିହ e q u a l s t h e c o e f f i c i e n t o f
ݔ௥ିଵ଴ in ሺͳെݔሻିହ is ቀሺݎെͳͲሻ൅ͷെͳ
ݎെͳͲቁǤ
Proposition: In how many ways can we select, with repetition allowed, r objects
from n distinct objects"
Proof: To prove this we need the following identity. munotes.in

Page 109

109Chapter 6: Generating Functionͳ
ሺͳെݔሻ௡ൌͳ൅ቀͳ൅݊െͳ
ͳቁݔ൅ቀʹ൅݊െͳ
ʹቁݔଶ൅ڮǥǥǤǤ൅ቀݎ൅݊െͳ
ݎቁݔ௥
൅ڮ
ൌ෍ቀ݊൅ݎെͳ
ݎቁݔ௥ஶ
௥ୀ଴
Now coming to our main result, the possible choices for the obj ect to choose
namely, none, one, two, ….. ሺݎ ൌ Ͳǡͳǡʹǡ͵ǡǥǤሻ are nothing but the coefficients of
powers of corresponding ݔ’s in the geometric series ͳ൅ݔ൅ݔଶ൅ڮǥ for each
of n distinct objects.
Considering all of the n dist inct objects, the generating funct ion is
݃ሺݔሻൌሺͳ൅ݔ൅ݔଶ൅ڮሻ௡ǡ
And the required answer is the coefficient of ݔ௥ in ݂ሺݔሻ. Now using the above
identity we have
ሺͳ൅ݔ൅ݔଶ൅ڮሻ௡ൌ൬ͳ
ሺͳെݔሻ൰௡
ൌͳ
ሺͳെݔሻ௡ൌ෍ቀ݊൅ݎെͳ
ݎቁݔ௥ஶ
௥ୀ଴
Therefore the coefficient of ݔ௥ is ቀ݊൅ݎെͳ
ݎቁ.
Example 10: How many ways are there to distribute 25 identical balls into Seven
distinct boxes if the first box ca n have no more than 10 balls but any number can
go into each of the other Six boxes"
Solution: The generating function for the number of ways to distribute r balls into
seven boxes with at most 10 balls in first box is
݄ሺݔሻ ൌ ሺͳ൅ݔ ൅ݔଶ൅ڮ൅ݔଵ଴ሻሺͳ൅ݔ൅ݔଶ൅ڮሻ଺
ൌሺͳെݔଵଵሻሺͳെݔሻି଻
By the identity (1) and (2)
Let ݂ሺݔሻൌ ሺͳെݔଵଵሻ and ݃ሺݔሻൌሺͳെݔሻି଻
Using identity (5) , we have
݃ሺݔሻൌሺͳെݔሻି଻
ൌͳ൅ቀͳ൅͹െͳ
ͳቁݔ൅ቀʹ൅͹െͳ
ʹቁݔଶ൅ڮǥ൅ቀݎ൅͹െͳ
ݎቁݔ௥
൅ڮ munotes.in

Page 110

110DISCRETE MATHEMATICSWe need the coefficient of ݔଶହ ( 2 5 b a l l d i s t r i b u t e d ) i n ݄ሺݔሻൌ ݂ሺݔሻ݃ሺݔሻ . We
need to consider only the terms in the product of the two polyn omials ሺͳെݔଵଵሻ
and ሺͳെݔሻି଻ that yields an ݔଶହ term. The only nonzero coefficients in ݂ሺݔሻൌ
ሺͳെݔଵଵሻ are ܽଵൌͳ and ܽଵଵൌെ ͳ. So the coefficient of ݔଶହ in ݂ሺݔሻ݃ሺݔሻ is
ܽ଴ܾଶହ൅ܽଵଵܾଵସൌͳൈቀʹͷ൅͹െͳ
ʹͷቁ൅ሺെͳሻቀͳͶ൅͹െͳ
ͳͶቁൌ͸ ǡ ͻ ͹ ǡ ͷ ʹ ͳ
Example 11: Find the number of ways to collect 15 rupees from 20 distinct
people if each of the 19 people can give a rupee (or nothing) a nd the twentieth
person can give a 1-rupee or 5-rupees (or nothing).
Solution: This collection problem is equivalent to finding the number of integer
solutions to
ݔଵ൅ݔଶ൅ڮǥǤ൅ݔ ଶ଴ൌʹ Ͳ
Where each ݔ௜represents the ݅௧௛ person,
When ݔ௜ 0 or 1, and the corresponding polynomial expression is
ሺͳ൅ݔሻଵଽ
݅ൌͳ ǡ ʹ ǡǥǥͳ ͻ and ݔଶ଴ൌͲ ǡͳ ݎ݋ ͷ and the corresponding polynomial is
ͳ൅ݔ൅ݔହǤ
The answer is the coefficient of ݔଵହ in the generating function of the product of
ሺͳ൅ݔሻଵଽ and ሺͳ൅ݔ ൅ݔହሻ,
݄ሺݔሻൌሺͳ൅ݔሻଵଽሺͳ൅ݔ ൅ݔହሻ.
Now we find the required answer as follows.
Let
݂ሺݔሻൌሺͳ൅ݔሻଵଽ and ݃ሺݔሻൌ ሺͳ൅ݔ ൅ݔହሻ.
Let ܽ௥ and ܾ௥ be the coefficient of ݔ௥ in ݂ሺݔሻ and ݃ሺݔሻ respectively, then we
know that
ܽ௥ൌቀͳͻ
ݎቁ and ܾ଴ൌܾଵൌܾହൌͳ and other ܾ௜’s are zero.
Now the coefficient of ݔଵହ in ݄ሺݔሻ is
ܽଵହܾ଴൅ܽଵସܾଵ൅ܽଵଷܾଶ൅ڮǥǤǤ൅ܽ ଴ܾଵହ munotes.in

Page 111

111Chapter 6: Generating FunctionWhich reduce to ܽଵହܾ଴൅ܽଵସܾଵ൅ܽଵ଴ܾହǤ
Substituting the values of ܽ௜Ԣݏ and ܾ௜Ԣݏ we get
ܽଵହܾ଴൅ܽଵସܾଵ൅ܽଵ଴ܾହൌቀͳͻ
ͳͷቁൈͳ൅ቀͳͻ
ͳͶቁൈͳ൅ቀͳͻ
ͳͲቁൈͳ
ൌቀͳͻ
ͳͷቁ൅ቀͳͻ
ͳͶቁ൅ቀͳͻ
ͳͲቁ
Example 12: Using generating functions to show that σܥሺ݊ǡݎሻଶൌ ܥሺʹ݊ǡ݊ሻ௡
௥ୀ଴
whenever n is a positive integer.
Solution: First note that by the Binomial Theorem ܥሺʹ݊ǡ݊ሻ is the coefficient of
ݔ௡ in ሺͳ൅ݔሻଶ௡Ǥ
However we also have
ሺͳ൅ݔሻଶ௡ൌሾሺͳ൅ݔሻ௡ሿଶ
ൌሾܥሺ݊ǡͲሻ൅ܥሺ݊ǡͳሻݔ൅ܥሺ݊ǡʹሻݔଶ൅ڮǥǤ൅ܥሺ݊ǡ݊ሻݔ௡ሿଶ
The coefficient of ݔ௡in this expression is
ܥሺ݊ǡͲሻܥሺ݊ǡ݊ሻ൅ܥሺ݊ǡͳሻܥሺ݊ǡ݊െͳሻ൅ܥሺ݊ǡʹሻܥሺ݊ǡ݊െʹሻ
൅ڮǥǤ൅ܥ ሺ݊ǡ݊ሻܥሺ݊ǡͲሻ
ൌσܥሺ݊ǡݎሻଶ ௡
௥ୀ଴ ܥ׶ሺ݊ǡ݊െݎሻൌܥሺ݊ǡݎሻǤ
Here both ܥሺʹ݊ǡ݊ሻ and σܥሺ݊ǡݎሻଶ ௡
௥ୀ଴ represent the coefficient of ݔ௡ in
ሺͳ൅ݔሻଶ௡.
Therefore σܥሺ݊ǡݎሻଶൌ ܥሺʹ݊ǡ݊ሻ௡
௥ୀ଴ Ǥ
.4 Exponential *enerating )unction
The Exponential generating function arise in selection problems where order was
not important i.e combination.
However, turning to the problems of arrangement ( Permutations) , where order is
important , we seek a comparable tool, namely the “ Exponential Generating
Function”.
Definition: For a sequence ܽ଴ǡܽଵǡǥǤ Of real numbers,
݃ሺݔሻൌܽ଴൅ܽଵݔ൅ܽଶ௫మ
ଶǨ൅ܽଶ௫య
ଷǨ൅ڮǥǤǤൌ σܽ௥௫ೝ
௥Ǩஶ
௥ୀ଴ munotes.in

Page 112

112DISCRETE MATHEMATICSis called the exponential generating function for the given seq uence. Note that
ܽ௜Ԣݏ may be constants or functions of reals.
For example; In the Maclaurin’s series expansion of ݁௫ǡ we find
݁௫ൌͳ൅ݔ൅ݔʹ
ʹǨ൅ݔ͵
͵Ǩ൅ڮǥǤǤൌ σݔݎ
ݎǨλ
ݎൌͲ.
Therefore ݁௫ i s t h e o r d i n a r y g e n e r a t i n g f u n c t i o n f o r t h e s e q u e n c e
ͳǡͳǡͳʹǨൗǡͳ͵Ǩൗǡ….and is the exponential generating function for sequence 1, 1, 1,
…..
Proposition: The expansion of ሺͳ൅ݔሻ௡ is an exponential generating function for
the sequence ܲሺ݊ǡݎሻǡ where Ͳ൑ݎ൑݊ .
Solution: We know that,
ቀ݊
ݎቁ ൌ ܥሺ݊ǡݎሻ is the number of combinations of n objects taken r at a time, and
ܲሺ݊ǡݎሻ is the number of permutations of n objects taken r at a time with Ͳ൑ݎ൑
݊ .
Consequently, ሺͳ൅ݔሻ௡ generates the sequence
ܥሺ݊ǡͲሻǡܥሺ݊ǡͳሻǡǥǥǤǤǡܥ ሺ݊ǡ݊ሻǡͲǡͲǡͲǥ
Now by Making use of the relation between ܥሺ݊ǡݎሻ and ܲሺ݊ǡݎሻ we write
ሺͳ൅ݔሻ௡ൌܥሺ݊ǡͲሻ൅ܥሺ݊ǡͳሻݔ൅ܥሺ݊ǡʹሻݔଶ൅ڮǥǤǤ൅ܥ ሺ݊ǡ݊ሻݔ௡
ൌܲሺ݊ǡͲሻ൅ܲሺ݊ǡͳሻݔ
ͳǨ൅ܲሺ݊ǡʹሻݔଶ
ʹǨ൅ڮǤ൅ܲ ሺ݊ǡ݊ሻݔ௡
݊ǨǤ
Where ܥሺ݊ǡݎሻൌ௉ሺ௡ǡ௥ሻ
௥ǨǤ
Hence ሺͳ൅ݔሻ௡ generates the sequence ܲሺ݊ǡͲሻǡܲሺ݊ǡͳሻǡǥǥǤǤǡܲ ሺ݊ǡ݊ሻ as the
coefficient of ௫ೝ
௥ǨǤ
Therefore the expansion of ሺͳ൅ݔሻ௡ is an exponential generating function for the
sequence ܲሺ݊ǡݎሻǡ where Ͳ൑ݎ൑݊ .
Example 13: A company hires 11 new employees, each of whom is to be
assigned one of four subdivisions. Each subdivision will get at least one new
employee. In how many ways can these assignments be made" munotes.in

Page 113

113Chapter 6: Generating FunctionSolution: Assuming the subdivisions A, B, C and D, we can equivalently c ount
the number of 11 letter sequences in which there is atleast one occurrence of each
of the letters A, B, C and D. The exponential generating functi on for these
arrangements is
݂ሺݔሻൌቆ ݔ൅ݔଶ
ʹǨ൅ݔଷ
͵Ǩ൅ڮǤቇସ
ൌሺ݁௫െͳሻସ
ൌ݁ସ௫െͶ݁ଷ௫൅͸݁ଶ௫െͶ݁௫൅ͳ
Now the required answer is the coefficient of ௫భభ
ଵଵǨ in ݂ሺݔሻ.
ͶଵଵെͶሺ͵ଵଵሻ൅͸ሺʹଵଵሻെͶሺͳଵଵሻൌ෍ሺെͳሻ௥ቀͶ
ݎቁሺͶെݎሻଵଵǤସ
௥ୀ଴
Example 14: A ship carries 48 flags, 12 each of the colors red, white, blu e and
green. 12 of these flags are placed on a vertical pole in order to communicate a
signal to other ships. How many of these signals use an even nu mber of blue flags
and an odd number of green flags"
Solution: The exponential generating function for this problem is
݂ሺݔሻൌቀ ͳ൅ݔ൅௫మ
ଶǨ൅௫య
ଷǨ൅ڮቁቀͳ൅௫మ
ଶǨ൅௫ర
ସǨ൅ڮቁቀݔ൅௫య
ଷǨ൅௫ఱ
ହǨ൅ڮቁ
Consider all such signals made up of n flags, where ݊൒ͳ Ǥ The last two factors in
݂ሺݔሻ restrict the signals to an even number of blue and an odd numb er of green
flags, respectively.
Since ݂ሺݔሻൌሺ݁௫ሻଶቀ௘ೣା௘షೣ
ଶቁቀ௘ೣି௘షೣ
ଶቁ
ൌͳ
Ͷሺ݁ଶ௫ሻሺ݁ଶ௫െ݁ିଶ௫ሻൌͳ
Ͷሺ݁ସ௫െͳሻ
ൌͳ
Ͷ൭෍ሺͶݔሻ௥
ݎǨെͳஶ
௥ୀ଴൱ൌͳ
Ͷ෍ሺͶݔሻ௥
ݎǨஶ
௥ୀ଴
The coefficient of ௫భమ
ଵଶǨ in the expansion of ݂ሺݔሻ yield ଵ
ସͶଵଶൌͶଵଵ signals made up
of 12 flags with an even number of blue flags and an odd number of green flags. munotes.in

Page 114

114DISCRETE MATHEMATICS.5 Use of generating functions for Solving homogeneous and
Non-homogeneous recurrence relations:
Now we demonstrate the procedure to solve a given recurrence r elation with the
help of generating functions in the following example in a syst ematic procedure.
Example15: Solve the recurrence relation
an+2 – 5an+1 + 6an 2, n ≥ 0.
a0 3,a1 7
Solution:
Step 1
Multiply the given relation by ݔn+2 , because n + 2 is largest subscript in
the relation. This gives us
Step 2
Sum all the equations represe nted by the result in step (1) and we get 20nnaf
¦ݔn+2 - 510nnaf
¦ݔn+2 + 60nnaf
¦ݔn+2 20nf
¦ݔn+2 .
Step 3
In order to have each of the subscripts on a match the corresponding
exponent on x, we rewrite the equation in step (2) as 20nnaf
¦ݔn+2 – 5x10nnaf
¦ݔn+2 + 6x20nnaf
¦ݔn+2 2x20nf
¦ݔn+2 .
Step 4
Let ݂ሺݔሻ 0nnaf
¦ݔn be the generating function for the solution. The
equation in step (3) now takes the form
(݂ሺݔሻ - a0 – a1ݔ - )5( ݂ሺݔሻ – aߜ + )6 ݔ2 ݂ሺݔሻ ଶ୶ଶ
ଵି௫
Or
(݂ሺݔሻ - 3 – 7ݔ - )5( ݂ሺݔሻ – 3) + 6 ݔ2 ݂ሺݔሻ ଶ୶ଶ
ଵି௫
Step 5
S o l v i n g f o r ݂ሺݔሻ we have
(1 - 5 ݔ + 6ݔ2) ݂ሺݔሻ 3 - 8 ݔ+ଶ୶ଶ
ଵି௫
ଷିଵଵ௫ାଵ଴௫ଶ
ଵି௫ , munotes.in

Page 115

115Chapter 6: Generating Function Form which it follows that
݂ሺݔሻ ଷିଵଵ௫ାଵ଴௫ଶ
ሺଵିହ௫ା଺௫ଶ ሻሺଵି௫ሻ
ሺଷିହ௫ሻሺଵିଶ௫ሻ
ሺଵିଷ௫ሻሺଵିଶ௫ ሻሺଵି௫ሻ
ଷିହ௫
ሺଵିଷ௫ሻሺଵି௫ሻ
P a r t i a l f r a c t i o n d e c o m p o s i t i o n g i v e s u s
݂ሺݔሻ ଶ
ଵିଷ௫ +ଵ
ଵି௫
20(3 )
nxf
¦n + 0()
nxf
¦n
C o n s e q u e n t l y , an 2(3n) + 1, n ≥ 0,
. Let us sum up
In this chapter we have learnt the following:
x For the sequence of real numbers, ܽ଴ǡܽଵǡܽଶǡǥǥǥ the function
݃ሺݔሻൌܽ଴൅ܽଵݔ൅ܽଶݔଶ൅ڮǥǥൌ σܽ௜ݔ௜ ஶ
௜ୀ଴
is called the ordinary gene rating function or generating function for the
given sequence.
x For a sequence ܽ଴ǡܽଵǡǥǤ Of real numbers,
݃ሺݔሻൌܽ଴൅ܽଵݔ൅ܽଶ௫మ
ଶǨ൅ܽଶ௫య
ଷǨ൅ڮǥǤǤൌ σܽ௥௫ೝ
௥Ǩஶ
௥ୀ଴
is called the exponential generating function for the given sequence.
x Finding the coefficient of ݔ௥ in the expansion of a polynomial.
x Solving various recurrence relations and the method of generati ng
functions.

munotes.in

Page 116

116DISCRETE MATHEMATICS.7 Unit end Exercise
1. What is the generating fun ction for the sequence 1,1,1,1,1"
2. Find the generating function for ሺͳ൅ݔሻି௡ and ሺͳെݔሻି௡ w h e n n i s a
positive integer. Using the e xtended Binomial theorem.
3. In how many different ways can 8 balls be distributed among thr ee distinct
boys. If each boy receives atleast t wo balls and no more than f our balls"
4. Using the generating functions to find the number of r-combinations of a set
with n- elements.
5. Use generating function to find the number of ways to select r- objects of n
different kinds, if we must select atleast one object of each k ind.
6. Determine the generating function for the number of ways to dis tribute a
large number of identical balls to four children so that the fi rst two children
receive an odd number of balls, the third child receives at lea st three balls,
and the fourth child receives at most two balls.
7. Determine the generating function for the number of n-combinati ons of
apples, bananas, oranges, and pears where in each n-combination the number
of apples is even, the number of bananas is odd, the number of oranges is
between 0 and 4, and the number of pears is at least two.
8. Let ܽ௡ denote the number of nonnegative integral solutions of the equ ation
ʹݔଵ൅͵ݔଶ൅Ͷݔଷ൅ͷݔସൌ݊. Find the generating function.
9. Determine the number ܽ௡ of n digit (under base 10) numbers with each digit
odd where the digit 1 and 3 occur an even number of times.
10. What is the number of distinct r-letter words based on n-letter alphabet
(repetition allowed, order matters)
11. Determine the number of ways to colors the square of a 1 by-n c hess board
using colors red, white and blue. If an even number of squares are to be
colored red.
12. Determine generating function for the sequence of squares 0,1,4 ,…..,݊ଶǤ
13. Solve the recurrence relati on using generating function
ܽ௡ൌͷ ܽ௡ିଵെ͸ܽ௡ିଶǡ݊ ൒ ʹǡܽ ଴ൌͳ ǡܽଵൌെ ͳ Ǥ munotes.in

Page 117

117Chapter 6: Generating Function14. Find an exponential generating function for the number of permu tations with repetition of length n of the set ^a,b,c`, in which there are a n odd number of a’s, an even number of b ’s, and any number of c ’s. 15. In how many ways can we paint the 10 rooms of a hotel if at mos t three can be painted red, at most 2 painted green, at most 1 painted whit e, and any number can be painted blue or orange" (The rooms are different, s o o r d e r matters.)
. References
1. Applied Combinatorics, Alan Tucker.
2. Combinotorial Techniques, Sharad S. Sane
3. Discrete mathematics its Application, Keneth H. Rosen TMG.
4. Discrete mathematics, Norman L. Biggs.
5. Discrete structures by B. Kolman HC Busby, S Ross PHI Pvt. L td.
6. Discrete mathematics, Schaum’s outlines s e r i e s , S e y m o u r L i p S c h u t z , M a r c
Lipson, TMG.
munotes.in

Page 118

118DISCRETE MATHEMATICS7
POLYA’S THEORY OF COUNTING
Unit Structure:
7.1 Objective
7.2 Introduction
7.3 Equivalence relations and orbits under a permutation group action.
7.4 Burnside’s Lemma
7.5 The Cycle Index
7.6 Polya’s Formula and Application.
7.1 ObMective
After going through this chapter students will be able to under stand:
● Equivalence relations and orbits under a permutation group acti on.
● Orbit Stabiliser theorem.
● Polya theorem.
● Burnside theorem and its application.
● Cycle index of a permutation.
● Polya’s formula and its application in counting theory.
7.2 Introduction
The section needs a good understanding of some basic facts from group theory,
particularly those connected with permutation groups. The Polya T h e o r y i n i t s
enumerative applications to permutations groups. The discussion i n c l u d e s t h e
notion of the power group, the Burnside
s Lemma along with the notions on groups,
stabilizer, orbits and other group t h e o r e t i c t e r m i n o l o g i e s w h i c h are so
fundamentally used for a good introduction to the Polya Theory. These in turn,
involve the introductory concepts on weights, patterns, figure and configuration 118Unit 4
munotes.in

Page 119

119Chapter 8: Polya’s Theory of Countingcounting series along with the extensive discussion of the cycl e indexes associated
with the permutation group at hand. Shows that the special figu re series c(x) 1 +
x is useful to enumerate the number of G-orbits of r -subsets of any arbitrary set X.
Further more, the paper also shows that this special figure ser ies simplifies the
counting of the number of orbits determined by any permutation group which
consequently determines whether or not the said permutation gro up is transitive.
Here we shall be studying a financial theorem of conservative c ombinations called
Polya’s theorem.
7.3 ETuivalence relations and orbi ts under a permutation group
action
Let ܺ be a set, which may be finite or infinite (but will usually be finite). We denote
by ݉ݕܵሺܺሻ t h e s y m m e t r i c g r o u p o n ܺ , the group whose elements are all the
permutations of ܺ( the bijective maps from ܺ to itself), with the operation of
composition. If ܺ is finite, say |ܺ | = n , we often write ݉ݕܵሺܺሻas ܵ௡.
We compose permutations from left to right, so that ݃ଵ݃ଶ means “apply first ݃ଵ ,
then ݃ଶ”. This goes naturally with writing a permutation on the right of its
argument: ߙ൫݃ͳ݃ʹ൯ൌ ሺ݃ߙͳሻ݃ʹ.
Now a permutation group on ܺ i s s i m p l y a s u b g r o u p o f ݉ݕܵሺܺሻ t h a t i s , a
permutation group G is a set of permutations of ܺ w h i c h i s c l o s e d u n d e r
composition, contains the identity permutation, and contains th e inverse of each of
its elements.
Remark : Let S be a mathematical structure of virtually any type built on the setܺ
.Then the automorphism group of S is usually a permutation gro up on ܺ( .A little
care is required: if S is a topology, then taking “automorphism ” to mean
“continuous bijection” does not work; we should take “automorph ism” to be
“homeomorphism” in this case.)
There is a related concept, that of a group action. Let G be a group (in the abstract
sense of group theory, a set with a binary operation). Then an action of G on ܺ is a
homomorphism from G to ݉ݕܵሺܺሻin other words, it associates a permutation with
each element of G. The image of a group action is a permutation group the extra
generality is that the action may have a kernel. The extra flex ibility is important,
since the same group may act on several different sets.
munotes.in

Page 120

120DISCRETE MATHEMATICSFor e.g. Let G be the group of symmetries of a cube,

Fi g. 7.1
Let ܺ be the set of size 26 consisting of the 8 vertices, 12 edges, and 6 faces of the
cube. Then G acts on Ω the action is faithful (no symmetry can fix all the vertices
except the identity), so we can regard G as a permutation group on ܺ .It is often the
case, as in the examples below, that when we say “Let G be a permutation group
on ”, we could as well say “Let the group G a c t o n ܺ .”For example, any
permutation group property immediately translates to group acti ons.
7.3.1 Orbits and transitivity:
In above example, the group G contains permutations which map any vertex to
another vertex we cannot map a vertex to an edge. We formalize this by the notion
of orbits.
Let G be a permutation group on ܺ .Define a relation ׽ on ܺ by the rule α ׽ β if
and only if there exists ܩא݃ such that ݃ߙ ൌ ߚ .
Definition: E q u i v a l e n c e r e l a t i o n : Let ‘R’ be a relation on ‘A’, ‘R’ is said to be an
equivalence relation on A iff ‘R’ is reflexive, symmetric and t ransitive.
Example 1: Show that ׽ is an equivalence relation on ܺ .
Solution: Define relation ׽ܺ by the rule,
ݔ̱ݕ฻݃ ሺݔሻൌݕ for some ܩא݃ .
Reflexivity: Since identity belong to any group, and ݀݅ሺݔሻൌݔ for all ܺאݔ ,we
have ݔ̱ݔǤ
Symmetry: Suppose ݔ̱ݕǡ so that ݃ሺݔሻൌݕ for some ܩא݃ Ǥ Since ܩ is a group,
݃ିଵܩאǡ and since ݃ିଵሺݕሻൌݔ we have ݕ̱ݔǤ
munotes.in

Page 121

121Chapter 8: Polya’s Theory of CountingTransitivity: If ݔ̱ݕand ݕ̱ݖ we must have ݕൌ݃ଵሺݔሻǡand ݖൌ݃ଶሺݕሻ for some
݃ଵand ݃ଶ in ܩǤ Since ܩ is a group , ݃ଶ݃ଵ is in ܩ and since ݃ଶ݃ଵሺݔሻൌݖ we have
ݔ̱ݖǤ
Hence ׽ is an equivalence relation on ܺ.
Since ׽ is an equivalence relation, ܺ decomposes as a disjoint union of its
equivalence classes. These classes are called orbits.
Definition: The Orbit of ݔ contains all the members of ܺ which are of the form
݃ሺݔሻ for some ܩא݃ǡ it is denoted by ݔܩ .Explicitly,
ݔܩ ൌሼݕൌ݃ሺݔሻܩא݃݁݉݋ݏݎ݋݂ ሽǤ
Therefore in above example of cube, the sets of vertices, edges and faces form the
three orbits of G.
Note: If a permutation group has just a single orbit, we say th at it is transitive.

Definition: Stabili]ers: Given an element ݔ in ܺ ,we define the stabilizer ܩ௫of ݔ
(in ܩ )by
ܩ௫ൌሼܩא݃ ȁݔ݃ ൌ ݔሽ
As can be readily checked, the stabilizer ܩ௫ is a subgroup of ܩ .There is a nice
relationship
between the stabilizers of point s that belong to the same orbit : if ݕൌݔ݃ for some
ܩא݃ for points ݕ and ݔ of ܺ ,then, as can be readily checked
ܩ௚௫ൌܩ݃ ௫݃ିଵ
The most fundamental theorem about group actions is the Orbit-S tabilizer
Theorem, which states that the size of the orbit of an element is equal to the index
of its stabilizer in the group. This applies to any situation i n which the relevant orbit
is finite, although for simplicity we state it only for finite groups
The Orbit-Stabili]er Theorem : Let ܩ be a finite group acting on a set ܺ ,and let
ܺאݔ .Then the number of elements in the orbit ݔܩ is equal to ሾܩǣܩ௫ሿǤ
i.e. ȁݔܩȁൌȁீȁ
ȁீೣȁ munotes.in

Page 122

122DISCRETE MATHEMATICSProof: we say that หܩห
หܩݔห is the index of ܩ௫ in ܩǤ which is the number of distinct
left cosets of ܩ௫ in ܩ .
Let ݃ and ݄ be elements of ܩ and consider when the elements ݔ݃ and ݔ݄ of ݔܩ are
equal.
ݔ݃ ൌ ݔ݄ ฻ ݃ିଵݔ݃ ൌ ݃ିଵݔ݄
Thus ݔ݃ ൌ ݔ if and only if ݃ିଵ݄ൌݏ for some ܩאݏ௫.
This occurs if and only if ݄ൌݏ݃ which means that ݄ belongs to the left coset of ܩ௫
determined by ݃ ,which means that ݃ and ݄ determine the same left coset of ܩ௫ .
Thus the number of distinct elements of the orbit of ݔ is equal to the number of
distinct left cosets of ܩ௫in ܩ ,as required.
Example 2: Let T be a regular tetrahedron in 3-dimensional space. Find the orde r
of the group of rotational symmetries of T. (Fig. 7.2)

Figure 7.2
Solution: Let G be the group of permutations of the corners which correspond t o
rotational symmet ries, and let x be any corner of T. Given any other corner y there
is an edge yx of T and there are two faces of T which are bounded by yx. Let a be
the centroid of one of these faces and let z be the opposite corner of T. Then a
rotation of ͳʹͲι about the axis az take x to y. Hence the orbit ݔܩ contains all four
vertices, and we have ȁݔܩȁൌͶ Ǥ
munotes.in

Page 123

123Chapter 8: Polya’s Theory of CountingThe only rotational symmetries which fix x are the rotations through ͲιǡͳʹͲι and
ʹͶͲι about the altitude passing through x, and so the stabilizer ܩ௫ has order 3.
Hence by the Orbit-Stabilizer Theorem,
ȁݔܩȁൌȁܩȁ
ȁܩ௫ȁ
׵ȁܩȁൌȁݔܩȁൈȁܩݔȁൌͶൈ͵ 12.
The number of orbits:
We turn now to the problem of counting the number of orbits whe n we are given a
group G of permutations of a set X. each orbit is a subset of X whose members are
indistinguishable under the action of G, and so the number of orbits tells us the
number of distinguishably different types of object in X.
Given any group G of permutations of a set ; we define, for each ݃ in G, a set
ܨሺ݃ሻൌሼܺאݔ ȁ݃ሺݔሻൌݔሽ
Thus ܨሺ݃ሻ is the set of objects fixed by ݃Ǥ The next theorem says that the number
of orbits is equal to the average size of the sets ܨሺ݃ሻ is called Burnside’s Lemma.
7.4 Burnside’s Lemma
We now develop a theory for count ing the number of different (n on-equivalent) 2-
colorings of the square. More generally, in a set T of colorings of the corners (edges
or faces) of same figure, we seek the number N of equivalence classes of T induced
by a group G of symmetries of this figure.
Suppose there is a group of s symmetries acting on the c-colorings in T. Let ܧ௖ be
the equivalence class consisting of C and all colorings C’ equivalent to C, that is,
all C’ such that for some ܩאߨ ǡߨሺܥሻൌܥ Ԣ. If each of the ߨݏԢs takes C to a different
coloring ߨሺܥሻ , then ܧ௖ would have ݏ colorings. Note that the set of ߨሺܥሻԢs includes
C since ߨூሺܥሻൌܥ (ߨூ is the identify symmetry). If every equivalence class is like
this with s colorings, then ܰݏ ൌ ܿ( n u m b e r o f s y m m e t r i e s ) ൈ(number of
equivalence classes) (to tal number of colorings)
Solving for N, we have ܰൌ௖
௦.
We can use Burnside’s Lemma to enumera te the number of distinct objects,
however, sometimes we will also wa nt to know more information a bout the munotes.in

Page 124

124DISCRETE MATHEMATICScharacteristics of these distinct objects.
Theorem: The number of orbits of ܩ on ܺ is ଵ
ȁீȁσ௚אீȁܨሺ݃ሻȁǤ Where ܨሺ݃ሻ is
the set of object fixed by ݃ .
Proof: We use method of counting pairs. Let ܧൌሼሺ݃ǡݔሻȁ݃ሺݔሻൌݔ ሽ Ǥ
Then the row total ݎ௚ሺܧሻ is equal to the number of x fixed ݃ ,that is ȁܨሺ݃ሻȁ .
Also, the column total ܿ௚ሺܧሻ is equal to the number of ݃ which fix x, that is ȁܩݔȁ .
Hence the two methods for counting ܧ lead to the equation
෍
௚אீȁܨሺ݃ሻȁൌ෍
௫א௑ȁܩ௫ȁ
Suppose there are t orbits, and let z be a chosen element of X. If x belong to the
orbit ܩ௭ then ȁܩݔȁൌȁܩݖȁ. Hence on the right hand side of the equation above there
are ȁݖܩȁ terms equal to ȁܩݖȁ, one for each x in ݖܩ .The total contribution from these
terms is ȁݖܩȁൌȁீȁ
ȁீೣȁǡ
Since there are t orbits altogether the right hand side is equal to ݐȁܩȁǡ a n d o n
rearranging the equation we obtain
ݐൌͳ
ȁܩȁ෍
௚אீȁܨሺ݃ሻȁǤ
Example 3: Necklaces are manufactured by arranging 13 white beads and 3 b lack
beads on a loop of string. How many different necklaces can be produced in this
way"
Solution:
Total number of beads 13 + 3 16 beads, can placed at the co rners of a regular
polygon with 16 sides.
Now, each configuration is specified by the choice of the 3 cor ners which are
occupied by black beads, therefore ሺͳ͸͵ሻൌͷ ͸ Ͳ configuration in all.
Two configurations give the same necklace if one can be obtaine d from the other
by a symmetry transformation of the polygon by either a rotatio n or a reflection,
the latter being equivale nt to overturning the polygon. munotes.in

Page 125

125Chapter 8: Polya’s Theory of CountingThere are 32 symmetries in all, as given below,
i) The identity fixes all 560 configurations.
ii) There are 15 rotations through angles ଶగ௡
ଵ଺ where ݊ൌͳ ǡ ʹ ǡǥǤǤǡͳ ͷ and
each of them has no fixed configurations.
iii) There are 8 reflections in axes joining the mid-points of oppos ite
sides, and each of them has no fixed configurations.
iv) There are 8 reflections in axes passing through opposite corner s. The
positions of the 3 black beads are unchanged by such a reflecti on only
if one of the beads occupies one of the 2 corners lying on the axis, and
the other pair occupies one of the 7 pairs of corners symmetric ally
placed with respect to this axis.
Hence there are ʹൈ͹ൌͳͶ fixed configurations for each reflection of
this kind.
Therefore the number of different necklaces ൌଵ
ଷଶሾͷ͸Ͳ൅ሺͺൈͳͶሻሿൌʹ ͳ Ǥ
Example 4: A stick is painted with equal sized cylindrical bands. Each ba nd can
be painted black or white. If the stick is un-oriented as when spun in the air, how
many different 2-coloring of the stick are possible if the stic k has i) 2 band" ii)
3 bands"
Solution:
i) The stick with 2 bands is shown in figure below:

Fig.7.3
Fig.7.3
There are two symmetries of a stick: first( x) is a Ͳι revolution and second( y) is a
ͳͺͲι revolution.
For the 2-band stick, the set of 2-colorings left by x is all 2-colorings of the stick.
There are ʹଶൌͶ Ǥ The set of 2-colorings left fixed by y consists of the all black
and all white coloring, and so 2.
Therefore by Burnside’s theorem,
The number of different colorings ଵ
ଶሾͶ൅ʹሿൌ͵ Ǥ 1:Black 2: white munotes.in

Page 126

126DISCRETE MATHEMATICSii) The stick with 3 bands is shown in figure below:

Fig. 7.4
Fig.7.4
There are two symmetries of a stick: first( x) is a Ͳι revolution and second( y) is a
ͳͺͲι revolution.
For the 3-band stick, the set of 2-colorings left by x is all 2-colorings of the stick.
There are ʹଷൌͺ Ǥ The set of 2-colorings left fixed by y can have any color in the
middle band and common color in the two end bands, and so ʹൈʹൌͶ .
Therefore by Burnside’s theorem,
The number of different colorings ଵ
ଶሾͺ൅Ͷሿൌ͸ Ǥ
7.5 The Cycle Index
In applying Burnside’s theorem we have been faced with computin g ܨሺ݃ሻ for each
ܩא݃ǡ where G is permutation group acting on a set X of configurations. We now
develop the theory for the simplified calculation of ܨሺ݃ሻ in Burnside’s theorem to
use it efficiently in terms of 2-colorings of a square.
Definition: Let G be a group whose elements are the permutations of X, where
ȁܺȁൌ݉ . We define the polynomial in m variables ݔଵǡݔଶǡǥǥǤǡݔ ௠ǡ i f
ሼܽଵǡܽଶǡܽଷǡǥǤǤሽ in the type of ݃.then the polynomial
ܲீሺݔଵǡݔଶǡǥǥǤǡݔ ௠ሻൌͳ
ȁܩȁ෍
௚אீݔଵ௔భݔଶ௔మǥǥǤǤݔ௠௔೘
is called the cycle index of G.
More generally we have the following result.
Let X be the set of all configurations obtained by a permutation gro up G. then for
any m, ܲீሺ݉ǡ݉ǡ݉ǥǤǤǡ݉ሻ will be the number of non-equivalent m-colorings of
X. 1:Black 2: white 3: black munotes.in

Page 127

127Chapter 8: Polya’s Theory of CountingExample 5: Suppose a necklace can be made from beads of three colors blac k,
white, and red. How many different necklaces with n beads are there"
Solution: Here beads on the necklace can rotate freely around the circle but
reflections are not permitted and that the number of different 3-colored strings of n
beads is equal to the number of 3-colorings of a cyclically un- oriented n-gon. For
݊ൌ͵, the rotations are of ͲιǡͳʹͲι and ʹͶͲι with cycle structure representations
of ݔଵଷǡ ݔଷǡ and ݔଷ respectively. Thus,
ܲீൌଵ
ଷሺݔଵଷ൅ݔଷሻ.
The number of 3-colored strings of three beads is
ܲீൌͳ
͵ሾ͵ଷ൅ʹൈ͵ሿൌͳ ͳ Ǥ
More generally, the number of m-colored necklace of three beads is
ܲீሺ݉ǡ݉ǡ݉ሻൌͳ
͵ሾ݉ଷ൅ʹ݉ሿǤ

7.6 Polya’s Formula
In many instances, the direct application of the Burnside’s Lem ma is not practically
efficient to permit us to enumerate the distinct ܩെorbits induced by a permutation
group. The difficulty perfectly stems from the computation of t he number of
invariances for a large ordered group.
It is an elegant combination of theory of groups of permutation s and the powerful
method of generating function. We are now ready to address our ultimate goal of a
formula for the pattern inventory. Recall that the pattern inve ntory is a generating
function that tells how many colorings of an unoriented figure are using different
possible collections of colors.
The Polya’s theorem provides a tool necessary to facilitate thi s computation. To
formulate and prove Polya’s theorem in an abstract and more con cise manner, it is
somehow convenient to require the notion of functions and patte rns as its
enumerations are basically performed over sets whose elements a re functions. In
the rest of discussion, we consider X be a set of elements call ed “places”, and Let
Y be a set of elements called “figure”. Also we consider the us ual permutation munotes.in

Page 128

128DISCRETE MATHEMATICSgroup G acting on ;, which is called Configuration group. Moreo ver, an element f
in ܻ௑ will be called Configuration.
Definition: On ܻ௑ ,the set of all configurations from ; to <, define the relatio n
݂ଵ̱݂ଶ, to mean that for some ܩאߨ Ǣ ݂ ଵ൫ߨሺݔሻ൯ൌ݂ଶሺݔሻܺאݔ׊ Ǥ
Definition: Let ݓǣܻ ՜ ሼͲǡͳǡʹǡǥǥǤሽ called weight function whose range is set of
non-negative integers. For each ݇ൌͲ ǡͳ ǡʹ ǡǥǤ Ǥ Let ܿ௞ൌȁݓିଵሺ݇ሻȁ be the number
of figures with weight k. Further the series in the indeterminate x,
ܿሺݔሻൌσஶ
௞ୀ଴ܿ௞ݔ௞
Definition: Let ; and R be finite sets, and G be permutation group of ;. W e will
assign a weight to each element ܴאݎ call it ݓሺݎሻ. The weight ܹሺ݂ሻ of a function
ܴא݂௑ is the product
ܹሺ݂ሻൌෑ
௫א௑ݓሾ݂ሺݔሻሿǤ
Note that if ݂ଵ̱݂ଶ, that is, if they belong to the same pattern, then they have t he
same weight.
Therefore, we may define the weight of the pattern as a common value. Thus if F
denotes a pattern, we will denote the weight of F by W(F) .
Definition: The pattern inventory written P.I is defined by ܲǤܫǤൌσ௙ܹሺ݂ሻ
where the sum is over all the patterns f ( in the action of a group G acting on the
domain X)
Polya’s Fundamental theorem:
Statement: Let G be a permutation group acting on the domain set X and let w
be a weight assignment on the range R. then the pattern inventory is given by
ܲǤܫ ൌܲ ீ቎෍
௥אோݓሺݎሻǡ෍
௥אோݓሺݎሻଶǡǥ ǥ Ǥ ǡ ෍
௥אோݓሺݎሻ௝቏
ൌܲீ൫ݔଵǡݔଶǡǥǤǤǡݔ ௝ǡǥ൯ȁቐݔ௝ൌ෍
௥אோݓሺݎሻ௝ቑ݆׊munotes.in

Page 129

129Chapter 8: Polya’s Theory of CountingThat is the pattern inventor is obtained by replacing each vari able ݔ௝ in the cycle
index of the group G by the sum σ௥אோݓሺݎሻ௝.
Proof: L e t ܹଵǡܹଶǡǥǤǤǡܹ ௜ǡǥ be the distinct entities that occur as weights of
patterns. Let ݉௜ denote the number of patterns whose weight is ܹ௜. Then by
definition, we have ܲǤܫ ൌσ௜݉௜ܹ௜Ǥ
Now fix an ݅ a n d c o n s i d e r t h e s e t T o f a l l t h e f u n c t i o n s f w h o s e w e i g h t ܹ௜.If
ܨଵǡܨଶǡǥǤǡܨ௜ denotes the ݉௜ patterns whose weight is ܹ௜ then ܶൌܨଵܨ׫ଶ׫ǥǤ׫
ܨ௜Ǥ Let ܶא݂ and let ܩאߙ Ǥ Then ܽఈሺ݂ሻ ܶא and hence ܽఈȁܶ is a permutation on
ܶǤ Therefore, we may restrict the action of the Permutation group G to T and that
gives us ݉௜ orbits of G on T. using Burnside’s lemma , we have
݉௜ൌȁܩȁିଵ෍
ఈאீหሺܨሺݔ݅ሻ ఈǡ௜ห
Where ܨሺݔ݅ሻఈǡ௜ൌሼ݂ǣܽ݀݊ܽܶא݂ ఈሺ݂ሻൌ݂ሽ
And we get ܨሺݔ݅ሻఈǡ௜ൌሼ݂ǣܴא݂ ௑ܽ݀݊ܽ ఈሺ݂ሻൌ݂ሽ

Hence the pattern inventory is given by summing over all ݅ .
ܲǤܫ ൌ ෍
௜݉௜ܹ௜
ൌ෍ ܹ ௜ȁܩȁିଵቐ෍
ఈאீหሺݔ݅ܨሻఈǡ௜หቑ
ൌȁܩȁିଵ෍
ఈאீቐ෍
௜หሺ݅ݔܨሻఈǡ௜หܹ௜ቑ
We now interpret the expression in the parentheses. Fix an ܩאߙ .Then we are
summing over all i. Thus σ௜หሺ݅ݔܨሻఈǡ௜หܹ௜ i s t h e s u m o f w e i g h t s o f a l l t h e
functions that are fixed by ߙ .Let
ܵఈൌሼ݂ǣܽఈሺ݂ሻൌ݂ሽmunotes.in

Page 130

130DISCRETE MATHEMATICSThen the expression of the pattern inventory simplifies to
ܲǤܫ ൌȁܩȁିଵ෍
ఈאீܹሺܵఈሻ
To simplifies the notation, Let ܵൌܵఈ. Let cycle type of ߙ be ൫ܾଵǡܾଶǡǥǡܾ௝ǡǥ൯Ǥ
Let ܺ௝ǡ௧ denote the ݐ௧௛, j-cycle in the cycle of decomposition of ߙ.Thus ڂ௝ڂ௧ୀଵ௕ೕܺ௝ǡ௧
is the partition of ;. Let ܺ௝ǡ௧ൌ ሺܽଵǡܽଶǡǥǤǤǡܽ ௝ǡǥሻ. Then ߙ fixed ݂ if and only if
݂ሺܽ௜ሻൌ݂ ൫ ߙሺܽ௜ሻ൯ൌܽ௜ାଵ where we read subscripts modulo j. Thus ܵא݂ if and
only if f is constant on each ܺ௝ǡ௧Ǥ T h a t g i v e s t h e w e i g h t o f S t o b e ݓሺݏሻൌ
ς௝ς௕ೕ
௧ୀଵσ௥אோݓሺݎሻห௑ೕǡ೟หൌς௝൛σ௥אோݓሺݎሻ௝ൟ௕ೕ Because ห݆ܺǡݐหൌ݆
and ܾ௝ cycles of the length j. it just remains to interpret the right hand side of the
equation just obtained. Since ߙ has cycle type ൫ܾଵǡܾଶǡǥǡܾ௝ǡǥ൯ǡ the monomial of
ߙis
ሺݔଵሻ௕భሺݔଶሻ௕మǥǥ൫ݔ ௝൯௕ೕǥൌෑ
௝ሺݔ௝ሻ௝
Thus ݓሺܵఈሻൌݓሺܵሻൌς௝ሺݔ௝ሻ௝ where the variable ݔ௝ is replace by the
expression σ௥אோݓሺݎሻ௝. Thus ݓሺܵఈሻ is nothing but the monomial of ߙ with the
݆௧௛ variable ݔ௝ is replace by σ௥אோݓሺݎሻ௝.
Since P.I is obtained by summing all ݓሺܵఈሻ and dividing by ȁܩȁ, by using the
definition of cycle index we get
ܲǤܫ ൌȁܩȁିଵ෍
ఈאீሺߙ݂݋݈ܽ݅݉݋݊݋݉ሻ
ܲǤܫ ൌܲ ீ቎෍
௥אோݓሺݎሻǡ෍
௥אோݓሺݎሻଶǡǥ ǥ Ǥ ǡ ෍
௥אோݓሺݎሻ௝቏
ൌܲீ൫ݔଵǡݔଶǡǥǤǤǡݔ ௝ǡǥ൯ȁቐݔ௝ൌ෍
௥אோݓሺݎሻ௝ቑ݆׊
Example : Find the number of 7-bead necklaces distinct under rotations u sing 3
black and 13 white beads. munotes.in

Page 131

131Chapter 8: Polya’s Theory of CountingSolution: we need to determine the coefficient of ܾଷݓସ in the pattern inventory.
Each rotation except the Ͳι rotation, is a cyclic permutation when the number of
beads is prime, so
ܲீൌͳ
͹ሺݔଵ଻൅͸ݔ଻ሻǤ
The pattern inventory is ଵ
଻ሾሺܾ൅ݓሻ଻൅͸ሺܾ଻൅ݓ଻ሻሿǤ
Since the factor ͸ሺܾ଻൅ݓ଻ሻ in the pattern inventory contributes nothing to the
ܾଷݓସterm, we can neglect it. Thus the number of 3-black , 4- white necklaces is
simply
ଵ
଻ሾܾ݂݋ݐ݂݂݊݁݅ܿ݅݁݋ܿଷݓସ݊݅ሺܾ൅ݓሻ଻ሿൌଵ
଻ሺ͹͵ሻൌͷ Ǥ
Example 7: Consider of colorings the 12 faces of a regular dodecahedron i n two
colors black and white with the weights of black and white b and w respectively.
Computed the cycle index of the rotation group of a regular dod ecahedron. Using
Polya
s theorem the pattern inventory is given by
ܲǤܫ ൌͳ
͸Ͳሾሺܾ൅ݓሻଵଶ൅ʹͲሺܾଷ൅ݓଷሻସ൅ͳͷሺܾଶ൅ݓଶሻ଺
൅ʹͶሺܾ൅ݓሻଶሺܾହ൅ݓହሻଶሿǤ
i) How many patterns have 4 faces black"
ii) How many patterns have 9 faces white"
iii) Find the total number of patterns.
Solution: Polya’s theorem the pattern inventory is given by
ܲǤܫ ൌͳ
͸Ͳሾሺܾ൅ݓሻଵଶ൅ʹͲሺܾଷ൅ݓଷሻସ൅ͳͷሺܾଶ൅ݓଶሻ଺
൅ʹͶሺܾ൅ݓሻଶሺܾହ൅ݓହሻଶሿ
i) Patterns have 4 faces black,. i.e. it have 8 faces white. There fore it has
coefficient ܾସݓ଼ in the ܲǤܫ is given by
ܲǤܫ ൌͳ
͸ͲሼሺͳʹͶሻ൅ͳͷൈሺ͸ʹሻሽൌͳ
͸ͲሼͶͻͷ൅ʹʹͷ ሽൌ͹ʹͲ
͸Ͳൌ͸ Ͳ
ii) patterns have 9 faces white i.e. it have 3 faces black. Therefo re it has
coefficient ܾଷݓଽ in the ܲǤܫ is given by
ܲǤܫ ൌͳ
͸Ͳሼሺͳʹͻሻ൅ʹͲൈሺͶሻሽൌͳ
͸ͲሼʹʹͲ൅ͺͲ ሽൌ͵ͲͲ
͸Ͳൌͷ munotes.in

Page 132

132DISCRETE MATHEMATICSiii) The total number of patterns is
ܲǤܫ ൌͳ
͸Ͳሾሺʹሻଵଶ൅ʹͲሺʹሻସ൅ͳͷሺʹሻ଺൅ʹͶሺͶሻସሿ
ൌͳ
͸ͲሾͶͲͻ͸൅ʹͲൈͳ͸൅ͳͷൈ͸Ͷ൅ʹͶൈͳ͸ ሿ
ൌͳ
͸ͲሾͶͲͻ͸൅͵ʹͲ൅ͻ͸Ͳ൅͵ͺͶ ሿൌͻ ͸
Example : In how many ways, can we color the corners of the square with two
colors"
Solution:

Fig. 7.5
Here the permutation group is ܦସ. We have two colors. First we find all possible
permutations under the action of rotation and reflection, and s et of all permutations
are isomorphic to ܦସ.
So,
ߝൌሺͳʹ͵Ͷͳʹ͵Ͷሻൌ ሺͳሻሺʹሻሺ͵ሻሺͶሻ
Possible ways (Number of col oring of square’s corners) under ac tion ε are
ȁܺߝȁൌʹͶൌͳ ͸

munotes.in

Page 133

133Chapter 8: Polya’s Theory of CountingWe have,
ߩଵൌሺͳʹ͵Ͷʹ͵Ͷͳሻൌ ሺͳʹ͵Ͷሻ ( ͻͲι counter clockwise)
ߩଶൌሺͳʹ͵Ͷ͵Ͷͳʹሻൌሺͳ͵ሻሺʹͶሻ (ͳͺͲιcounter clockwise)
ߩଷൌሺͳʹ͵ͶͶͳʹ͵ሻൌ ሺͳͶ͵ʹሻ ( ͻͲιclockwise )
So, possible ways (Number of coloring of square’s corners) unde r action
ߩଵǡߩଶǡߩଷ are
ቚܺߩͳቚൌቚܺߩ͵ቚൌʹͳൌʹ, ቚܺߩʹቚൌʹʹൌͶ
By reflections of square along axis, we have
ߪ௫ൌሺͳʹ͵ͶͶ͵ʹͳሻൌሺͳͶሻሺʹ͵ሻ (rotation along x-axis)
ߪ௬ൌሺͳʹ͵ͶʹͳͶ͵ሻൌሺͳʹሻሺ͵Ͷሻ (rotation along y-axis)
So, possible ways (Number of coloring of square’s corners) unde r action ߪ௫ and
ߪ௬ are
ȁߪݔȁൌหߪݕหൌʹʹൌͶ
By reflections of square along diagonals, we have
ߪ݀ͳൌሺͳʹ͵Ͷ͵ʹͳͶሻൌሺͳ͵ሻሺʹሻሺͶሻ (rotation along ݀ଵ diagonal)
ߪ݀ʹൌሺͳʹ͵ͶͳͶ͵ʹሻൌሺͳሻሺ͵ሻሺʹͶሻ (rotation along ݀ଶ diagonal)
So, possible ways (Number of coloring of square’s corners) unde r action ߪ݀ͳ and
ߪ݀ʹ are
ቚߪ݀ͳቚൌቚߪ݀ͳቚൌʹ͵ൌͺ.
we have,
Required number of colorings ൌଵ
଼ሺͳ͸൅ʹൈʹ൅Ͷ൅ʹൈͶ൅ʹൈͺ ሻൌ͸.
Now, we are going to use Polya’s theorem for two colors in a sq uare. From
above, we have the following cycle structures of permutations
ሺͳሻሺʹሻሺ͵ሻሺͶሻ
ሺͳʹ͵Ͷሻmunotes.in

Page 134

134DISCRETE MATHEMATICSሺͳ͵ሻሺʹͶሻ
ሺͳͶ͵ʹሻ
ሺͳͶሻሺʹ͵ሻ
ሺͳʹሻሺ͵Ͷሻ
ሺͳ͵ሻሺʹሻሺͶሻ
ሺͳሻሺ͵ሻሺʹͶሻ
Cycle structure of ܦସ
so the cycle index of ܦସ is
ܼሺܦସሻൌͳ
ͺሺͳൈܽଵସ൅͵ܽଶଶ൅ʹܽଵଶܽଶ൅ʹܽସሻ
Generating function coloring one corner is
ܨሺܺǡܻሻൌͳ Ǥܺ൅ͳ Ǥܻ
We can use color X or Y to colo r a corner in the square. By Pol ya’s Enumeratio n
Theorem (PET), we have
ܲǤܫ ൌͳ
ͺሾሺܺ ൅ܻሻସ൅͵ሺܺଶ൅ܻଶሻଶ൅ʹሺܺ൅ܻሻଶሺܺଶ൅ܻଶሻ൅ʹሺܺସ൅ܻସሻሿ
Generating function for the colorings of the square. We have
ܼሺܦସሻሺܺǡܻሻൌܺସ൅ܻସ൅ܺଷܻ൅ܻܺଷ൅ʹܺଶܻଶ
ܼሺܦସሻሺͳǡͳሻൌͳ൅ͳ൅ͳ൅ͳ൅ʹൌ͸
So, total number of colorings 6. Hence, the possible coloring s are:
1- All corners have color ;,
1- All corners have color <,
1- Three corners have color ;, and one has <,
1- One corner has color ; and three have <,
2- Two corners have color ; and two have < munotes.in

Page 135

135Chapter 8: Polya’s Theory of CountingExample : One of the important applications of the content version of Po lya
s
theorem is the finding of different possible isomers of a chemi cal compound.
Recall that isomers are chemical compounds with the same chemic al formula
with a different arrangement of the atoms.
a) Find the number of benzene rings with Cl substituted in the pla ce of H.
Solution: The symmetry group of the benzene ring is ܦ଺ (i.e., the symmetries of a
regular hexagon).

)ig 7.

munotes.in

Page 136

136DISCRETE MATHEMATICSNow, ܼሺܦ଺ሻൌଵ
ଵଶሾܵଵ଺൅Ͷܵଶଷ൅ʹܵଷଶ൅͵ܵଵଶܵଶଶ൅ʹܵ଺ሿ
Here, ܦൌሼͳǡ ʹǡ͵ǡͶǡͷǡ͸ ሽܴ ൌ ሼܪǡ݈ܥሽ
Let content ሺܪሻൌͲ, content ሺ݈ܥሻൌͳ,
So ܿሺݔሻൌͳ൅ݔ .
ܲǤܫ ൌͳ
ͳʹሾሺͳ൅ݔሻ଺൅Ͷሺͳ൅ݔଶሻଷ൅ʹሺͳ൅ݔଷሻଶ൅͵ሺͳ൅ݔሻଶሺͳ൅ݔଶሻଶ
൅ʹሺͳ൅ݔ଺ሻሿ
ൌͳ൅ݔ൅͵ ݔଶ൅͵ݔଷ൅͵ݔସ൅ݔହ൅ݔ଺
Replace ݔൌͳ we get,
The number of benzene rings with ݈ܥ ൌ ͳ൅ͳ൅͵൅͵൅͵൅ͳ൅ͳ ൌ ͳ͵
Therefore there are 13 chemic al compounds obtained in this mann er.
Example 10: Find the number of (simple, undirected) graphs upto isomorphism
on a set of 4 vertices.
Solution: Here D is the set of ሺͶʹሻ pairs of vertices. If there is an edge between
a pair of vertices,

)ig. 7.7
munotes.in

Page 137

137Chapter 8: Polya’s Theory of CountingLet it have content 1, if it has no edge, then let it have cont ent 0.
So, a configuration is a graph, and its content is the number o f edges.
Then ܿሺݔሻൌͳ൅ݔǤ
Now, two labelled graphs are isomorphic if there exists a bijec tion between the
vertices that preserves adjacency (therefore, two graphs are eq uivalent if they are
isomorphic). Now, the group G of symmetries of the set of pairs of vertices is
called ݏ௡ሺଶሻ and its cycle index is
ܼቀݏͶሺʹሻቁൌͳ
ʹͶቂݏͳ͸൅ͻݏͳʹݏʹʹ൅ͺݏ͵ʹ൅͸ݏʹݏͶቃ
Counting series for such graphs
ܲǤܫ ൌሾሺͳ൅ݔሻ଺൅͸ሺͳ൅ݔሻଶሺͳ൅ݔଶሻଶ൅ͺሺͳ൅ݔଷሻଶ൅͸ሺͳ൅ݔଶሻሺͳ൅ݔସሻሿ
ൌͳ൅ݔ൅ʹ ݔଶ൅͵ݔଷ൅ʹݔସ൅ݔହ൅ݔ଺
Replace ݔൌͳ we get,
Total number of unlabelled graphs on 4 vertices ൌͳ൅ͳ൅ʹ൅͵൅ʹ൅ͳ൅ͳൌ
ͳͳ.
Therefore total number of unlabelled graphs on 4 vertices 11
Let us Sum up:
In this unit we have learnt the following:
● Equivalence relations and orbits under a permutation group acti on.
● Basic concept of Orbits and stabiliser, Orbit stabiliser theor em.
● Burnside Lemma and its appl ications base examples.
● Polya’s counting theory with Cycle index, Polya’s theorem and i ts
application.

munotes.in

Page 138

138DISCRETE MATHEMATICSUnit End Exercise
1. Calculate the group of rotational symmetries, and count its orb its on the set
of dimples on the golf ball.
2. How many different 3-colorings of the bands of an n-band stick are there if
the stick is un-oriented"
3. Suppose a necklace can be made from beads of three colors black , white,
and red. How many different necklaces with n beads are there"
4. How many necklaces can be made from a string of 3 black beads a nd 13
white beads"
5. Each face of a cube is painted in one of the following five col ors: red,
green, blue, yellow, or white. Determine the number of cubes th at can be
generated this way, if the color red has to be used exactly two times. Cubes
are considered distinct if they cannot be obtained from each ot her using
rotations.
6. Find the number of distinct squares that can be obtained by pai nting each
edge of a given square in eithe r red or green. Squares are cons idered distinct
if they cannot be obtained from each other using rotations or r eflections.
7. A disc lies in a plane. Its Centre is fixed but it is free to r otate. It has been
divided into n sectors of angle ଶగ
௡. Each sector is to be colored Red or Blue.
How many different colorings are there"
8. How many necklaces of n beads can be made in m colors, if the g roup
acting on them is the cyclic group ܥ௡"
9. Compute the number of distinct colorings of the vertices of a s quare with 3
colors, under the following equivalencies:
a) Rotations are not distinct.
b) Rotations and reflections are not distinct.
c) Rotations, reflections, and color permutations are not distinct .
10. How many distinct organic molecul es can be formed under the fol lowing
stipulation" The geometry of a typical organic molecule has a c arbon atom
at the center of a regular tetrahedron with four valencies goin g towards the
four comers of the regular tetrahedron. munotes.in

Page 139

139Chapter 8: Polya’s Theory of CountingReference:
1. Applied Combinatorics, Alan Tucker.
2. Combinotorial Techniques, Sharad S. Sane
3. Discrete mathematics its Application, Keneth H. Rosen TMG.
4. Discrete mathematics, Norman L. Biggs.
5. Discrete structures by B. Kolman HC Busby, S Ross PHI Pvt. L td.
6. Discrete mathematics, schaum’s outlin es series, seymour Lip Schutz, Marc
Lipson, TMG.

munotes.in