Permutation and Combination

Factorial Notation

Let n be positive integer.Then factorial n denoted by n! is defined as n! = n(n-1)(n-2). . . . . . . .3.2.1.

For example, 5! = (5 * 4* 3 * 2 * 1) = 120

  • 0! = 1

Fundamental Principles of Counting

Addition Rule

If an experiment can be performed in 'n' ways, & another experiment can be performed in 'm' ways, then either of the two experiments can be performed in (m+n) ways. This rule can be extended to any finite number of experiments.

Multiplication Rule

If a work can be done in 'm' ways, another work can be done in 'n' ways, then both of the operations can be performed in m x n ways. It can be extended to any finite number of operations.

Permutations

The different arrangements of a given number of things by taking some or all at a time, are called permutations. For example, all permutations (or arrangements) made with the letters a, b, c by taking two at a time are (ab, ba, ac, ca, bc, cb)

Numbers of Permutations

Number of all permutations of n things taken r at a time is given by

nPr = n(n-1)(n-2). . .. . . (n-r+1) = n!/(n-r)!

Important Results

The number of permutations of n dissimilar things taken all at a time is nPn = n!

The number of permutations of n dissimilar things taken r at a time, when repetition of things is allowed any number of times is nr

If there are n objects of which p1 are alike of one kind, p2 are alike of another kind, p3 are alike of third kind such that p1+p2+p3=n, then the number of permutation of these n objects is n! / (p1!).(p2!).(p3!)

Circular Permutations

If the things are arranged around a circle, then a permutation is called a circular permutation.

In circular permutation, there is no first or last place of an object. Hence, the principles of linear permutations are not applicable in circular permutations. In such type of permutations, the relative positions of the things alone need to be taken into consideration and not the actual position.

The number of circular permutation of n different things taken all at a time around a circle is (n - 1)!

If any arrangement of n different things around a circle in the clockwise direction is considered to be not different from the similar arrangement in the anti-clockwise direction, then, the number of circular permutations of n different things is (n-1)!/2.

Combinations

Each of different groups or selections which can be formed by taking some or all of a number of objects, is called a combination. For example, suppose you want to select two out of three items A, B, C; then possible selection are AB, BC and CA. Note that AB and BA represent the same selection.

Number of Combination

The number of all combination of n things taken r at a time is:

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

Important Results

  • nCn = 1
  • nC0 =1
  • nCr = nC(n-r)

Distribution of Things into Groups

The number of ways in which things can be divided into two different groups of m and n things respectively is (m+n)!/m!n!

Important Results

The total number of combinations of (p + q) things taken any number at a time when p things are alike of one kind and q things are alike of a second kind is (p + 1)(q + 1) - 1.

The total number of ways of selecting one or more objects from n given objects is (2n - 1).