## 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