Permutation & Combinations

Permutation & Combinations

FUNDAMENTAL PRINCIPLE OF COUNTING


Rule of Product

If one experiment has n possible outcomes and another experiment has m possible outcomes, then there are m × n possible outcomes when both of these experiments are performed.

In other words if a job has n parts and the job will be completed only when each part is completed and the first part can be completed in a1 ways, the second part can be completed in

a₂ ways and so on.... the nth part can be completed in an ways, then the total number of ways of doing the job is a₁a₂a₃... an. This is known as the rule of product.


Rule of Sum

If one experiment has n possible outcomes and another has m possible outcomes, then there are (m + n) possible outcomes when exactly one of these experiments is performed.

In other words if a job can be done by n methods and by using the first method can be done in a1 ways or by second method in a₂ ways and so on ... by the nth method in an ways,

then the number of ways to get the job can be done is (a₁ + a₂ + .... + a_n).


Factorial of an integer

Let n N. The continued product of first n natural numbers is called the factorial n and is denoted by n! or .

We define 0! = 1 and hence by definition

n! = n(n - 1)(n - 2) ... 2.1 = 1. 2. 3 ... n.

Also, from the definition, n! = n [(n - 1)!].

We do not define the factorial of negative integers or proper fractions. Since for negative integers the product never ends


Note:
(m + n)! m! + n!; (mn)! (m!) (n!);

(m - n)! m! - n!; .


PERMUTATIONS (Arrangements of Objects):

The number of permutations of n objects, taken r at a time, is the total number of arrangements

of n objects, in groups of r where the order of the arrangement is important.


(i) Without repetition

(a) Arranging n objects, taking r at a time in every arrangement, is equivalent to filling r places from n things.

r-Places:
Number of Choices:	n	n-1	n-2	n-3		n - (r - 1)

Number of ways of arranging = Number of ways of filling r places

= n(n - 1) (n - 2) ... (n - r + 1)

= = = ⁿP_r.


(b) Number of arrangements of n different objects taken all at a time = ⁿP_n = n!.


Note:
1.Since ⁿP_n = n!, we have .

2. ⁿP_r , r > n is undefined (more than available objects can not be arranged).

3. ⁿP₀ is the number of permutation of n objects taken 0 at a time .



(ii) With repetition

(a) Number of permutations (arrangements) of n different objects, taken r at a time, when each object may occur once, twice, thrice, ... upto r times in any arrangements = Number of

ways of filling r places, each out of n objects.

r-Places:
Number of Choices:	n	n	n	n		n

Number of ways to arrange = Number of ways to fill r places = (n)^r.


(iii) Number of arrangements that can be formed using n objects out of which p are identical (and of one kind), q are identical (and of one kind), r are identical (and of one kind) and

rest are different = .


Circular Permutations

The arrangements we have considered so far are linear. There are also arrangements in closed loops, called circular arrangements.

Suppose n persons (a₁, a₂, a₃,...,a_n) are to be seated around a circular table. There are n! ways in which they can be seated in a row. On the other hand, all the linear arrangements

a₁, a₂, a₃, ........., a_n

a_n, a₁, a₂,..........,a_{n - 1}

a_{n - 1}, a_n, a₁, a₂.....a_{n - 2}

.........................

.........................

a₂, a₃, a₄,..........,a₁

will lead to the same arrangements for a circular table. Hence one circular arrangements corresponds to n unique row (linear) arrangements. Let x be the number of circular permutation

and number of permutation that can be formed from n things is

n! nx = n! x = (n - 1)!.


Distinction between clockwise and Anti-clockwise Arrangements

Consider the following circular arrangements:




In figure I the order is clockwise whereas in figure II, the order is anti-clock wise. These are two different arrangements. When distinction is made between the clockwise and the anti-

clockwise arrangements of n different objects around a circle, then the number of arrangements = (n - 1)! .

But if no distinction is made between the clockwise and anti-clockwise arrangements of n different objects around a circle, then the number of arrangements is (n - 1)! .


Note:

(i) When the positions are numbered, circular arrangements is treated as a linear arrangement.

 

In a linear arrangements it does not make difference whether the positions are numbered

or not.

 

Number of circular permutations of n different things taken r at a time

= (if clockwise and anticlockwise orders are taken as different)

= (if clockwise and anticlockwise orders are not taken to be different).



Combinations:

Meaning of combination is selection of objects. In many practical problems, the interest is in selection without arranging. We denote the number of ways of selecting r objects out of n

objects by ⁿC_r. Obviously r n. When r = o, no object is being selected and this is the only combination. Hence ⁿC₀ = 1. For r = 1, one object is being selected out of n and there are

n combinations so that ⁿC₁ = n.


Selection of objects without repetition:

 

The number of selections (combinations or groups) that can be formed from n different objects taken r (0 r n) at a time is .


=

For r = 0,

For r = 1,

For r = n,

.



Selection of objects with repetition

The number of combinations of n distinct objects taken r at a time when each may occur once, twice, thrice,..... upto r times, in any combination = ^{n + r - 1}C_r .


Restricted selection/ Arrangement:

(a) The number of ways in which r objects can be selected from n different objects if k particular objects are

(i) always included = ^n-k C_r-k ,

(ii) never included = ^n-k C_r.


(b) The number of arrangement of n distinct objects taken r at a time so that k particular objects are

(i) always included = ^n-k C_r-k .r!,

(ii) never included = ^n-k C_r .r! .


Some results related to ⁿC_r

1.If ⁿC_r = ⁿC_k , then r = k or n-r =k

^2.nC_r + ⁿC_r-1 = ⁿ⁺¹C_r for ⁿC_r + ⁿC_r-1

3.


^{4. n}C_r = ^n-1C_r-1 for ⁿC_r =.


5. for r.ⁿC_r =.


6.(a) If n is even , ⁿC_r is greatest for r = n/2

(b) If n is odd, ⁿC_r is greatest for r = ,


All possible selections:

 

Selection from distinct objects:

The number of selections from n different objects, taking at least one

= ⁿC₁ + ⁿC₂+ ⁿC₃+------ + ⁿC_n = 2ⁿ-1.

This also includes the case when none is selected. And the number of such cases = 1.


Selection from identical objects:

(a) The number of selections of r objects out of n identical objects is 1.

(b) Total number of selections of zero or more objects from n identical objects is n+1.

(c) Total number of selections of at least one out of a₁+a₂+a₃+----+a_n objects , where a₁ are alike (of one kind ), a₂ are alike (of second kind ) and so on ------a_n are alike (of nth kind ), is [(a₁+1)(a₂+1)(a₃+1)-------(a_n+1)]-1.



Selection when both identical and distinct objects are present:

The number of selections, taking at least one out of a₁+a₂+a₃+----+a_n+k objects, where a₁ are alike (of one kind), a₂ are alike (of second kind) and so on ---------a_n are alike (of nth

kind), and k are distinct ={[(a₁+1)(a₂+1)(a₃+1)-------(a_n+1)] 2^k} - 1.



(iv). Total number of divisors of a given natural number

To find the number of factors of a given natural number greater than 1 we can write n as n =, where p₁, p₂, ... ,p_n are distinct prime numbers and a₁, a₂,...a_n are non-

negative integers. Now any divisor of n will be of the form

d = ; here number of factors will be equal to numbers of ways in which we can choose b_is' which can be done in (a₁ + 1)(a₂ + 1)...(a_n + 1) ways.

Sum of all the divisors of n is given by

.


Division and distribution of objects

(with fixed number of objects in each group)

(i) Into groups of unequal size (different number of objects in each group)

(a) Number of ways, in which n distinct objects can be divided into r unequal groups containing a₁ objects in the first group, a₂ objects in the second group and so on

==

Here a₁+a₂+a₃+----+a_r = n.


(b) Number of ways in which n distinct objects can be distributed among r persons such that first person get a₁ objects, 2^nd person get a₂ objects --------- rth person gets a_r objects =

.



Into groups of equal size (each group containing same number of objects)

Number of ways in which m×n distinct objects can be divided equally into n groups (unmarked) =.

Number of ways in which m× n different objects can be distributed equally among n persons (or numbered groups) = (number of ways of dividing)×(number of groups)!


=



Derangements

Any change in the existing order of things is called a derangement.

If 'n' things are arranged in a row, the number of ways in which they can be deranged so that none of them occupies its original place is


= n!and it is denoted by D(n).



Multinomial Theorem

Let x₁, x₂,...,x_m be integers. Then number of solutions to the equation

x₁ + x₂ + ... + x_m = n . . . (1)

subject to the conditions a₁ x₁ b₁, a₂ x₂ b₂, ..., a_m x_m b_m . . . (2)

is equal to the coefficient of xⁿ in

. . . . (3)

This is because the number of ways in which sum of m integers in (1) subject to given conditions (2) equals n is the same as the number of times xⁿ comes in (3).

Some Important Results

 

(1) Number of ways of distribution of n distinct balls in r distinct boxes when order is considered

= n! ^n-1C_r-1, if blank (empty) boxes are not allowed.

And it is :

= n! ^n+r-1C_r-1 if blank (empty) boxes are allowed.



(2) Number of ways of distribution of n identical balls into r distinct boxes

= ^n-1C_r-1, if blank (empty) boxes are not allowed.

And it is :

= ^n+r-1C_r-1 if blank (empty) boxes are allowed.


(3) Number of ways of distribution of n distinct balls into r distinct boxes when order is not considered = rⁿ, if blank (empty) boxes are allowed.

And it is= rⁿ - ^rC₁(r-1)ⁿ + ^rC₂(r-2)ⁿ - ^rC₃(r-3)ⁿ + ..... +(-1)^{r-1 r}C_r-1 , if blank (empty) boxes are not allowed.


(4) The number of combinations of n objects of which p are identical taken r at a time is = ^n-pC_r + ^n-pC_r-1 + ^n-pC_r+1+....+ ^n-pC₀ if r p

and it is= ^n-pC_r + ^n-pC_r-1 + ^n-pC_r+1+....+ ^n-pC_r-p if r > p.


(5) The coefficient of x^r in the expansion of (1-x)^-n = ^n+r-1C_r.



Use of Series

(1) If there are n₁ objects of one kind, n₂ objects of second kind and so on n_k objects of k^th kind; then the number of ways of choosing r objects out of these objects is

= coeff of x^r in (1+x+x²+.... +)(1+x+x²+.... +) .... (1+ x + x²+.... +).


(2) If one object of each kind is to be included in selection of (1) , then the number of ways of choosing r objects is:

= coeff of x^r in (x+x²+.... +)(x+x²+.... +).... (x+x²+.... +)


(3) The number of possible arrangements / permutations of p objects out of n₁ objects of kind 1, n₂ of kind 2 and so on is = p! times the coefficient of x^p in the expansion

.