# Permutations and Combinations - Tricks & important formulas

## Combinations

Combinations are basically 'selections without replacements' of distinct objects.

In selection, the order of the objects doesn't matter. Means, when we are selecting two distinct objects, say A and B and this is same as the selection of B and A.

Comparison of permutation and combination:
Let us consider a group of 4 distinct objects, A, B, C and D.
Combination (Selection of any two objects)Permutation (Arrangements of the selected objects)
AB AB, BA
AC AC, CA
BC BC, CB
BD BD, DB
CD CD, DC
6 combinations 12 permutations

In the above example, we can easily observe that each of the selection of two objects has 2! corresponding arrangements.

Similarly, in general, each of the selection of 'r' distinct objects should have 'r!' corresponding arrangements.

(Selections of 'r' distinct objects) * r = Arrangements of the selected objects.

i.e. Combinations of 'r' objects = Permutations of r objects / r!

Combination of 'r' distinct objects out of a total of 'n' distinct objects is expressed as nCr,

where n > 0, n ≥ r, r ≥ 0.

Therefore, nCr = nPr/r! = n!/((n-r)! r!)

In general, Combination of 'n' objects taken 'r' at a time, denoted by n and is defined as

 n = ncr = n! / (n-r)! r!

## Important properties and results of combinations.

• The number of ways to select 'no' objects out of 'n' distinct objects is,
nc0 =n!/0!(n-0)! = 1
• The number of ways to select exactly one object out of n distinct objects is,
nc0 =n!/1!(n-1)! = n
• The number of ways to select 'all' the objects out of 'n' distinct objects is,
nc0 =n!/n!(n-n)! = n
• The number ways to select 'r' objects out of 'n' distinct objects is equal to the number of selections of 'n - r' objects out of 'n' objects.

i.e. nCr = nC(n - r)

Example: 6C4 = 6!/4!(6-4)! = 6!/4! 2!

6C(6 - 4) = 6C2 = 6!/2!(6-2)! = 6!/2! 4!

i.e. 6C4 = 6C2

 How to find the numerical value of nCr easily? Instead of applying the entire results of nCr, you can follow the below method for finding the numerical value of nCr. Try to keep the value of 'r' as least as possible by applying the result nCr = nC(n - r). Eg: Find the value of 10C8. We know that 10C8 = 10C2 10C2 = Product of two consecutive numbers from 10 in descending order / Product of two consecutive numbers from 1 in ascending order= 10 *9/1 *2 = 45 Similarly; 15C3 = 15 * 14 * 13 / 1 * 2 *3 21C16 = 21C5 = 21 * 20 * 19 * 18 * 17 / 1 * 2 * 3 * 4 * 5

Values to remember:

The table of values of nC2 plays an important role in solving problems from combinations. So, if you want to become more professional in this area of counting, it is better to by heart following table.

 2C2 = 1 3C2 = 3 4C2 = 6 5C2 = 10 6C2 = 15 7C2 = 21 8C2 = 28 9C2 = 36 10C2 = 45 11C2 = 55 12C2 = 66 13C2 = 78 14C2 = 91 15C2 = 105 16C2 = 120 17C2 =136 18C2 = 153 19C2 = 171 20C2 = 190

## Additional important results in Combinations

In this area, we are dealing with some very important counting tricks under Combinations (Selections). These are the frequently tested results in exams. So show an extra interest in the following results and properties of Combinations.

 Result 1: Number of ways to select 'zero or more' objects out of 'n' distinct objects = 2n OR nC0 + nC1 + nC2 + ..... + nCn = 2n

Proof:

Here we have to count from the side of objects. Each of the 'n' distinct objects has two possibilities: either selected or not selected.

Hence the total number of selections (zero or more) out of the 'n' distinct objects = 2n

Example: A class test is conducted for 5 students, how many different ways a result card can be entered such that the result card contains only the details whether the student is passed or failed?

Each of the five students has exactly two possible results: PASS or FAIL.

Hence the total number of possible entries = 25 = 32

 Result 2: Number of ways to select 'at least one' objects out of 'n' distinct objects = 2n - 1 OR nC1 + nC2 + nC3 + ..... + nCn = 2n - 1

Example:

How many different ways you can invite at least one among your five friends for your birthday party?

Each of your 5 friends has two possibilities: invited or not invited.

Hence the total number of possibilities = 25 = 32

But out of these 32 possibilities, one possibility is 'none among them is invited'.

Avoid this one possibility from the entire 32 possibilities for satisfying the condition of 'at least one'.

Therefore the required number of ways = 25 - 1 = 32 - 1 = 31

 Result 3: Number of ways to select 'r' objects out of 'n' identical objects = 1

Example:

Find the number of ways to select 3 toys out of 5 identical toys?

Here toys are identical, hence the number of ways = 1

 Result 4: Number of ways to select 'zero or more' objects out of 'n' identical objects = n + 1 Where 0 ≤ r ≤ n.

Example:

How many different ways can select zero or more apples out of 5 identical apples?

Here the difference in selections only depends upon the number of apples.

i.e. You can select 0, 1, 2, 3, 4 or 5 apples.

Hence there is 5 + 1 = 6 different selections are possible.

 Result 5: Number of ways to select 'zero or more' objects out of 'p + q + r' objects of which p objects are alike of one kind, q objects are alike of second kind and r objects are alike of third kind is {(p + 1) (q + 1) (r + 1)}

Example: How many different ways of selections of zero or more fruits are possible from 3 identical apples and 2 identical oranges?

Here again the number of selection is only based on the number of fruits from two different categories.

The possible selections can be tabulated in the following manner.

ApplesOranges
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
3 0
3 1
3 2
Hence a total of (3+ 1) (2 + 1) = 4 * 3 = 12 ways
 Result 6: Number of ways to select 'at least one' objects out of 'p + q + r' objects of which p objects are alike of one kind, q objects are alike of second kind and r objects are alike of third kind is {(p + 1) (q + 1) (r + 1)}- 1.

Example: How many different ways of selections of at least one fruits are possible from 3 identical apples and 2 identical oranges?

From the above illustrated tabulation of the selections, one section is (0, 0), i.e. No apple and no orange. Avoid this selection from the above mentioned total possible selections for satisfying the condition of 'at least one' fruit.

Hence the required number of selections = 12 - 1 = 11

 Result 7: Number of ways to select 'zero or more' objects out of 'p + q + r' objects of which p objects are alike of one kind, q objects are alike of second kind and r distinct objects is {(p + 1) (q + 1) 2r}.

Example: How many different ways can select 'zero or more' fruits from 2 identical apples, 3 identical oranges and 4 distinct fruits other than apple or orange?

Required number of selections = (2 +1) (3 + 1) 24 = 3 * 4 * 16 = 192

 Result 8: Number of ways to select 'at least one' objects out of 'p + q + r' objects of which p objects are alike of one kind, q objects are alike of second kind and r distinct objects is {(p + 1) (q + 1) 2r}- 1.

Example: How many different ways can select 'at least one' fruits from 2 identical apples, 3 identical oranges and 4 distinct fruits other than apple or orange?

Required number of selections = {(2 +1) (3 + 1) 24 } - 1 = (3 * 4 * 16) - 1 = 192 - 1 = 191

 Result 9: Number of selections of 'k' consecutive (adjacent) objects from a row of 'n' objects is (n - k + 1)

Examples:

Five persons are seated in a row, how many different ways can select 3 adjacent persons?

Solution:

From the diagram, it is easy to understand that the selections can be done in 3 ways.

i.e. (1, 2, 3), (2, 3, 4) or (3, 4, 5).

i.e. The number of ways to select 3 adjacent persons out of a row of 5 persons = 5 - 3 + 1 = 3

## Geometrical application of combinations.

Total numbers of diagonals in a polygon having 'n' sides

Consider a polygon having 'n' sides (n vertices). We have to find the number of diagonals in this polygon. If we subtract the number of sides from all possible number of lines which can be formed by join these n vertices, then the remaining will be the number of diagonals.

Total number of lines which can be formed by join the 'n' vertices = combination of 'n' vertices taken two at a time =nc2

Note: Any questions (in this manner) based on lines are the concept of combinations.

Since line join from v1 to v2 in some lines join from v2 to v1 and here is no possibility to form a line by joining v1 to v1.

Replacement is not possible and there is no role for order.

Questions based on lines are combination.

Total number of sides on the polygon is 'n'

Number of diagonals = Total number of possible lines - Number of sides

= nc2 -n

 Number of diagonals in an 'n' sided polygon = nc2 -n
Page 2 of 2