Derangement Theorem and Multinomial Theorem

 

DERANGEMENTS

We first discuss the Derangement Theorem. The word derangement in simple words means any change in the existing order of things. Mathematically, derangement refers to the permutation consisting of elements of a set in which the elements don’t exist in their respective usual positions.

We consider a simple example to understand this concept. Suppose that a teacher has given assignments to 4 groups. Now, obviously a group cannot grade or assess his own assignment and so the teacher wants the groups to grade each other’s assignment. Our first concern is that in how many ways the teacher can provide the assignments to groups 1, 2, 3 and 4 the so that none of the group gets its own. In this case, the total possible number of permutations is 4! = 24. But, out of these there are only 9 derangements. The possible derangements are listed below:
 

2143

 

2341

2413

3142

3412

3421

 

4123

4312

4321

 

In the remaining permutations except the above list, at least one group will receive its own assignment.

Hence, derangements can basically be assumed to be the permutations in which the positions of the elements are altered. The only possible derangements of the set {1, 2, 3} are {2, 3, 1} and {3, 1, 2}. Another point to be noted is that derangements don’t contain cycles or permutations of length one.  

On similar lines of the problem discussed above, another question that is asked on derangement is of envelopes. If we are asked the total number of ways of placing n letters in n already addressed envelopes, wherein every letter is addressed to a different person in such a way that none of the letter is placed in the correctly addressed envelope. 

This is the most general question on the derangement principle that is often asked in the examinations. If ‘n’ particular items need to be arranged or organized in a row in such a manner that none of them acquires its usual or correct place is calculated using the formula:

This is the most important dearrangement formula. We now discuss the kind of questions one can expect from this topic in the exam:

Illustration:

Supposing 4 letters are placed in 4 different envelopes. In how many ways can they be taken out from their original envelopes and distributed among the 4 different envelopes so that no letter remains in its original envelope?

Solution: This is clearly a case of derangement. Using the formula for the number of derangements that are possible out of 4 letters in 4 envelopes, we get the number of ways as:

 4!(1 - 1 + 1/2! - 1/3! + 1/4!)

= 24(1 - 1 + 1/2 - 1/6 + 1/24)

= 9.

Multinomial Theorem

 

As the name suggests, multinomial theorem is the result that applies to multiple variables. It is basically a generalization of binomial theorem to more than two variables. The multinomial theorem provides a method of evaluating or computing an nth degree expression of the form (x1 + x2 +?+ xk)n, where n is an integer. 

 

Let us assume that x1, x2, ......, xm are integers. Then number of solutions to the equation

x1 + x2 + ... + xm = n                                                                    ... (1)

subject to the conditions a1 < x1 < b1, a2 < x2 < b2, ..., am < xm < bm  ... (2)

is equal to the coefficient of xn in

(xa1 + xa1 + 1 + ………+ xb1)(xa2 + xa2 + 1 + …… + xb2)… (xam + xam + 1 + …… + xbm)

...(3)

There is a simple logic behind this. The total possible number of ways in which the sum of n integers as expressed in equation (1) subject to certain conditions (2) totals n is exactly the same as the number of times xn occurs in equation (3). From this fact, it follows that the total number of non-negative integral solutions is given by the expression n+m-1Cm-1 and number of positive integral solutions of (1) is given by n-1Cm-1.

View the video for more on multinomial theorem

 

Illustration:

In how many different ways can three persons A, B, C having 6, 7 and 8 one rupee coins respectively donate Rs.10 collectively?

Solution:

The number of ways in which they can denote Rs.10 is the same as the number of solutions of the equation

x1 + x2 + x3 = 10

subject to conditions 0 < x1 < 6, 0 < x2 < 7, 0 < x3 < 8

Hence the required number of ways

= coefficient of x10 in (1+x+x2+...+x6)(1+x+x2+...+x7)(1+x+x2+...+x8)

= coefficient of x10 in (1-x7)(1-x8)(1-x9)(1-x)-3

= coefficient of x10 in (1-x7-x8-x9)(1+3C1x + 4C2x2+ 5C3x3+...+12C10x10)

                                            (ignoring powers higher than 10)

= 12C2 - 5C3 - 4C2 - 3C1

= 66 - 10 - 6 - 3 = 47.

Illustration:  mn squares of equal size are arranged to form a rectangle of dimension m by n, where m and n are natural numbers. Two squares will be called ‘neighbours’ if they have exactly one common side. A natural number is written in square such that the number written in any square is the arithmetic mean of the numbers written in its neighbouring squares. Show that this possible only if all the numbers used are equal.  

Solution: For any given square, there will be at most 2, 3, or 4 neighbours. Consider the square which has the largest number ‘d’ written on it. Let us assume that this square has 4 neighbours. Let p, q, r and s represent the numbers as the neighbours.

Hence, p + q + r + s = 4d

So, (d-p) + (d-q) + (d-r) + (d-s) = 0.

Sum of four positive numbers can be zero only if they are individually zero.

So, (d-p) = 0 = (d-q) = (d-r) = (d-s)

Hence, d = p = q = r = s.

Hence, all the numbers written are same.

 

askIITians is a group of IITians which provide you free online courses and a good professional advice for IIT JEE. You can visit askIITians to study topics pertaining to the IIT JEE. It also offers comprehensive study material which covers all the important topics like derangement formula, multinomial theorem in permutation and combination, formula of disarrangement etc. It is important to have a good hold on the topics in order to remain competitive in the JEE.

Related resources:

Name
Email Id
Mobile

Exam
Target Year

Related Resources
Basic Principles of Counting

FUNDAMENTAL PRINCIPAL OF COUNTING Rule of Product...

Restricted Selection and Arrangement

Restricted Selection and Arrangement (a) The...

Combinations

Combinations Just like permutations, combination...

Circular Permutations

Circular Permutations The arrangements we have...

Permutations

Permutations (Arrangements of Objects): The number...

Division and Distribution of Objects

Division and Distribution of Objects (With fixed...

Some Useful Tips

Useful Tips for Algebra SOME USEFUL TIPS (i)...

Permutations vs Combinations

Permutations vs Combinations DIFFERENCE BETWEEN...

Solved Examples Part-1

Download IIT JEE Solved Examples on Permutaions...