PERMUTATION AND COMBINATION

Fundamental principle of counting,

Multiplication rule,
If an operation can be performed in m different ways and a second operation can be done in n different ways, then the two operations can be performed in m*n ways. The operations are depending on each other.
Addition rule,
If a operation can be performed in m different ways and another operation independant of the first is performed in n different ways, then either of the two operations are performed in m+n ways.

Factorial notation :
The continued product of first n natural numbers is called n factorial. It is denoted by n!
n!=n(n-1)!
Factorial of negative numbers are not defined.

Permutations
Each of the different arrangements which can be made by taking some or all of a number of things is called permutation.
Number of permutations of n things taken r at a time is nPr=n!/[{n-r}!]

Note :
a. Permutations of n things taken all at a time is nPn=n!
b. Pn=n!

Permutations under conditions :
When all objects are distinct,
a. The no. Of permutations of n different objects taken r at a time when a particular object is to be always included in each arrangement is
r!{(n-1)C(r-1)}.
b. Number of permutations of n different things taken all at a time when m things always come together is m!(n-m+1)!
c. Number of permutations of n different things taken all at a time when m specified things never come together is n!-(n-m+1)!m!
When all objects are not distinct,
The no. Of permutations of n things taken all at a time, p of one kind, q of another kind, and r of the third kind, while the rest of n-(p+q+r) are all different, is
n!/(p+q+r)!

Circular Permutation:
The no. Of circular permutation of n different things taken all at a time is (n-1)!, provided that clockwise and anti-clockwise orders are different. If same, then it (n-1)!/2.
Note : Circular permutation of n things taking r at a time when clockwise and anti-clockwise orders are different is nPr/r and if same then nPr/2r.


Combination :
The different groups or selection that can be made by some or all of a number of given things without reference to the order of the things in each group is called combination.
It is denoted by nCr.
nCr=n!/{(n-r)!r!}.
Note : In a combination only selection is made while in permutation both selection and order is essential.

Properties of combination:
a. nCr=nC(n-r)
b. nCr+nC(r-1)=(n+1)Cr
c. If n is odd then the greatest value of nCr is nC{(n+1)/2} or nC{(n-1)/2}
and if n is even then it is nC(n/2).
d. nCx=nCy, then x=y or x+y=n.
e. nC0+nC1+.....+nCn=2^n
f. nCn+(n+1)Cn+...+(2n-1)Cn = 2nC(n+1)
g. nCr=n{(n-1)C(r-1)}/r
h. nC0+nC2+nC4+... = nC1+nC3+nC4=2^(n-1)
h. Restricted combination,
The number of combinations of n different things taking r at a time when :
i] p things are always included = (n-p)C(r-p)
ii] p things are always excluded = (n-p)Cr
iii] p things are included and q things excluded = (n-p-q)C(r-p).
i. The no. Of combinations of n things taking some or all atleast once at a time is = 2^n - 1.
j. Total selection of some or all out of p+q+r+t items where p,q,r and each distinct and t are different is = {(p+1)(q+1)(r+1)2^t}-1.

Division into groups :
a. The number of ways in which n objects can be split into three groups containing r, s, t objects; r, s, t are distinct and r+s+t=n is given by nCr.(n-r)Cs.(n-r-s)Ct = n!/(r!s!t!)
b. If n objects are to be divided into l groups containing p objects each, m object containing q objects each then ways of group formation,
=n!/{(p!)^l*(q!)^m*l*m} = x
permutations of these = x*{(l+m)!}
Here, lp+mq=n.

Note :
1] if order of group is not important, the number of ways in which mn things can be arranged equally into m groups is
mn!/[{(n!)^m}*m!]
2] if order of group is not important, the number of ways of arranging mn things equally into m groups is (mn!)/{(n!)^m}.

Arrangement into groups :
i. The no. Of ways in which n different things can be arranged into r different groups is r(r-1)(r-2)...(r+n-1) or n!*(n-1)C(r-1) according as blank groups are allowed or not.
ii. The no. Of ways of distributing n things into r parcels
= n!*coefficient of x^n in (e^x-1)^r
= r^n-rC1(r-1)^n+...+(-1)^(r-1)[rC(r-1)].
iii. The no. Of ways of arranging n identical things into r groups is (n+r-1)C(r-1) or (n-1)C(r-1) according as blank groups are admissible or not.

Dearrangements :
If n things are arranged in a row then the no. Of ways in which they can be dearranged so that no one is at the original place is n!(1! - 1/2! + 1/3! +...+(-1)^n*1/n!)

Number of rectangles and squares :
1] no. Of rectangles of any size in a square of n*n is (1^3+2^3+...+n^3) and no. Of squares of any size is (1^2+2^2+...+n^2)
2] In a of rectangle of n*p size, no. Of rectangle of any size is = np(n+1)(p+1)/4 and no. Of squares = summation of (n+r-1)(p+1-r), r=from 1 to n.