Basic Counting Principles

Sum Rule Principle: Assume some event E can occur in m ways and a second event F can
occur in n ways, and suppose both events cannot occur simultaneously. Then E or F can
occur in m + n ways.

In general, if there are n events and no two events occurs in same time then the event can
occur in n1+n2..........n ways.

Example: If 8 male processor and 5 female processor teaching DMS then the student can
choose professor in 8+5=13 ways.

Product Rule Principle: Suppose there is an event E which can occur in m ways and,
independent of this event, there is a second event F which can occur in n ways. Then
combinations of E and F can occur in mn ways.

In general, if there are n events occurring independently then all events can occur in the
order indicated as n1 x n2 x n3.........n ways.

Example: In class, there are 4 boys and 10 girls if a boy and a girl have to be chosen for
the class monitor, the students can choose class monitor in 4 x 10 = 40 ways.

Mathematical Functions:
Factorial Function: The product of the first n natural number is called factorial n. It is
denoted by n!, read "n Factorial."

The Factorial n can also be written as

1. n! = n (n-1) (n-2) (n-3)......1.

2. = 1 and 0! = 1.

Example1: Find the value of 5!

Solution:

5! = 5 x (5-1) (5-2) (5-3) (5-4)

= 5 x 4 x 3 x 2 x 1 = 120

Example2: Find the value of

Solution: = = 10 x 9=90

Binomial Coefficients: Binomial Coefficient is represented by nCr where r and n are

positive integer with r ≤ n is defined as follows:

Example: 8C2 = = = 28.

Permutation and Combinations:

Permutation:
Any arrangement of a set of n objects in a given order is called Permutation of Object.
Any arrangement of any r ≤ n of these objects in a given order is called an r-
permutation or a permutation of n object taken r at a time.

It is denoted by P (n, r)

P (n, r) =

Theorem: Prove that the number of permutations of n things taken all at a time is n!.

Proof: We know that

Example: 4 x np3=n+1P3

Solution: 4 x

4 (n-2) = (n+1)
4n - 8 = n+1
 3n = 9
n = 3.

Permutation with Restrictions:

The number of permutations of n different objects taken r at a time in which p particular
objects do not occur is

The number of permutations of n different objects taken r at a time in which p particular

objects are present is

Example: How many 6-digit numbers can be formed by using the digits 0, 1, 2, 3, 4, 5, 6,
7, 8 if every number is to start with '30' with no digit repeated?

Solution: All the numbers begin with '30.'So, we have to choose 4-digits from the
remaining 7-digits.

∴ Total number of numbers that begins with '30' is

7P4 = =840.

Permutations with Repeated Objects:

Theorem: Prove that the number of different permutations of n distinct objects taken at
a time when every object is allowed to repeat any number of times is given by n r.

Proof: Assume that with n objects we have to fill r place when repetition of the object is
allowed.

Therefore, the number of ways of filling the first place is = n

The number of ways of filling the second place = n
.............................
.............................
The number of ways of filling the rth place = n
Thus, the total number of ways of filling r places with n elements is
= n. n. n..............r times =nr.

Circular Permutations:
A permutation which is done around a circle is called Circular Permutation.

Example: In how many ways can get these letters a, b, c, d, e, f, g, h, i, j arranged in a

circle?

Solution: (10 - 1) = 9! = 362880

Theorem: Prove that the number of circular permutations of n different objects is (n-1)!

Proof: Let us consider that K be the number of permutations required.

For each such circular permutations of K, there are n corresponding linear permutations.
As shown earlier, we start from every object of n object in the circular permutations.
Thus, for K circular permutations, we have K...n linear permutations.
Combination:
A Combination is a selection of some or all, objects from a set of given objects, where
the order of the objects does not matter. The number of combinations of n objects,
taken r at a time represented by nCr or C (n, r).

Proof: The number of permutations of n different things, taken r at a time is given by

As there is no matter about the order of arrangement of the objects, therefore, to every
combination of r things, there are r! arrangements i.e.,

Example: A farmer purchased 3 cows, 2 pigs, and 4 hens from a man who has 6 cows, 5
pigs, and 8 hens. Find the number m of choices that the farmer has.

The farmer can choose the cows in C (6, 3) ways, the pigs in C (5, 2) ways, and the hens
in C (8, 4) ways. Thus the number m of choices follows:
The Pigeonhole Principle
If n pigeonholes are occupied by n+1 or more pigeons, then at least one pigeonhole is
occupied by greater than one pigeon. Generalized pigeonhole principle is: - If n
pigeonholes are occupied by kn+1 or more pigeons, where k is a positive integer, then
at least one pigeonhole is occupied by k+1 or more pigeons.

Example1: Find the minimum number of students in a class to be sure that three of
them are born in the same month.

Solution: Here n = 12 months are the Pigeonholes

And k + 1 = 3
K=2

Example2: Show that at least two people must have their birthday in the same month if
13 people are assembled in a room.

Keep Watching

Solution: We assigned each person the month of the year on which he was born. Since
there are 12 months in a year.

So, according to the pigeonhole principle, there must be at least two people assigned to
the same month.

Inclusion-Exclusion Principle:
Let A1,A2......Ar be the subset of Universal set U. Then the number m of the element
which do not appear in any subset A1,A2......Ar of U.

Example: Let U be the set of positive integer not exceeding 1000. Then |U|= 1000 Find
|S| where S is the set of such integer which is not divisible by 3, 5 or 7?

Solution: Let A be the subset of integer which is divisible by 3

Let B be the subset of integer which is divisible by 5
Let C be the subset of integer which is divisible by 7

Then S = Ac ∩ Bc∩ Cc since each element of S is not divisible by 3, 5, or 7.

By Integer division,

|A|= 1000/3 = 333

|B|= 1000/5 = 200
|C| = 1000/7 = 142
|A∩B|=1000/15=66
|B∩C|=1000/21=47
|C∩A|=1000/35=28
|A∩B∩C|=1000/105=9

Thus by Inclusion-Exclusion Principle

|S|=1000-(333+200+142)+(66+47+28)-9
|S|=1000-675+141-9=457

Recurrence Relations
A recurrence relation is a functional relation between the independent variable x,
dependent variable f(x) and the differences of various order of f (x). A recurrence relation
is also called a difference equation, and we will use these two terms interchangeably.

Example1: The equation f (x + 3h) + 3f (x + 2h) + 6f (x + h) + 9f (x) = 0 is a recurrence

relation.

It can also be written as

ar+3 + 3ar+2 + 6ar+1 + 9ar = 0

yk+3 + 3yk+2 + 6yk+1 + 9yk = 0

Example2: The Fibonacci sequence is defined by the recurrence relation ar = ar-2 + ar-1,
r≥2,with the initial conditions a0=1 and a1=1.

Order of the Recurrence Relation:

The order of the recurrence relation or difference equation is defined to be the difference
between the highest and lowest subscripts of f(x) or ar=yk.

Example1: The equation 13ar+20ar-1=0 is a first order recurrence relation.

Example2: The equation 8f (x) + 4f (x + 1) + 8f (x+2) = k (x)

Degree of the Difference Equation:
The degree of a difference equation is defined to be the highest power of f (x) or ar=yk

Example1: The equation y3k+3+2y2k+2+2yk+1=0 has the degree 3, as the highest power of
yk is 3.

Example2: The equation a4r+3a3r-1+6a2r-2+4ar-3 =0 has the degree 4, as the highest power
of ar is 4.

Example3: The equation yk+3 +2yk+2 +4yk+1+2yk= k(x) has the degree 1, because the
highest power of yk is 1 and its order is 3.

Example4: The equation f (x+2h) - 4f(x+h) +2f(x) = 0 has the degree1 and its order is 2.

Linear Recurrence Relations with Constant

Coefficients
A Recurrence Relations is called linear if its degree is one.

The general form of linear recurrence relation with constant coefficient is

C0 yn+r+C1 yn+r-1+C2 yn+r-2+⋯+Cr yn=R (n)

Where C0,C1,C2......Cn are constant and R (n) is same function of independent variable n.

A solution of a recurrence relation in any function which satisfies the given equation.

Linear Homogeneous Recurrence Relations with Constant

Coefficients:
The equation is said to be linear homogeneous difference equation if and only if R (n) = 0 and it
will be of order n.

The equation is said to be linear non-homogeneous difference equation if R (n) ≠ 0.

Example1: The equation ar+3+6ar+2+12ar+1+8ar=0 is a linear non-homogeneous equation of

order 3.

Example2: The equation ar+2-4ar+1+4ar= 3r + 2r is a linear non-homogeneous equation of order

2.
A linear homogeneous difference equation with constant coefficients is given by

C0 yn+C1 yn-1+C2 yn-2+⋯......+Cr yn-r=0 ....... equation (i)

Where C0,C1,C2.....Cn are constants.

The solution of the equation (i) is of the form , where ∝1 is the characteristics root and A is
constant.

Substitute the values of A ∝K for yn in equation (1), we have

C0 A∝K+C1 A∝K-1+C2 A∝K-2+⋯....+Cr A∝K-r=0.......equation (ii)

After simplifying equation (ii), we have

C0 ∝r+C1 ∝r-1+C2 ∝r-2+⋯Cr=0..........equation (iii)

The equation (iii) is called the characteristics equation of the difference equation.

If ∝1 is one of the roots of the characteristics equation, then is a homogeneous solution to

the difference equation.

To find the solution of the linear homogeneous difference equations, we have the four cases that
are discussed as follows:

Case1: If the characteristic equation has n distinct real roots∝1, ∝2, ∝3,.......∝n.

Thus, are all solutions of equation (i).

Also, we have are all solutions of equation (i). The sums of

solutions are also solutions.

Hence, the homogeneous solutions of the difference equation are

Case2: If the characteristics equation has repeated real roots.

If ∝1=∝2, then (A1+A2 K) is also a solution.

If ∝1=∝2=∝3 then (A1+A2 K+A3 K2) is also a solution.

Similarly, if root ∝1 is repeated n times, then.

(A1+A2 K+A3 K2+......+An Kn-1)

The solution to the homogeneous equation.

Case3: If the characteristics equation has one imaginary root.

If α+iβ is the root of the characteristics equation, then α-iβ is also the root, where α and β are
real.

Thus, (α+iβ)K and (α-iβ)K are solutions of the equations. This implies

(α+iβ)K A1+α-iβ)K A2

Is also a solution to the characteristics equation, where A 1 and A2 are constants which are to be
determined.

Case4: If the characteristics equation has repeated imaginary roots.

When the characteristics equation has repeated imaginary roots,

(C1+C2 k) (α+iβ)K +(C3+C4 K)(α-iβ)K

Is the solution to the homogeneous equation.

Example1: Solve the difference equation ar-3ar-1+2ar-2=0.

Solution: The characteristics equation is given by

s2-3s+2=0 or (s-1)(s-2)=0
⇒ s = 1, 2

Therefore, the homogeneous solution of the equation is given by

ar=C1r+C2.2r.

Example2: Solve the difference equation 9yK+2-6yK+1+yK=0.

Solution: The characteristics equation is

 9s2-6s+1=0 or (3s-1)2=0

⇒s= and

Therefore, the homogeneous solution of the equation is given by

yK=(C1+C2 k).

Example3: Solve the difference equation yK-yK-1-yK-2=0.

Solution: The characteristics equation is s2-s-1=0

s=

Therefore, the homogeneous solution of the equation is

Example4: Solve the difference equation yK+4+4yK+3+8yK+2+8yK+1+4yK=0.

Solution: The characteristics equation is s4+4s3+8s2+8s+4=0

(s2+2s+2) (s2+2s+2)=0
s = -1±i,-1±i

Therefore, the homogeneous solution of the equation is given by

yK=(C1+C2 K)(-1+i)K+(C3 +C4 K)(-1-i)K

Particular Solution
(a) Homogeneous Linear Difference Equations and Particular
Solution:
We can find the particular solution of the difference equation when the equation is of
homogeneous linear type by putting the values of the initial conditions in the
homogeneous solutions.
Example1: Solve the difference equation 2ar-5ar-1+2ar-2=0 and find particular solutions
such that a0=0 and a1=1.

Solution: The characteristics equation is 2s2-5s+2=0

(2s-1)(s-2)=0

s= and 2.

Therefore, the homogeneous solution of the equation is given by

ar(h)= C1 +C2 .2r..........equation (i)

Putting r=0 and r=1 in equation (i), we get

a0=C1+C2=0...........equation (a)

a1= C1+2C2=1...........equation.(b)

Solving eq (a) and (b), we have

C1=- and C2=

Hence, the particular solution is

Example2: Solve the difference equation ar-4ar-1+4ar-2=0 and find particular solutions
such that a0=0 and a1=6.

Solution: The characteristics equation is

s2-4s+4=0 or (s-2)2=0 s = 2, 2

Therefore, the homogeneous solution of the equation is given by

ar(n)=(C1+C2 r).2r.............. equation (i)

Putting r = 0 and r = 1 in equation (i), we get

a0=(C1+0).20 = 1 ∴C1=1
a1=(C1+C2).2=6 ∴C1+C2=3⇒C2=2
Hence, the particular solution is
ar(P)=(1+2r).2r.

Example3: Solve the difference equation 9ar-6ar-1+ar-2=0 satisfying the conditions a0=0
and a1=2.

Solution: The characteristics equation is

9s2-6s+1=0 or (3s-1)2=0

s=

Therefore, the homogeneous solution of the equation is given by

ar(h)=(C1+C2 r). ..........equation (i)

Putting r = 0 and r = 1 in equation (i), we get

a0=C_1=0

a1= (C1+C2). =2. ∴C1+C2=6⇒C2=6

Hence, the particular solution is

ar(P)=6r. .

(b) Non-Homogeneous Linear Difference Equations and

Particular Solution:
There are two methods to find the particular solution of a non-homogeneous linear
difference equation. These are as follows:

1. Undetermined coefficients method

2. E and ∆ operator method.

1. Undetermined Coefficients Method: This method is used to find a particular

solution of non-homogeneous linear difference equations, whose R.H.S term R (n)
consist of terms of special forms.
 In this method, firstly we assume the general form of the particular solutions according
to the type of R (n) containing some unknown constant coefficients, which have to be
determined. Then according to the difference equation, we will determine the exact
solution.

The general form of a particular solution to be assumed for the special forms of R (n), to
find the exact solution is shown in the table.

Form of R (n) General form to be assumed

Z, here z is constant A

Zr, here z is constant Zr

P (r), a polynomial of degree n A0 rn+A1 rn-1+⋯..An

Zr. P (r), here P(r) is a polynomial of the nth degree in r. Z is a constant. [A0 rn+A1 rn-1+⋯..An].Zr

Example1: Find the particular solution of the difference equation ar+2-

3ar+1+2ar=Zr ........equation (i)

Where Z is some constant.

Solution: The general form of solution is = A. Zr

Now putting this solution on L.H.S of equation (i), we get

= A Zr+2-3AZr+1+2AZr=(Z2-3Z+2) A Zr.........equation (ii)

Equating equation (ii) with R.H.S of equation (i), we get

(Z2-3Z+2)A=1

A= (Z≠1, Z≠2)

Therefore, the particular solution is

Example2: Find the particular solution of the difference equation ar+2-
5ar+1+6ar=5r .............equation (i)

Solution: Let us assume the general form of the solution= A. 5r.

Now to find the value of A, put this solution on L.H.S of the equation (i), then this
becomes
= A. 5r+2-5.A5r+1+6.A5r
= 25A. 5r-25A.5r+6A.5r
= 6A.5r ............equation (ii)

Equating equation (ii) to R.H.S of equation (i), we get

A=

Therefore, the particular solution of the difference equation is = .5r.

Example3: Find the particular solution of the difference equation

ar+ 2+ar+1+ar=r.2r..........equation (i)

Solution: Let us assume the general form of the solution = (A0+A1r). 2^r

Now, put these solutions in the L.H.S of the equation (i), we get
= 2r+2 [A0+A1 (r+2)]+2r+1 [A0+A1 (r+1)]+2r (A0+A1 r)
= 4. 2r (A0+A1 r+2A1 )+2.2r (A0+A1 r+A1 )+2r (A0+A1 r)
= r. 2r (7A1 )+2r (7A0+10A1)............equation (ii)

Equating equation (ii) with R.H.S of equation (i), we get

7A1=1 ∴ A1=

7A0+10A1=0 ∴ A0=

Therefore, the particular solution is

2. E and ∆ operator Method:

Definition of Operator E: The operator of E on f(x) means that give an increment to the
value of x in the function. The operation of E is, put (x+h) in the function wherever there
is x. Here h is increment quantity. So Ef(x) = f(x+h)

Here, E is operated on f(x), therefore, E is a symbol known as shift operator.

Definition of Operator∆: The operation ∆ is an operation of two steps.

Firstly, x in the function is incremented by a constant and then former is subtracted from
the later i.e.,
∆f(x)=f(x+h)-f(x)

Theorem1: Prove that E ≅1+∆.

Proof: The operation of ∆ on f(x) is of two steps. First, increment the value of x in the
function. So, whenever, there is x in f(x) put x+h (here h is constant increment), which
means operation of E on f(x) i.e.,
f (x+h)=Ef(x).

Second, subtract the original function from the value obtained in the first step, hence
∆f(x)=Ef(x)-1f(x)=(E-1)f(x)

So, the operation of ∆ on f(x) is equivalent to the operation of (E-1) on f(x).

Therefore, we have
E ≅1+∆.

Theorem2: Show that En f(x)=f(x+nh).

Proof: We know that E f(x) =f (x+h)

Now En f(x)=E.E.E.E.........n times f(x)

= En-1 [E f(x)] = En-1 f(x+h)
= En-2 [E f(x+h)] = En-2 f(x+2h)
......................
......................
= E f[x+ (n-1) h] = f(x+nh).

Theorem3: Show that E Cf(x) = CE f(x)

Proof: We know that E C f(x) = C f(x+h) = CE f(x+h). Hence Proved.

There is no effect of the operation of E on any constant. Therefore, the operation of E on
any constant will be equal to constant itself.

By E and ∆ operator method, we will find the solution of

C0 yn+r+C1 yn+r-1+C2 yn+r-2+⋯+Cn yn=R (n)..............equation (i)

Equation (i) can be written as

C0 Er yn+C1 Er-1 yn+C2 Er-2 yn+⋯+Cn yn=R (n)
(C0 Er+C1 Er-1+C2 Er-2+⋯+Cn) yn=R (n)
Putting C0 Er+C1 Er-1+C2 Er-2+⋯+Cn=P(E)

So P (E) yn=R (n)

∴ yn= ................equation (ii)

To find the particular solution of (ii) for different forms of R (n), we have the following
cases.

Case1: When R (n) is some constant A.

We know that, the operation of E on any constant will be equal to the constant itself i.e.,
EA=A
Therefore, P (E) A = (C0 Er+C1 Er-1+C2 Er-2+⋯+Cn)A
= (C0+C1+C2+⋯+Cn)A
= P (1) A

Therefore, using equation (ii), the particular solution of (i) is

yn= ,P(1)≠0

P (1) is obtained by putting E = 1 in P (E).

Case2: When R (n) is of the form A. Zn, where A and Z are constants

We have, P (E) (A. Zn)={C0 Er+C1 Er-1+⋯+ Cn} ([Link])

=A{C0 Zr+n+C1 Zr+n-1+⋯+Cn Zn}
= A{C0 Zr+C1 Zr-1+⋯+Cn }. Zn
=AP(Z).Zn

To get, P (Z) put E=Z in P (E)

Therefore, , provided P (Z) ≠ 0

Thus, yn= , P (Z) ≠ 0

If A = 1, then yn=

When P (Z) = 0 then for equation

(i) (E-Z) yn= A. Zn

For this, the particular solution becomes A. Zn=A. n Zn-1

(ii) (E-Z)2 yn= A. Zn

For this, the particular solution becomes

(iii) (E-Z)3 yn= A. Zn

For this, the particular solution becomes and so on.

Case3: When R (n) be a polynomial of degree m is n.

We know that E≅1+∆

So, P (E) =P (1+∆)

Which can be expanded in ascending power of ∆ as far as upto ∆m

⇒ =(b0+b1 ∆+b2 ∆+⋯.+bm ∆m+⋯)

⇒ .R(n)=( b0+b1 ∆+b2 ∆+⋯.+bm ∆m+⋯).R(n)

= b0 R(n)+b1 ∆ R(n)+⋯+bm ∆m R(n)

All other higher terms will be zero because R (n) is a polynomial of degree m.
Thus, the particular solution of equation (i), in this case will be

yn=b0 R(n)+b1 ∆ R(n)+⋯.+bm ∆m R(n).

Case4: When R (n) is of the form R(n).Zn,where R(n) is a polynomial of degree m and Z is
some constant

We have Er[Zn R(n)]=Zr+n R (n+r)=[Link].R(n)=Zn (ZE)rR(n)

Similarly, we have

[Zn R(n)]=Zn .(R(n))= Zn [P(Z+Z∆)]-1.R(n)

Thus, the particular solution of equation (i), in this case will be

yn=Zn [P(Z+Z∆)]-1.R(n)

Example1: Find the particular solution of the difference equation

2ar+1-ar=12.

Solution: The above equation can be written as

(2E-1) ar=12

The particular solution is given by

ar= .12

Put E=1, in the equation. The particular solution is ar=12

Example2: Find the particular solution of the difference equation ar-4ar-1+4ar-2=2r.

Solution: The above equation can be written as

(E2-4E+4) ar=2r

Therefore, P (E) = E2-4E+4 = (E-2)2

Thus, the particular solution is given by