Permutation and Combination

Basic formulas - Permutation and Combination

n Factorial: It is the product of first 'n' natural numbers. 'n factorial' is denoted as n!.
n! = 1 × 2 × 3 × ... × n

Example: 2! = 1 × 2 = 2; 3! = 1 × 2 × 3 = 6; 4! = 1 × 2 × 3 × 4 = 24
NOTE: 0! = 1! = 1

Fundamental Principle of Counting

Multiplication Rule: If there are two jobs such that one of them can be completed in 'm' ways and when it has been completed in any one of the 'm' ways, then the second job can be completed in 'n' ways. So, total ways to complete the two jobs are m × n ways.

Similarly, if there is a task that involves 'k' jobs such that the first job can be performed in m1 ways, second job in m2, ... , kth job in mk ways. Then, total ways to complete the task are m1 × m2 × ... × mk.

Example 1: A hall has 12 gates. In how many ways, can a man enter the hall through one gate and come out through a different gate?

Solution: Since, there are 12 gates of entering the hall, the man comes out through a different gate in 11 ways. Hence, by fundamental principle of multiplication, total number of ways are 12 × 11 = 132
Addition Rule: If there are two jobs such that they can be performed independently in 'm' and 'n' ways respectively, then either of the two jobs can be performed in m + n ways.
Similarly, if there are 'k' independent jobs, each of which can be performed in mi ways, then the total number of ways of performing all things simultaneously is m1 + m2 + ... + mk.
Here, the jobs are mutually exclusive.

Example 2: There are 25 students in a class with 15 boys and 10 girls. The class teacher selects either a boy or a girl for monitor post of the class. In how many ways, the class teacher can make this selection?

Solution: There are 15 boys and 10 girls and a monitor selected can be anyone from the given students.
Hence, required number of ways = 15 + 10 = 25

Download: Seating Arrangement around Geometrical Figures

Combination:

Number of ways of selecting 'r' things out of 'n' things is given by nCr.
nCr
nCr = nCn-r
Keyword over here is selection.
nCr - 1 + nCr = n + 1Cr

Permutation:

Number of ways of selecting 'r' things out of 'n' things and then arranging these 'r' things is given by nPr.
nPr
Keyword over here is selection and arrangement.

Total number of permutations of 'n' objects is n!.
Total number of linear arrangements (arrangements in a row) of 'n' things is n!.

Example 3: Suppose that you want to arrange 6 books on a shelf. In how many ways can you do it.

Solution: Total number of permutations of 6 objects is 6!. So, 6 books can be arranged on a shelf in 6! ways.

Example 4: In how many different ways 5 girls can be seated in a row.

Solution: Number of ways in which 5 girls can be seated in a row = 5! = 120 ways.

Permutation of 'r' objects out of 'n' objects:

Suppose that we have 'n' objects and we have to arrange 'r' of these in 'r' boxes, one in each box (Given that ).
So, Box-1 can be filled in 'n' ways
Box-2 can be filled in 'n-1' ways
Box-3 can be filled in 'n-2' ways
.
.
Box-r can be filled in 'n - r + 1' ways
So, 'r' boxes can be filled in ways.


Download: Permutation and Combination Practice Questions

Example 5: Suppose there are 5 books, and we want to distribute one book to each of A,B,C. In how many ways can this be done.

Solution: We can give one of the 5 books to A, one of the remaining 4 books to B, and one of the remaining 3 books to 'C'.
Total number of ways are 5×4×3 = 120.

Other Formulas:
C(n,n) = C(n,0) = 1
C(n,r) = C(n,n-r) = P(n,r)/r!
C(n,0) + C(n,1) + C(n,2) + ... + C(n,n) = 2n
C(n,1) + C(n,2) + ... + C(n,n) = 2n - 1


prep4paper.com