NOTE

M A T H E M A T I C S

PERMUTATIONS AND
COMBINATIONS
APPLICATIONS OF MULITNOMIAL THEOREM AND
MISCELLANEOUS PROBLEMS

What you already know What you will learn

• Combinations • Applications of multinomial theorem

• Derangements • Miscellaneous problems
• Distribution of things
• Finding the number of non-negative, positive
integral solutions of the equations involving
multiple variables

Find the number of non-negative integral solutions of a + b + c + d ≤ 20

Solution

Step 1:
Given, a + b + c + d ≤ 20 . . . . . . .(1)
Let us introduce a dummy variable e to make this inequality an equation.
As (1) is an inequality so to change it into an equation we need to add some value in L.H.S of the
inequality
Let 20 ≥ e ≥ 0 be a dummy variable such that a + b + c + d + e = 20. . . . . . .(2)

Step 2:
Now, number of non-negative integral solution of (1) = Number of non-negative integral
solution of (2)
We know, for a linear equation of type: x1 + x2 + x3 +. . .+ xr = n , number of non-negative integral
solutions is given as follows:
n+r-1
Cr - 1
For equation (2), n = 20, r = 5
Hence, number of non-negative integral solutions = n + r - 1Cr - 1 = 20 + 5 - 1C5 - 1 = 24C4

Concept Check 1

Find the number of integral solutions of x + y + z = 20, where x ≥ -4, y ≥ 1, z ≥ 0

© 2020, BYJU'S. All rights reserved

 02

Applications of Multinomial Theorem

In this theorem, we try to write all the possible outcomes in powers of a random variable x and then
calculate the coefficient of the required outcome.
Let us understand the application of the multinomial theorem by an example.
Example
Find the number of ways of distributing 10 identical apples among 3 children without any restriction.
Solution (By formula)
In the above example, there is no restriction on the number of apples.
So, we can solve it by the method of number of non-negative integral solutions that we already
know.
Let a, b, c be the number of apples distributed to three children.
Then from question, a + b + c = 10; a ≥ 0, b ≥ 0, c ≥ 0 . . .(1)
We know, for a linear equation of type: x1 + x2 + x3+. . . + xr = n, number of non-negative integral
solutions is given as follows:
n+r-1
Cr - 1
For equation (1), n = 10, r = 3
Hence, number of non-negative integral solution = n + r - 1Cr - 1 = 10 + 3 - 1C3 - 1 = 12C2 = 66
Now, let us say, we have a restriction on the upper limit of one variable that the third child should
not get more than 6 apples, i.e., 6 ≥ c ≥ 0
In such a case, we cannot apply the formula for the number of non-negative integral solutions.
And in such cases, we need application of multinomial theorems to solve such problems.
Now, let us try to solve the same given example by the application of a multinomial theorem for
understanding the process of it.
Solution (By application of multinomial theorem)
Let a, b, c be the number of apples distributed to three children.
Then from question, a + b + c = 10; (a ≥ 0, b ≥ 0, c ≥ 0) . . .(1)
All the possible outcomes of ‘a’ in powers of a random variable x can be written as follows:
x0 + x1 + x2+ . . ., where 0, 1, 2, 3, ... are the possible outcomes of ‘a’ and x is a random variable.
All the possible outcomes of ‘b’ in powers of a random variable x can be written as follows:
x0 + x1 + x2 + . . ., where 0, 1, 2, 3, ... are the possible outcomes of ‘b’ and x is a random variable.
All the possible outcomes of ‘c’ in powers of a random variable x can be written as follows:
x0 + x1 + x2+ . . ., where 0, 1, 2, 3, ... are the possible outcomes of ‘c’ and x is a random variable.

Possible outcomes
a b c
(x0 + x1 + x2+ . . .) (x0 + x1 + x2+ . . .) (x0 + x1 + x2+ . . .)

As exponents represent the possible outcomes,

So, number of solutions = Coefficient of x10 in
(x0 + x1 + x2+ . . .)(x0 + x1 + x2+ . . .)(x0 + x1 + x2+ . . .) . . .(2)
All the above three terms are the same and infinite G.P.

© 2020, BYJU'S. All rights reserved

 03

a
We know, sum of infinite G.P. = , where a is the first term of G.P. and r ( r < 1 ) is the common
1-r
difference.
1
So, x0 + x1 + x2 + . . . =
1-x
1 1 1
⇒ (x0 + x1 + x2+ . . .)(x0 + x1 + x2+ . . .)(x0 + x1 + x2+ . . .) =
1-x 1-x 1-x
= (1-x)-1(1-x)-1(1-x)-1 = (1-x)-3
By putting this value in equation (2), we get,
Number of solution = Coefficient of x10 in (1-x)-3
By using the result of binomial theorem, we get, coefficient of xr in (1-x)-m is m+r-1Cr
So, number of solutions = Coefficient of x10 in (1-x)-3
= m+r-1Cr= 10+3-1C10= 12C10 = 66
Observations
a + b + c = 10
(x0 + x1 +. . . + x 10+ . . .)(x0 + x1 +. . . + x 10+ . . .)(x0 + x1 +. . . + x 10+ . . .)

Here, in the question, it was given that a + b + c = 10 and there was no restriction on the variable.
Let us consider the case of dice. In dice, we cannot get a number greater than 6. So, here, we have
restrictions on the variables. Such problems can also be solved by using algebraic expression or
application of multinomial theorems.

Result

Consider the equation,

x1 + x2 + x3+. . .+ xr = n, where ai ≤ xi ≤ bi
For i = 1, 2, 3,. . . r,
The number of integral solutions of the above equation = The coefficient of xn in the product
(xa + xa +1 + . . . +xb )(xa +xa +1+ . . . +xb ) . . .(xa +xa +1+ . . . +xb )
1 1 1 2 2 2 r r r

Find the number of non-negative integral solutions of x1 + x2 + x3 + 4x4 = 20

Solution

Step 1:
Given, x1 + x2 + x3 + 4x4= 20 and we have to find the number of non-negative integral solutions.
Here, All the possible outcomes of ‘x1’ in powers of a random variable x can be written as follows:
(x0 + x1 + x2+ . . .), where, 0, 1, 2, . . . are the possible outcomes of ‘x1’ and x is a random variable.
All the possible outcomes of ‘x2’ in powers of a random variable x can be written as follows:
(x0 + x1 + x2+ . . .), where, 0, 1, 2, . . . are the possible outcomes of ‘x2’ and x is a random variable.
All the possible outcomes of ‘x3’ in powers of a random variable x can be written as follows:
(x0 + x1 + x2+ . . .), where, 0, 1, 2, . . . are the possible outcomes of ‘x3’ and x is a random variable.
let say we are putting x4 = 0, then fourth term will become zero hence possible
outcome of fourth term i.e., 4x4 for this case is 0.

© 2020, BYJU'S. All rights reserved

 04

Similarly for x4 = 1, the possible outcome of the fourth term is 4, and so on.
All the possible outcomes of ‘4x4’ in powers of a random variable x can be written as follows:
(x0 + x4 + x8 + . . .), where, 0, 4, 8, . . . are the possible outcomes of ‘4x4’ and x is a random variable.
Number of non-negative integral solutions = The coefficient of x20 in the product
(x0 + x1 + x2+ . . .)(x0 + x1 + x2+ . . .)(x0 + x1 + x2+ . . .)(x0 + x4 + x8 + . . .)
= The coefficient of x20 in the product (x0 + x1 +x2 +...)3 (x0 +x4 +x8 +...) . . . .(1)
Both the terms are infinite G.P.
a
We know, sum of infinite G.P. = , where a is the first term of G.P. and r ( r < 1) is the common
1-r
difference.
1
So, (x0 + x1 + x2+ . . .) =
1-x
1
And , (x + x + x + . . .) =
0 4 8
1 - x4
Putting these values in equation (1) 1 1
Number of non-negative integral solutions = The coefficient of x20 in the product (1 - x)3 × 1 - x4
= Coefficient of x20 in (1-x)-3 × (1-x4)-1

Step 2:
Now, using,
(1 - x)-m = 1 + mC1x + (m+1)C2x2+ (m+2)C3x3+...
We get,
= Coefficient of x20 in (1+ 3C1x + 4C2x2 +... + r+2Crxr+...)(1 + x4 + x8 + x12 + x16+ x20+...)

Step 3:
Now, we get the coefficient of x20 by multiplying the following terms:
1 by x20, 6C4x4 by x16, 10C8x8 by x12, 14C12x12 by x8, 18C16x16 by x4, and 22
C20x20 by 1
And we get,
Coefficient of x20 = 1+ 6C4+ 10C8+ 14C12+ 18C16+ 22C20 = 536

Concept Check 2 JEE ADVANCED 2020

An engineer is required to visit a factory for exactly 4 days during the first 15 days of every
month and it is mandatory that no two visits take place on consecutive days. What is the number
of all possible ways in which such visits to the factory can be made by the engineer during 1-15
June 2021?

Concept Check 3 JEE MAIN 2020

What is the total number of 3-digit numbers whose sum of digits is 10?

© 2020, BYJU'S. All rights reserved

 05

Miscellaneous Problems

Find the sum of all four-digit numbers formed by using the digits 2, 3, 4, 5 without
repetition.

Solution
Step 1: Step 2:
Given, ∴ Sum of all digits in units place
Digits 2, 3, 4, 5 = 3! × (2 + 3 + 4 + 5)
Therefore, number of 4-digit number Now, numbers having 2 in tens place
= 4! = 24 __ __ 2 __
Now, numbers having 2 in units place And rest 3 digits can be arranged in 3! ways in
__ __ __ 2 the remaining three places.
Rest three places can be filled by 3! ways Similarly, numbers having 3, 4, 5 in tens place
Here, units place digit 2 will be repeated by 3!. __ __ 3 __ = __ __ 4 __ = __ __ 5 __ = 3!
So, sum will be = 3! × 2 Now, sum of all digits in tens place
Similarly, numbers having 3, 4, 5 in units places = 3! × (2+3+4+5) × 10
__ __ __ 3 = __ __ __ 4 = __ __ __ 5 [We have multiplied it by 10 because it is the
= 3! sum of the numbers of tens places]

Step 3:
Sum of all digits = Sum of all digits for units, tens, hundreds, and thousands places
Hence, the sum of all 4-digit number
= 3! (2 + 3 + 4 + 5 )( 1 + 10 + 100 + 1,000)
= 93,324
Result
If d1, d2 ,..., dn are the given non-zero digits, then the sum of all n-digit numbers (without repetition)
is equal to the following:
(n-1)! × (d1 + d2+ d3+...+dn)(100 + 101 + 102 +...+10n-1)

Summary Sheet

Key Takeaways

• Consider the following equation:

x1 + x2 + x3 + . . .+xr = n, where ai ≤ xi ≤ bi
For i = 1, 2, 3,. . . r,
The number of integral solutions of the above equation = The coefficient of xn in the product
(xa + xa + 1 + . . . + xb )(xa + xa +1+ . . . +xb ) . . .(xa + xa +1 + . . . + xb )
1 1 1 2 2 2 r r r

• If d1, d2, ..., dn are the given non-zero digits, then the sum of all n-digit numbers (without repetition)
is equal to the following:
(n-1)! × (d1 + d2 + d3 +... + dn) × (100 + 101 + 102+...+10n-1)

© 2020, BYJU'S. All rights reserved

 06

Mind Map

P and C

Applications of
multinomial theorem Combined problems

Self-Assessment

1. Find the number of non-negative integral solutions of x + y + z + w ≤ 20

2. In how many ways can the sum of upper faces of four distinct dices be six?

Answers

Concept Check 1

Step 1: Step 2:
Given, Now, adding 4 and subtracting 1 on both sides of
x + y + z = 20 . . . . . . (1) the equation (1), we get,

Also, x ≥ -4, y ≥ 1, z ≥ 0 x + y + z + 4 - 1 = 20 + 4 - 1

As all the variables are not non-negative ⇒ (x + 4) + (y - 1) + z = 23

variables, first make them non-negative ⇒ x1 + y1+ z = 23 . . . . . . (2)
variables. As (x + 4) = x1 and (y - 1) = y1.
Given, x ≥ -4 ⇒ x + 4 ≥ 0
Step 3:
Let us name x + 4 as a new variable x1.
⇒ x1 ≥ 0 For equation (2), n = 23, r = 3
Hence, the variable x1 is a non-negative Hence, the number of non-negative integral
variable. solutions are as follows:
Similarly, y ≥ 1 ⇒ y - 1 ≥ 0 = 23+3-1C3-1 = 25C2 = 25 × 12 = 300
Let us name y - 1 as a new variable y1.
⇒ y1 ≥ 0
Hence, the variable y1 is a non-negative
variable.
z≥0
So, z is already a non-negative variable.

© 2020, BYJU'S. All rights reserved

 07

Concept Check 2

Step 1: Step 2:
Given, 15 days → Total 4 days factory visit in Now, equation (i) becomes,
such a way that no two visits take place on a + (b - 1) + (c - 1) + (d - 1) + e = 11 - 3
consecutive days.
[In order to not change the equation, we
Let V1, V2, V3, V4 be the four visiting days. subtracted 3 from RHS]
__ V1 __ V2 __ V3 __ V4 __ Now, let (b - 1) = x, (c - 1) = y, and
Where, a, b, c, d, e be the remaining days be- (d - 1) = t
tween two consecutive visits as given, We get,
respectively. a+x+y+t+e=8 ----(ii)
So, a + b + c + d + e = 11 ----(i) Where all the variables are ≥ 0.
Where, a ≥ 0, b ≥ 1, c ≥ 1, d ≥ 1, e ≥ 0 So, solution of equation (ii) is the number of
Or a ≥ 0, b - 1 ≥ 0, c - 1 ≥ 0, d - 1 ≥ 0, e ≥ 0 non-negative integral solutions, i.e., n + r - 1Cr - 1
Now, we get, 8 + 5 - 1C5 - 1 = 12C4 = 495

Concept Check 3
Step 1: Step 2:
We have to find the total number of 3-digit x1 + y +z = 9 ----(ii)
numbers whose sum is 10. Where all variables are ≥ 0.
Let xyz be a 3-digit number such that So, solution of equation (ii) is the number of
x + y + z = 10 ---(i) non-negative integral solutions, i.e.,
(where, x ≥ 1, y ≥ 0, z ≥ 0)
n+r-1
Cr - 1

Or (x - 1) ≥ 0, y ≥ 0, z ≥ 0) Therefore, 9 + 3 - 1C3 - 1 = 11C2 = 55

⇒ (x - 1) + y + z = 10 - 1 However, when x1 becomes 9, then x = 10, i.e.,

not a digit.
[In order to not change the equation, we
subtracted 1 from RHS also] Therefore, final number of ways = 55 - 1 = 54

Self-Assessment 1

Given, x + y + z + w ≤ 20
Let x + y + z + w + t = 20, where t ≥ 0
Now, we get the non-negative integral solutions by n+r-1
Cr - 1.
I.e., 20 + 5 - 1C5 - 1 = 24C4

Self-Assessment 2

Step 1:
Given, here the number of required ways will be equal to the number of solutions of
x1 + x2 + x3 + x4 = 6, i.e., 1 ≤ x1, x2, x3, x4 ≤ 6

© 2020, BYJU'S. All rights reserved

 08

All the possible outcomes of ‘x1’ in powers of a random variable x can be written as follows:
x1 + x2 + x3+ . . ., where, 1, 2,3, . . . are the possible outcomes of ‘x1’ and x is a random variable.
All the possible outcomes of ‘x2’ in powers of a random variable x can be written as follows:
x1 + x2 + x3 + . . . where, 1, 2, 3, . . . are the possible outcomes of ‘x2’ and x is a random variable.
All the possible outcomes of ‘x3’ in powers of a random variable x can be written as follows:
x1 + x2 + x3 + . . .,where, 1, 2,3 . . . are the possible outcomes of ‘x3’ and x is a random variable.
All the possible outcomes of ‘x4’ in powers of a random variable x can be written as follows:
x1 + x2 + x3 + . . .,where, 1, 2,3 . . . are the possible outcomes of ‘x4’ and x is a random variable.
Since, the upper limit is 6, which is equal to the sum required, so the upper limit can be taken
as infinite.

Step 2:
So, the number of solutions is equal to the coefficient of t6 in the product (t + t2 + t3 +...)4
= Coefficient of t6 in t4 (1 + t + t2 + t3 +..)4 = Coefficient of t2 in (1 - t)-4
= 2 + 4 - 1C4 - 1 = 5C3 = 10

© 2020, BYJU'S. All rights reserved