Basics of Permutation and Combination

In this article, we will understand the very basic concepts of Permutation and Combination (P & C), and also learn to differentiate between the two.

Concept of P & C

Combination - Each of the groups or selections which can be made by taking some or all of a number of items.

Combinations implies ‘selection’ - the order in which the items are taken is not considered as long as the specific things are included.

Permutation - Each of the arrangements which can be made by taking some or all of a number of items.

Permutation implies ‘arrangement’ – ‘order of the items’ is important.

Selection:
Suppose there are 3 books: A, B and C. We have to select 2 books out of these 3. This can be done in 3 ways. i.e. (A and B), (B and C), (C and A). – Selection of A & B is the same as selecting B & A etc.
When we select something, we use the word ‘combination’, represented by C.

Arrangement:
If we are to choose the best and the second best book, there will be 6 ways of doing so, i.e. (A, B), (B, A), (B, C), (C, B), (C, A), (A, C).
Here (A, B) and (B, A) are different because in the first scenario A is the best book, while in the second scenario it is the second best book.
When we arrange something, we use the word permutation, represented by P.

Identifying the Problem

When you encounter a P & C problem, the first thing you should do is to find out whether it is permutation or combination that is being discussed.

• Some times the problem states this explicitly:
  
  For permutations, “Find the number of permutations that can be made …” OR “Find the number of arrangements that can be made…..” OR “Find the number of ways in which you can arrange…..” (notice the use of keywords permutation and arrangement)
  
  For combinations, “Find the number of combinations that can be made…..” OR “Find the number of selections that can be made…..” OR “Find the number of ways in which you can select…..” (notice the use of keywords combination and selection)

• Some times the problem states this implicitly:
  
  ‘How many five-digit numbers can be made from the digits 1, 3, 6, 7 and 9 using each digit once?’
  Here, the order of the digits matters, as different orders will make different numbers. So, this is a question of arrangement/permutation.
  
  ‘Out of a group of six friends, I have to invite two for lunch. In how many different ways can it be done?’
  Here, order of items is not important. E.g. if I invite friend 3 and friend 5, then this selection is all I have to do. It does not matter if I invite friend 3 first or friend 5 first. So, this is a question of selection/combination.
  
  

$C^n_r$ and $P^n_r$

Number of combinations of n different things taken r at a time or Selection of r things out of n different things is given by:

$C^n_r$ = $\frac{n!}{r!(n-r)!}$

Number of arrangements of n different things taken r at a time or Selecting r things out of n different things and then arranging these r things is given by:

$P^n_r$ = $\frac{n!}{(n-r)!}$

Q. Find the number of permutations and combinations if n = 6 and r = 2.

Explanation:

Property 1

$C^n_0$ = $\frac{n!}{0!(n-0)!} $ = $\frac{n!}{n!} $ = 1

$C^n_n$ = $\frac{n!}{n!(n-n)!} $ = $\frac{n!}{n!} $ = 1

Property 2

$C^n_r$ = $C^n_{n-r}$ (for 0 ≤ r ≤ n)

Q. Find the value of $C^9_7$.

Explanation:

Property 3

If x and y are non-negative integers such that $C^n_x$ = $C^n_y$ , then:
x = y or x + y = n

Q. If $C^n_8$ = $C^n_{15}$, then what is the value of n?

Explanation:

Property 4

$C^n_{r-1}$ + $C^n_r$ = $C^{n+1}_r$

(n and r are non-negative integers such that r ≤ n)

For example, $C^5_2 + C^5_3 = C^{5+1}_3 = C^6_3$

Property 5

$C^n_0$ + $C^n_1$ + $C^n_2$ + ……+ $C^n_n$ = $2^n$