JEE Advanced
JEE Main
BITSAT
View complete IIT JEE section
NTSE
KVPY
Olympiads
CBSE
ISCE
UAE
Saudi Arabia
Qatar
Kuwait
Oman
Bahrain
View complete NRI section
Physics
Chemistry
Maths
Revision notes
View complete study material
Buy IIT JEE/AIPMT study material
Buy CBSE Grade 8/9/10 study material
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:
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.
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 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.
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_{1} + x_{2} +⋯+ x_{k})^{n}, where n is an integer.
Let us assume that x_{1}, x_{2}, ......, x_{m} are integers. Then number of solutions to the equation
x_{1} + x_{2} + ... + x_{m} = n ... (1)
subject to the conditions a_{1} < x_{1} < b_{1}, a_{2} < x_{2} < b_{2}, ..., a_{m} < x_{m} < b_{m} ... (2)
is equal to the coefficient of x^{n} 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^{n }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-1}C_{m-1} and number of positive integral solutions of (1) is given by ^{n-1}C_{m-1}.
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_{1} + x_{2} + x_{3} = 10
subject to conditions 0 < x_{1} < 6, 0 < x_{2} < 7, 0 < x_{3} < 8
Hence the required number of ways
= coefficient of x^{10} in (1+x+x^{2}+...+x^{6})(1+x+x^{2}+...+x^{7})(1+x+x^{2}+...+x^{8})
= coefficient of x^{10} in (1-x^{7})(1-x^{8})(1-x^{9})(1-x)^{-3}
= coefficient of x^{10} in (1-x^{7}-x^{8}-x^{9})(1+^{3}C_{1}x + ^{4}C_{2}x^{2}+ ^{5}C_{3}x^{3}+...+^{12}C_{10}x^{10})
(ignoring powers higher than 10)
= ^{12}C_{2} - ^{5}C_{3} - ^{4}C_{2} - ^{3}C_{1}
= 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:
FUNDAMENTAL PRINCIPAL OF COUNTING Rule of Product...
Restricted Selection and Arrangement (a) The...
Permutations (Arrangements of Objects): The number...
Division and Distribution of Objects (With fixed...
Combinations Just like permutations, combination...
Useful Tips for Algebra SOME USEFUL TIPS (i)...
Permutations vs Combinations DIFFERENCE BETWEEN...
Circular Permutations The arrangements we have...
Download IIT JEE Solved Examples on Permutaions...