Permutations and Combinations

Important Concepts and Formulas 1. Multiplication Theorem (Fundamental Principles of Counting)

If an operation can be performed in $m$ different ways and following which a second operation can be performed in $n$ different ways, then the two operations in succession can be performed in $m\times n$ different ways.

2. Addition Theorem (Fundamental Principles of Counting)

If an operation can be performed in $m$ different ways and a second independent operation can be performed in $n$ different ways, either of the two operations can be performed in $(m+n)$ ways.

3. Factorial

Let $n$ be a positive integer. Then $n$ factorial can be defined as
$n!=n(n-1)(n-2)\cdots 1$

Examples
$5!=5\times 4\times 3\times 2\times 1=1203!=3\times 2\times 1=6$
Special Cases
$0!=11!=1$

4. PermutationsPermutations are the different arrangements of a given number of things by taking some or all at a time.

Examples
All permutations (or arrangements) that can be formed with the letters a, b, c by taking three at a time are (abc, acb, bac, bca, cab, cba)
All permutations (or arrangements) that can be formed with the letters a, b, c by taking two at a time are (ab, ac, ba, bc, ca, cb)

5. CombinationsEach of the different groups or selections formed by taking some or all of a number of objects is called a combination.

Examples
Suppose we want to select two out of three girls P, Q, R. Then, possible combinations are PQ, QR and RP. (Note that PQ and QP represent the same selection.)
Suppose we want to select three out of three girls P, Q, R. Then, only possible combination is PQR

6. Difference between Permutations and Combinations and How to identify them

Sometimes, it will be clearly stated in the problem itself whether permutation or combination is to be used. However if it is not mentioned in the problem, we have to find out whether the question is related to permutation or combination.
Consider a situation where we need to find out the total number of possible samples of two objects which can be taken from three objects P, Q, R. To understand if the question is related to permutation or combination, we need to find out if the order is important or not.
If order is important, PQ will be different from QP, PR will be different from RP and QR will be different from RQ
If order is not important, PQ will be same as QP, PR will be same as RP and QR will be same as RQ
Hence,
If the order is important, problem will be related to permutations.
If the order is not important, problem will be related to combinations.
For permutations, the problems can be like "What is the number of permutations the can be made", "What is the number of arrangements that can be made", "What are the different number of ways in which something can be arranged", etc.
For combinations, the problems can be like "What is the number of combinations the can be made", "What is the number of selections the can be made", "What are the different number of ways in which something can be selected", etc.

pq and qp are two different permutations, but they represent the same combination.

Mostly problems related to word formation, number formation etc will be related to permutations. Similarly most problems related to selection of persons, formation of geometrical figures, distribution of items (there are exceptions for this) etc will be related to combinations.

7. Repetition

The term repetition is very important in permutations and combinations. Consider the same situation described above where we need to find out the total number of possible samples of two objects which can be taken from three objects P, Q, R.
If repetition is allowed, the same object can be taken more than once to make a sample. i.e., PP, QQ, RR can also be considered as possible samples.
If repetition is not allowed, then PP, QQ, RR cannot be considered as possible samples.
Normally repetition is not allowed unless mentioned specifically.

8. Number of permutations of n distinct things taking r at a time

Number of permutations of n distinct things taking r at a time can be given by

ⁿP_r = $\frac{n!}{(n-r)!}$ $=n(n-1)(n-2)...(n-r+1)$ where $0\le r\le n$

Special Cases
ⁿP₀ = 1
ⁿP_r = 0 for $r>n$
ⁿP_r is also denoted by P(n,r). ⁿP_r has importance outside combinatorics as well where it is known as the falling factorial and denoted by (n)_r or n^r

Examples
⁸P₂ = 8 × 7 = 56
⁵P₄= 5 × 4 × 3 × 2 = 120

9. Number of permutations of n distinct things taking all at a time
Number of permutations of n distinct things taking them all at a time
= ⁿP_n = n!

10. Number of Combinations of n distinct things taking r at a time
Number of combinations of n distinct things taking r at a time ( ⁿC_r) can be given by 
ⁿC_r = $\frac{n!}{(r!)(n-r)!}$ $=\frac{n(n-1)(n-2)\cdots (n-r+1)}{r!}$ where $0\le r\le n$
Special Cases
ⁿC₀ = 1
ⁿC_r = 0 for $r>n$
ⁿC_r is also denoted by C(n,r). ⁿC_r occurs in many other mathematical contexts as well where it is known as binomial coefficient and denoted by $(\frac{n}{r})$

Examples
⁸C₂ = $\frac{8\times 7}{2\times 1}$ = 28
⁵C₄= $\frac{5\times 4\times 3\times 2}{4\times 3\times 2\times 1}$ = 5