## Important Concepts and Formulas - Permutations and Combinations

1. Multiplication Theorem (Fundamental Principles of Counting)

If an operation can be performed in different ways and following which a second operation can be performed in different ways, then the two operations in succession can be performed in different ways.

If an operation can be performed in different ways and a second independent operation can be performed in different ways, either of the two operations can be performed in ways.

**3. Factorial**

Let be a positive integer. Then factorial can be defined as

**Examples**

**Special Cases**

4. Permutations

Permutations are the different arrangements of a given number of things by taking some or all at a time.

**Examples**

All permutations (or arrangements) that can be formed with the letters a, b, c by taking three at a time are (abc, acb, bac, bca, cab, cba)

All permutations (or arrangements) that can be formed with the letters a, b, c by taking two at a time are (ab, ac, ba, bc, ca, cb)

5. Combinations

Each of the different groups or selections formed by taking some or all of a number of objects is called a combination.

**Examples**

Suppose we want to select two out of three girls P, Q, R. Then, possible combinations are PQ, QR and RP.

*(Note that PQ and QP represent the same selection.)*
Suppose we want to select three out of three girls P, Q, R. Then, only possible combination is PQR

Sometimes, it will be clearly stated in the problem itself whether permutation or combination is to be used. However if it is not mentioned in the problem, we have to find out whether the question is related to permutation or combination.

Consider a situation where we need to find out the total number of possible samples of two objects which can be taken from three objects P, Q, R. To understand if the question is related to permutation or combination, we need to find out if the order is important or not.

If order is important, PQ will be different from QP, PR will be different from RP and QR will be different from RQ

If order is not important, PQ will be same as QP, PR will be same as RP and QR will be same as RQ

Hence,

If the order is important, problem will be related to permutations.

If the order is not important, problem will be related to combinations.

If the order is important, problem will be related to permutations.

If the order is not important, problem will be related to combinations.

For permutations, the problems can be like "What is the number of permutations the can be made", "What is the number of arrangements that can be made", "What are the different number of ways in which something can be arranged", etc.

For combinations, the problems can be like "What is the number of combinations the can be made", "What is the number of selections the can be made", "What are the different number of ways in which something can be selected", etc.

pq and qp are two different permutations, but they represent the same combination.

Mostly problems related to word formation, number formation etc will be related to permutations. Similarly most problems related to selection of persons, formation of geometrical figures, distribution of items (there are exceptions for this) etc will be related to combinations.

The term repetition is very important in permutations and combinations. Consider the same situation described above where we need to find out the total number of possible samples of two objects which can be taken from three objects P, Q, R.

If repetition is allowed, the same object can be taken more than once to make a sample. i.e., PP, QQ, RR can also be considered as possible samples.

If repetition is not allowed, then PP, QQ, RR cannot be considered as possible samples.

Normally repetition is not allowed unless mentioned specifically.

**8. Number of permutations of n distinct things taking r at a time**

Number of permutations of n distinct things taking r at a time can be given by

^{n}P_{r}= where**Special Cases**

^{n}P

_{0}= 1

^{n}P

_{r}= 0 for

^{n}P

_{r}is also denoted by P(n,r).

^{n}P

_{r}has importance outside combinatorics as well where it is known as the falling factorial and denoted by (n)

_{r}or n

^{r}

**Examples**

^{8}P

_{2}= 8 × 7 = 56

^{5}P

_{4}= 5 × 4 × 3 × 2 = 120

**9. Number of permutations of n distinct things taking all at a time**

Number of permutations of n distinct things taking them all at a time

=

=

^{n}P_{n}= n!
Number of combinations of n distinct things taking r at a time (

^{n}C_{r}) can be given by^{n}C_{r}= where**Special Cases**

^{n}C

_{0}= 1

^{n}C

_{r}= 0 for

^{n}C

_{r}is also denoted by C(n,r).

^{n}C

_{r}occurs in many other mathematical contexts as well where it is known as binomial coefficient and denoted by

**Examples**

^{8}C

_{2}= = 28

^{5}C

_{4}= = 5

Permutations under RestrictionsCase 1: When s particular things are always to be included

Number of permutations of n distinct things taking r at a time, when s particular things are always to be included in each arrangement, is

(r−s) objects can be selected from the (n−s) objects in

s objects can be selected from s objects only 1 way.

Totally r objects are selected and these can be arranged in r! ways.

Total number of arrangements =

Some text books give the formula as

As you can see, both these formulas are indeed the same.

^{(n-s)}C_{(r-s)}× r!__Derivation of the formula__(r−s) objects can be selected from the (n−s) objects in

^{(n-s)}C_{(r-s)}ways.s objects can be selected from s objects only 1 way.

Totally r objects are selected and these can be arranged in r! ways.

Total number of arrangements =

^{(n-s)}C_{(r-s)}× r!__Alternative Form__Some text books give the formula as

^{(n-s)}P_{(r-s)}×^{r}P_{s}which is same as^{(n-s)}C_{(r-s)}× r!^{(n-s)}C_{(r-s)}× r!^{(n-s)}P_{(r-s)}×^{r}P_{s}As you can see, both these formulas are indeed the same.

Number of permutations of n distinct things taking r at a time, when a particular thing is always to be included in each arrangement, is

Derivation of the formula is similar to that of case 1.

As we have seen for case 1, the same formula can also be expressed as

^{(n-1)}C_{(r-1)}× r!Derivation of the formula is similar to that of case 1.

__Alternative Form__As we have seen for case 1, the same formula can also be expressed as

^{(n-1)}P_{(r-1)}× r
Number of permutations of n distinct things taking r at a time, when s particular things are never included is

Remove the s objects which are never included and we are left with (n-s) objects. r objects can be selected from these (n−s) objects in

r objects can be arranged in r! ways.

Total number of arrangements

=

^{(n-s)}C_{r}× r!__Derivation of the formula__Remove the s objects which are never included and we are left with (n-s) objects. r objects can be selected from these (n−s) objects in

^{(n-s)}C_{r}ways.r objects can be arranged in r! ways.

Total number of arrangements

=

^{(n-s)}C_{r}× r!
Number of permutations of n distinct things taking r at a time, when a particular thing is never included, is

Derivation of the formula is similar to that of case 3.

^{(n-1)}C_{r}× r!Derivation of the formula is similar to that of case 3.

**Case 5: When m particular things always come together knowledgPhilic.com**

Number of permutations of n distinct things taking them all at a time, when m particular things always come together, is

(n-m+1)! × m!

Group these m objects and consider it as a single object. Then the total number objects = (n-m+1). These (n-m+1) objects can be arranged in (n-m+1)! ways

m objects can be arranged in m! ways.

Total number of arrangements = (n-m+1)! × m!

(n-m+1)! × m!

__Derivation of the formula__Group these m objects and consider it as a single object. Then the total number objects = (n-m+1). These (n-m+1) objects can be arranged in (n-m+1)! ways

m objects can be arranged in m! ways.

Total number of arrangements = (n-m+1)! × m!

Number of permutations of n distinct things taking them all at a time, when m particular things never come together, is

n! - (n – m + 1)! × m!

Total number of arrangements possible using n distinct objects taking all at a time = n!

Number of arrangements of n distinct things taking all at a time, when m particular things always come together, is

(n-m+1)! × m!

Hence, number of permutations of n distinct things taking all at a time, when m particular things never come together

= n! - (n-m+1)! × m!

n! - (n – m + 1)! × m!

__Derivation of the formula__Total number of arrangements possible using n distinct objects taking all at a time = n!

Number of arrangements of n distinct things taking all at a time, when m particular things always come together, is

(n-m+1)! × m!

*(As we have seen in case 5)*Hence, number of permutations of n distinct things taking all at a time, when m particular things never come together

= n! - (n-m+1)! × m!

More Concepts and Formulas - PermutationsPermutations of objects when all objects are not distinct

Number of ways in which things can be arranged taking them all at a time, when of the things are exactly alike of

^{st}type, of them are exactly alike of a^{nd}type ... of them are exactly alike of^{th}type and the rest all are distinct is
Number of permutations of distinct things taking at a time when each thing may be repeated any number of times is

Number of circular permutations (arrangements) of distinct things

Number of circular permutations (arrangements) of distinct things, when clockwise and anticlockwise arrangements are not different (i.e., when observations can be made from both sides)

Useful Relations - Permutations and Combinations

n! = n.(n-1)!

^{n}C_{r}=^{n}P

_{n}= n!

^{n}P

_{0}= 1

^{n}P

_{1}= n

^{n}P

_{n}=

^{n}P

_{n - 1}

^{n}P

_{r}= n(

^{n-1}P

_{r-1})

^{n}C

_{r}=

^{n}C

_{(n - r)}

Example

^{8}C_{6}=^{8}C_{2}^{n}C

_{n}= 1

^{n}C

_{0}= 1

^{n}C

_{r-1}+

^{n}C

_{r}=

^{(n+1)}C

_{r}(Pascal's Law)

^{n}C

_{0}+

^{n}C

_{1}+

^{n}C

_{2}+ ... +

^{n}C

_{n}= 2

^{n}

Example

^{4}C_{0}+^{4}C_{1}+^{4}C_{2}+^{4}C_{3}+^{4}C_{4}
If

^{n}C_{x}=^{n}C_{y}then either x = y or (n-x) = y
(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.

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

Geometrical Figures - Permutations and Combinations

In this chapter, we are dealing with formulas related to geometrical figures using the principles of permutations and combinations.

Number of quadrilaterals that can be formed by joining the vertices of a polygon of n sides

=

=

^{n}C_{4}
Suppose there are n points in a plane out of which m points are collinear. Number of triangles that can be formed by joining these n points as vertices

=

=

^{n}C_{3}-^{m}C_{3}
Suppose there are n points in a plane out of which no three points are collinear. Number of triangles that can be formed by joining these n points

=

=

^{n}C_{3}
Suppose there are n points in a plane out of which m points are collinear. Number of straight lines that can be formed by joining these n points

=

=

^{n}C_{2}-^{m}C_{2}+ 1
Suppose there are n points in a plane out of which no points are collinear. Number of straight lines that can be formed by joining these n points

=

=

^{n}C_{2}
Number of rectangles that can be formed by using m horizontal lines and n vertical lines

=

=

^{m}C_{2}×^{n}C_{2}
More Formulas in Permutations and Combinations

If all possible digit numbers using distinct non-zero digits are formed, sum of all the numbers so formed

× (sum of the digits) × (111 ... times)

× (sum of the digits) × (111 ... times)

**Number of handshakes**

Suppose there are persons present in a party and every person shakes hand with every other person. Then, total number of handshakes

=

^{n}C

_{2}

**Derangements**

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

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

Counting non-negative integral solutionsNumber of non-negative integral solutions of equation

= Number of ways in which identical balls can be distributed into distinct boxes

=

= Number of ways in which identical balls can be distributed into distinct boxes

=

^{(k+n-1)}C_{(n-1)}
Counting positive integral solutionsNumber of positive integral solutions of equation

= Number of ways in which identical balls can be distributed into distinct boxes where each box must contain at least one ball

=

= Number of ways in which identical balls can be distributed into distinct boxes where each box must contain at least one ball

=

^{(k-1)}C_{(n-1)}**Example 1:**Find number of non-negative integral solutions of the equation

One solution is

Another solution is

Note that is not a solution because each must be a non-negative integer.

Total number of solutions

=

Another solution is

Note that is not a solution because each must be a non-negative integer.

Total number of solutions

=

^{(k+n-1)}C_{(n-1)}=^{(7+4-1)}C_{(4-1)}=^{10}C_{3}= 120**Example 2:**Find number of positive integral solutions of the equation

**Solution 1**

Using the formula, required number of solutions

=

^{(k-1)}C

_{(n-1)}=

^{(15-1)}C

_{(3-1)}=

^{14}C

_{2}= 91

**Solution 2**

Give one to , one to and one to .

Remaining quantity is 15-3=12 which is to be distributed to and

Therefore, required number of solutions

= number of non-negative integral solutions of

=

^{(k+n-1)}C

_{(n-1)}=

^{(12+3-1)}C

_{(3-1)}=

^{14}C

_{2}= 91

**Example 3:**A lift starts at the basement with 10 people (6 men and 4 women, excluding the operator) and all get out by the time lift reaches 5

^{th}floor. Find the number of ways in which the operator could have perceived the people leaving the lift if all people look alike to the operator?

Required number of ways (knowledgPhilic.in)

= Number of non-negative integer solutions to

=

= Number of non-negative integer solutions to

=

^{(k+n-1)}C_{(n-1)}=^{(10+5-1)}C_{(5-1)}=^{14}C_{4}= 1001
Let be integers.

Then the number of solutions to the equation

subject to the conditions

is equal to the coefficient of in

Then the number of solutions to the equation

subject to the conditions

is equal to the coefficient of in

Distributing Balls into Boxes

Here, we are counting the number of ways in which k balls can be distributed into n boxes under various conditions.

The conditions which are generally asked are

1. The balls are either distinct or identical.

2. The boxes are either distinct or identical.

3. No box can contain more than one ball or any box may contain more than one ball.

4. No box can be empty or any box can be empty.

2. The boxes are either distinct or identical.

3. No box can contain more than one ball or any box may contain more than one ball.

4. No box can be empty or any box can be empty.

This is an area which many students choose to ignore. However these concepts will help us in solving many advanced problems in permutations and combinations.

We can use the principles of permutations and combinations to deal with problems of distributing balls into boxes. The concept of identical boxes are more complicated and generally studied in detail in combinatorics.

The table below explains the number of ways in which k balls can be distributed into n boxes under various conditions. All the below mentioned cases are derived under the assumption that the order in which the balls are placed into the boxes is not important. (i.e., if a box has many balls, the order of the balls inside the box is not important).

Distribution of | How many balls boxes can contain | ||||

k Balls | into n Boxes | No Restrictions | ≤ 1 (At most one) | ≥ 1 (At least one) | = 1 (Exactly one) |

Distinct | Distinct | n^{k}(formula 1) | ^{n}P_{k}(formula 2) | S(k,n) × n! (formula 3) | ^{n}P_{n} = n! if k = n0 if k ≠ n (formula 4) |

Identical | Distinct | ^{(k+n-1)}C_{(n-1)}(formula 5) | ^{n}C_{k}(formula 6) | ^{(k-1)}C_{(n-1)}(formula 7) | 1 if k = n 0 if k ≠ n (formula 8) |

Distinct | Identical | (formula 9) | 1 if k ≤ n 0 if k > n (formula 10) | S(k,n) (formula 11) | 1 if k = n 0 if k ≠ n (formula 12) |

Identical | Identical | (formula 13) | 1 if k ≤ n 0 if k > n (formula 14) | P(k, n) (formula 15) | 1 if k = n 0 if k ≠ n (formula 16) |

**S(k,n), Stirling number of the second kind**can be defined as

**Special Cases**

S(0,0) = 1

S(k,0) = 0 for k ≥ 1

S(k,n) = 0 for k < n

**P(k,n) = The number of partitions of the integer k into n parts**.

Formula for P(k,n) is much harder than that of S(k, n). The following examples will explain how we can find the value of P(k,n).

**What is the value of P(6,3) ?**

The partitions of 6 into 3 parts are

4 + 1 + 1

3 + 2 + 1

2 + 2 + 2

(Note that 4 + 1 + 1, 1 + 4 + 1, 1 + 1 + 4 are same. Similarly we need to consider all other cases as well)

Hence the number of partitions of 6 into 3 parts = 3

=> P(6,3) = 3

**What is the value of P(6,2) ?**

The partitions of 6 into 2 parts are

1 + 5

2 + 4

3 + 3

Hence the number of partitions of 6 into 2 parts = 3

=> P(6,2) = 3

**What is the value of P(6,1) ?**

Here, we count the number of partitions of 6 into 1 part.

Clearly the number of such partitions = 1

=> P(6,1) = 1

**Now try to find out the value of P(6,4)**

The partitions of 6 into 4 parts are

1 + 1 + 1 + 3

1 + 2 + 2 + 2

Hence the number of partitions of 6 into 4 parts = 2

=> P(6,4) = 2

**Special Cases**

P(0, 0) = P(k, k) = P(k, k-1) = P(k, 1) = 1

1. Division and Distribution of Distinct Objects

Number of ways in which n distinct things can be divided into r unequal groups containing a

=

(Note that )

_{1}, a_{2}, a_{3}, ......, a_{r}things*(different number of things in each group and the groups are unmarked, i.e., not distinct)*=

^{n}C_{a1}×^{(n-a1)}C_{a2}× ... ×^{(n-a1-a2 - ... -ar-1)}C_{ar}(Note that )

Number of ways in which n distinct things can be distributed among r persons such that one person get a

= Number of ways in which n distinct things can be divided into r unequal groups containing a

(Note that )

_{1}things, another person get a_{2}things, ... and another person gets a_{r}things*(each person gets different number of things)*= Number of ways in which n distinct things can be divided into r unequal groups containing a

_{1}, a_{2}, a_{3}, ......, a_{r}things*(different number of objects in each group and the groups are numbered, i.e., distinct)*(Note that )

Number of ways in which distinct things can be divided equally into groups

*(each group will have m things and the groups are unmarked, i.e., not distinct)*
Number of ways in which distinct things can be distributed equally among persons

= Number of ways in which distinct things can be divided equally into groups

*(each person gets m number of things)*= Number of ways in which distinct things can be divided equally into groups

*(each group will have m things and the groups are numbered, i.e., distinct)*
2. Division and Distribution of Identical Objects

Number of ways in which n identical things can be divided into r groups, if blank groups are allowed

= Number of ways in which n identical things can be distributed among r persons, each one of them can receive 0,1,2 or more items

=

*(here groups are numbered, i.e., distinct)*= Number of ways in which n identical things can be distributed among r persons, each one of them can receive 0,1,2 or more items

=

^{(n+r-1)}C_{(r-1)}
Number of ways in which n identical things can be divided into r groups, if blank groups are not allowed

= Number of ways in which n identical things can be distributed among r persons, each one of them can receive 1,2 or more items

=

*(here groups are numbered, i.e., distinct)*= Number of ways in which n identical things can be distributed among r persons, each one of them can receive 1,2 or more items

=

^{(n-1)}C_{(r-1)}
Combinations under Restrictions

Number of combinations of n distinct things taking r at a time, when s particular things are always to be included in each selection, is

^{(n-s)}C_{(r-s)}
Number of combinations of n distinct things taking r at a time, when a particular thing is always to be included in each selection, is

^{(n-1)}C_{(r-1)}
Number of combinations of n distinct things taking r at a time, when s particular things are never included in any selection, is

^{(n-s)}C_{r}
Number of combinations of n distinct things taking r at a time, when m particular things never come together in any selection, is

^{n}C_{r}-^{(n-m)}C_{(r-m)}
More Concepts and Formulas - Combinations

Number of combinations of n distinct objects taking r at a time when each object may be repeated any number of times

=

=

^{(n+r-1)}C_{r}
Number of ways in which one or more objects can be selected from n distinct objects

=

*(i.e., we can select 1 or 2 or 3 or … or n objects at a time)*=

^{n}C_{1}+^{n}C_{2}+ ... +^{n}C_{n}= 2^{n}- 1
Number of ways in which one or more objects can be selected out of S

= (S

_{1}alike objects of one kind, S_{2}alike objects of second kind and S_{3}alike objects of third kind= (S

_{1}+ 1)(S_{2}+ 1)(S_{3}+ 1) - 1
The above formula can be generalized as follows.

Number of ways in which one or more objects can be selected out of S

= (S

_{1}alike objects of one kind, S_{2}alike objects of second kind , S_{3}alike objects of third kind and so on ... S_{n}alike objects of n^{th}kind= (S

_{1}+ 1) (S_{2}+ 1)(S_{3}+ 1)...(S_{n}+ 1) - 1
Number of ways in which one or more objects can be selected out of S

= (S

_{1}alike objects of one kind, S_{2}alike objects of second kind and rest p different objects= (S

_{1}+ 1)(S_{2}+ 1)2^{p}- 1
The above formula can be generalized as follows.

Number of ways in which one or more objects can be selected out of S

_{1}alike objects of one kind, S_{2}alike objects of second kind and so on ... S_{n}alike objects of n^{th}kind and rest p different objects_{ }= (S_{1}+ 1) (S_{2}+ 1) ... (S_{n}+ 1) 2^{p}- 1
## 0 comments:

Post a Comment