## Tuesday, 18 October 2011

### Applications of Permutations & Combinations

A-I) To find the Rank of a word
This is one of the traditional types. Here we elaborate on a simple example to find rank of word ‘MATH’:
First we arrange the letters alphabetically - A,H,M,T
Now we find number of words starting with each letter in the alphabetical order.
Number of words starting with A = 3! = 6    (Arrangements of remaining three letters – ‘M’ , ‘T’ and ‘H’)
Number of words starting with H = 3! = 6    (Arrangements of remaining three letters – ‘A’ , ‘M’ and ‘T’)
Our word ‘MATH’ is in the next set of words ie., words starting with ‘M’
First word in this set- MAHT
Second word is – MATH, there we are. So rank of the word = 6 + 6 + 2 = 14
A-2) To find the number of straight lines passing through distinct points
Given ‘m’ points in a plane out of which ‘p’ points are collinear and no other three points are collinear.
To form a line two points are required. So from the given ‘m’ points, we are supposed to get mC2 lines (why not mP2 ???,because we are selecting two points and thats all, we need not arrange them). But since
‘p’ out of the given ‘m’ points are collinear, by joining these ‘p’ points we get only one line instead of pC2 lines.
The number of lines formed = mC2 – pC2 + 1

A-3) To find the number of triangles formed by joining distinct points
Given ‘m’ points in a plane out of which ‘p’ points are collinear and no other three points are collinear.
To form a triangle three points are required. So from the given m points, we are supposed to get mC3 triangles. But since ‘p’ out of the given ‘m’ points are collinear, no triangle can be formed from these ‘p’ points instead of estimated pC3 triangles.
The number of triangles formed = mC3 –pC3

A-4) Two sets of intersecting parallel lines forming parallelograms
Find the number of parallelograms formed when a set of m parallel lines intersects another set of n parallel lines:
Parallelogram is formed when one pair of parallel lines intersects with another pair. Hence we need to select one pair each from the given two sets of parallel lines. Here selection only is involved but no arrangement. So we go for nCr but not nPr.
One pair of lines (ie., 2 lines) can be selected from first set of ‘m’ lines in mC2 ways and second pair from second set of ‘n’ lines in nC2 ways. Both can be performed in (mC2)*(nC2) ways (can be understood form the fundamental principle).
Hence number of parallelograms formed = (mC2)*(nC2)

A-5) Number of Squares and Rectangles  in a nXn square
Consider the following 2X2 square:
To find number of squares in the above diagram:
Number of 1X1 squares = 4    (ABED, BCFE, DEHG, EFIH)
Number of 2X2 squares = 1    (ACIG)
Total number of squares = 4 + 1 = 5 = 22 + 1
Similarly for 3X3 square, we get 14 = 9+4+1 = 32+22+1
The general formula is Σn2

To find number of rectangles in the above diagram:
(We consider squares also as rectangles)
Number of 1X1 rectangles = 4                        (ABED, BCFE, DEHG, EFIH)
Number of 1X2 and 2X1 rectangles = 4          (ACFD, DFIG, ABHG, BCIH)
Number of 2X2 rectangles =1                         (ACIG)
Total number of rectangles = 4 + 4 + 1 = 9 which can be expressed as

Similarly for 3X3 square, we get 36 , which can be expressed as 33+23+13
The general formula for rectangles is Σn3

If we consider 3X3 square, we can find 36 rectangles.
The logic here is nXn square is formed by two sets of n+1 number of parallel lines, and to form a rectangle we need 2 lines from each set thus forming (n+1)C2 * (n+1)C2 rectangles
Number of squares in a nXn square = Σn2
Number of rectangles in a nXn square = Σn3

A-6) To find Number of divisors
If a given number n can be expressed as p1k1. p2k2. P3k3...... pnkn
Where p1, p2, p3,... pn are prime numbers and k1,k2,k3,...kn are positive integers
(This is nothing but factorisation of the given number and expressing in the form of exponents),
then total number of divisors of the given number = (k1+1) (k2+1) (k3+1)... (kn+1)
Explanation:
Observe that this is corollary of the theorem of all possible selections (similar things).
Divisors of p1k1 are 1,p1, p12,p13,.... p1k1           – resulting in (k1+1) numbers
Divisors of p2k2 are 1,p2, p22,p23,.... p2k2           – resulting in (k2+1) numbers
And so on and so on...
Divisors of pnkn are 1,pn, pn2,pn3,.... pnkn          – resulting in (kn+1) numbers
By applying fundamental principle, this results in (k1+1) (k2+1) (k3+1)... (kn+1) number of divisors