Derangements and Multinomial Theorem

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

 and it is denoted by D(n).

A question on derangement can be of the following kind:

Illustration:

Supposing 4 letters are placed in 4 different envelopes. In how many ways can be 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:

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

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). Using this we get the number of non negative integral solutions of (1) is given by ^n+m-1C_m-1 and number of positive integral solutions of (1) is given by ^n-1C_m-1.

Illustration:

In how many different ways three persons A, B, C having 6, 7 and 8 one rupee coins respectively can 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.

AskIITians is a group of IITians which provide you free online courses and a good professional advice for IIT JEE, AIEEE and other Engineering Examination preparation. You can visit askIITians.com to study topics pertaining to the IIT JEE and AIEEE syllabus for free.