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:

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 (x₁ + x₂ +?+ x_k)ⁿ, where n is an integer. 

Let us assume that x₁, x₂, ......, x_m are 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

(x^a1 + x^{a1 + 1} + ………+ x^b1)(x^a2 + x^{a2 + 1} + …… + x^b2)… (x^am + x^{am + 1} + …… + x^bm)

...(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 xⁿ 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-1C_m-1 and number of positive integral solutions of (1) is given by ^n-1C_m-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

x₁ + x₂ + x₃ = 10

subject to conditions 0 < x₁ < 6, 0 < x₂ < 7, 0 < x₃ < 8

Hence the required number of ways

= coefficient of x¹⁰ in (1+x+x²+...+x⁶)(1+x+x²+...+x⁷)(1+x+x²+...+x⁸)

= coefficient of x¹⁰ in (1-x⁷)(1-x⁸)(1-x⁹)(1-x)^-3

= coefficient of x¹⁰ in (1-x⁷-x⁸-x⁹)(1+³C₁x + ⁴C₂x²+ ⁵C₃x³+...+¹²C₁₀x¹⁰)

                                            (ignoring powers higher than 10)

= ¹²C₂ - ⁵C₃ - ⁴C₂ - ³C₁

= 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

• Click here for the Complete Syllabus of IIT JEE Mathematics.

• Look into the Past Year Papers with Solutions to get a hint of the kinds of questions asked in the exam.

• You can get the knowledge of Important Books of Mathematics here. 

To read more, Buy study materials of Permutations and Combinations comprising study notes, revision notes, video lectures, previous year solved questions etc. Also browse for more study materials on Mathematics here.