Permutation and Combination — Advanced Concepts, Formulas and Tricks

                                   Number of Integral Solution
The formal expression of binomial theorem is as follows:

⦿ (1 + x)ⁿ = 1 + ⁿC₁ x +ⁿC₂ x² + ⁿC₃ x³ + ⁿC₄ x⁴ + ……….
now understand multinomial theorem:-

∴ Coefficient of xʳ in (1-x)⁻ⁿ
= ⁿ ⁺ ʳ ⁻¹Cᵣ
& Since we know that ⁿCᵣ = ⁿCₙ₋ᵣ
∴ ⁿ ⁺ ʳ ⁻¹Cᵣ = ⁿ ⁺ ʳ ⁻¹C₍ₙ ₊ ᵣ ₋ ₁₎ – ᵣ
                   = ⁿ ⁺ ʳ ⁻¹Cₙ₋₁

Example:-

⦿ Coefficient of x¹⁰ in (1-x)⁻ⁿ = ¹⁰⁺⁽ⁿ⁻¹⁾Cₙ₋₁
⦿ Coefficient of x¹⁵ (1-x)⁻ⁿ = ¹⁵⁺ⁿ⁻¹Cₙ₋₁
⦿ Coefficient  of x⁸ in (1-x)⁻ⁿ = ⁸⁺⁽⁵⁻¹⁾C₅₋₁ = ¹²C₄

(Q). Find the coefficient of x⁶ in ((1+x)¹⁰ + 10x³ + 6x⁶)

⦿ n identical objects can be distributed among r person in 

So distribution of n identical object among r person & number of integral solution of equation x₁ + x₂ + x₃ + x₄ + x₅ + ……….. + xᵣ = n 
         where x₁, x₂, x₃, x₄, x₅,……….xᵣ ≥ 0
have the same solution which is 

Using Multinomial theorem to find the number of non-negative integral solution of equation
 x₁ + x₂ + x₃ + x₄ + x₅ + ……….. + xᵣ = n 

(Q). Find the number of non-negative integral solution of x + y + z = 20
Solution-

x + y + z = 20               x≥0
                                        y≥0
                                        z≥0

= ²⁰⁺²C₂
= ²²C₂ Answer

method(2):S= coefficient of p²⁰ in (p⁰ + p¹ + p² + …….. p²⁰)³
= coefficient of p²⁰ in (1 + p¹ + p² + …….. p²⁰ + p²¹ + p²² + …….. ∞)³
=  coefficient of p²⁰ in  \({\left( {\frac{1}{{1 – p}}} \right)^3}\)
= coefficient of p²⁰ in (1-p)⁻³
= ²⁰ ⁺ ⁽³⁻¹⁾C₃₋₁
=²²C₂ Answer

(Q). Find number of positive integral solution of x + y + z = 20
Solution:-

x + y + z = 20                  x≥ 1
                                           y≥ 1
                                           z≥1

Method (2):-

Coefficient of p²⁰ in (p¹ + p² + p³ …….. p²⁰)³
= Coefficient of p²⁰ in (p + p² + p³ + …….. p²⁰+ ……..∞)³
= Coefficient of p²⁰ in  \({\left( {\frac{p}{{1 – p}}} \right)^3}\)
= Coefficient of p²⁰ in p³(1-p)⁻³
= Coefficient of p¹⁷ in (1-p)⁻³
= ¹⁷⁺⁽³⁻¹⁾C₍₃₋₁₎
= ¹⁹C₂ Answer

(Q). Find the number of  non-negative integral solution of a + b + c + 4d = 20
Solution:-

a + b + c + 4d = 20                      20≥a≥0
                                                        20≥b≥0
                                                        20≥b≥0
                                                        5≥b≥0
Method(1):

a + b + c + 4d = 20 
⦿ d = 0 ⟹ a + b + c = 20 ⟹ ²²C₂
⦿ d = 1 ⟹ a + b + c = 16 ⟹ ¹⁸C₂
⦿ d = 2 ⟹ a + b + c = 12 ⟹ ¹⁴C₂
⦿ d = 3 ⟹ a + b + c = 8 ⟹ ¹⁰C₂
⦿ d = 4 ⟹ a + b + c = 4 ⟹ ⁶C₂
⦿ d = 5 ⟹ a + b + c = 0 ⟹ ²C₂

Hence Answer = ²²C₂ + ¹⁸C₂ + ¹⁴C₂

+ ¹⁰C₂ + ⁶C₂ + ²C₂
= 231 + 153 + 91 + 45 + 15 + 1
=536 Answer

Method(2):

a + b + c + 4d = 20
⟹ a + b + c = 20 – 4d
Let d be a contant k where 5≥k≥0
∴ a + b + c = 20 – 4k             5≥k≥0           

= ²²C₂ + ¹⁸C₂ +¹⁴C₂ + ¹⁰C₂ + ⁶C₂ + ²C₂
= 536 Answer

Methode(3): Using multinomial theorem:-

Coefficient of p²⁰ in (p⁰ + p¹ + p² + p³ …….. + p²⁰)³(p⁰ + p⁴ + p⁸ + p¹² + p¹⁶ + p²⁰)
= Coefficient of p²⁰ in (1 + p + p² + p³ …….. + p²⁰ + ……….∞)³ (p⁰ + p⁴ + p⁸ + p¹² + p¹⁶ + p²⁰)
=  Coefficient of p²⁰ in  \({\left( {\frac{1}{{1 – p}}} \right)^3}\) (p⁰ + p⁴ + p⁸ + p¹² + p¹⁶ + p²⁰)
=  Coefficient of p²⁰ in (1-p)⁻³ (p⁰ + p⁴ + p⁸ + p¹² + p¹⁶ + p²⁰)
= ²²C₂ + ¹⁸C₂ + ¹⁴C₂ + ¹⁰C₂ + ⁶C₂ + 1
= 536 Answer

(Q). Find number of non-negative integral solution of inequality
x₁ + x₂ + x₃ + x₄ + x₅ ≤ 20
Solution:- 

x₁ + x₂ + x₃ + x₄ + x₅ + k = 20         where 20≥k≥0
when k=0 then x₁ + x₂ + x₃ + x₄ + x₅ = 20
when k=1 then x₁ + x₂ + x₃ + x₄ + x₅ = 19
when k=2 then x₁ + x₂ + x₃ + x₄ + x₅ =18
           ⋮                                                            ⋮
           ⋮                                                            ⋮
           ⋮                                                            ⋮
           ⋮                                                            ⋮ 
when  k=20 then x₁ + x₂ + x₃ + x₄ + x₅ = 0

So on depending value of k (20≥k≥0)
value of expression automatically becomes
x₁ + x₂ + x₃ + x₄ + x₅ ≤ 20
                   ⇓

Hence number of intergral solution = ⁵⁺²⁰C₅ = ²⁵C₅ Answer

(Q). Find Number of integral solution off equation
x₁ + x₂ + x₃ + x₄ = 20               
                                             ;where x₁≥2
                                                            x₂≥4
                                                            x₃≥0
                                                            x₄≥6
Solution:-

Method(1):

Method(2): Using Multinomial theorem:-

Coefficient of p²⁰ in (p² + p³ + p⁴ + ……… + p²⁰)(p⁴ + p⁵ + p⁶ + ……… + p²⁰)(p⁰ + p¹ + p² + p³ + …….. + p²⁰)(p⁶ + p⁷ + p⁸ + ….. + p²⁰)
= Coefficient of p²⁰ in (p² + p³ + p⁴ + …….. + ∞)(p⁴ + p⁵ + p⁶ + ……… ∞)(p⁰ + p¹ + p² + p³ + …….. ∞)(p⁶ + p⁷ + p⁸ + ….. ∞)
= Coefficient of p²⁰ in  \(\left( {\frac{{{p^2}}}{{1 – p}}} \right)\left( {\frac{{{p^4}}}{{1 – p}}} \right)\left( {\frac{1}{{1 – p}}} \right)\left( {\frac{{{p^6}}}{{1 – p}}} \right)\)
=Coefficient of p²⁰ in p¹²(1-p)⁻⁴
= Coefficient of p⁸ in (1-p)⁻⁴
=⁸⁺³C₃
= ¹¹C₃ Answer 

(Q). Find number of non-negative integral solution of 
a + b + c + d + e + f = 30
                     a + b + c = 17
Solution:-

(Q). There are two sections A & B and there are 16 intermediate stations between A & B. A train is going from station A toward station B. In how many ways train can stop at 4 stations if no two stations should be consecutive. Train can take stoppage at any of these A, B & 16 intermediate stations.
Solution:-

(Q). There are 18 chairs. These chairs are to be occupied by 4 students. Find the number of possible arrangement if:-
(i) No two students sit side-by-side.
(ii) There should be atleast 3 empty chairs between any two students.
Solution:-

(i) 

(Q) There are unlimited number of balls of colours Red, Green, Blue & White. They are all alike except for colour. In how many ways 20 balls can be selected?
Solution:-

(Q). Let a student can score maximum 100 marks in physics, chemistry & math each. Then find the number of ways in which he can score a total of 170 marks while getting atleast 50 marks in each subjects. Only integral marks are allowed.
Solution:-

P    +    C    +    M = 170
                                                  100≥P≥50
                                                  100≥C≥50
                                                  100≥M≥50
Using Multinomial theorem

(Q). In the above question if the total numbers (marks) required are 240.
Solution:-
Coefficient of x²⁴⁰ in  \({\left[ {\frac{{{x^{50}}(1 – {x^{51}})}}{{(1 – x)}}} \right]^3}\)
= Coefficient of x²⁴⁰ in x¹⁵⁰(1-x⁵¹)³(1-x)⁻³

= Coefficient of x⁹⁰ in (1-x⁵¹)³(1-x)⁻³
= Coefficient of x⁹⁰ in (1 – 3x⁵¹ + 3x¹⁰² – x¹⁵³)(1-x)⁻³
                                      ✅  ✅
= ⁹⁹C₂ – 3.⁴¹C₂ Answer

(Q). In how many ways a batman can score 20 runs out of six balls if he can score 0, 1, 2, 3, 4, 5 or 6 runs at a particular ball?
Solution:-

x₁ + x₂ + x₃ + x₄ + x₅ + x₆ = 20
                                                                6≥x₁, x₂, x₃, x₄, x₅, x₆≥0
∴ Coefficient of p²⁰ in (p⁰ + p¹ + p² + p³ + p⁴ + p⁵ + p⁶)⁶
= Coefficient of p²⁰ in  \({\left[ {\frac{{(1 – {p^7})}}{{(1 – p)}}} \right]^6}\)
= Coefficient of p²⁰ in (1 – p⁷)⁶(1 – p)⁻⁶

= ²⁵C₅ – ⁶C₁×¹⁸C₅ + ⁶C₂×¹¹C₅ Answer

(Q). a+b+c+d+e+f = 20; find the number of integral solution of this equation
If 10≥a≥5
     b, c, d, e≥0
Solution:- 

Method (2):

Coefficient of  p²⁰ in (p⁵ + p⁶ + p⁷ + p⁸)( p⁷ + p⁸ + p⁹ + p10)(p⁰ + p¹ + p² + p³ + ……. + p²⁰)⁴
= Coefficient of  p²⁰ in p⁵(1 + p + p² + p³).p⁷.(1 + p + p² + p³)(1 + p + p² + p³+ …….. p²⁰)⁴
= Coefficient of  p²⁰ in p¹²(1 + p + p² + p³)²((1 + p + p² + p³ + ……… + p²⁰)⁴
= Coefficient of p⁸ in  \({\left[ {\frac{{1 – {p^4}}}{{1 – p}}} \right]^2}{\left[ {\frac{1}{{1 – p}}} \right]^4}\)
= Coefficient of p⁸ in (1-p⁴)²(1-p)⁻⁶
= Coefficient of p⁸ in (1-2p⁴+p⁸)(1-p)⁻⁶
= ¹³C₅ – 2×⁹C₅ + 1
= 1036 Answer

(Q). Find number of integral solution of equation
x₁ + x₂ + x₃ + x₄ + x₅ = 48
if x₁, x₂, x₃, x₄, x₅ ← evennumbers; ≥0
Solution:-

2n₁ + 2n₂ + 2n₃ + 2n₄ + 2n₅ = 48
⟹ n₁   +   n₂   +   n₃   +   n₄   +   n₅ = 24
      ≥0       ≥0         ≥0      ≥0         ≥0
= ²⁸C₄ Answer

                                        Special cases of Integral Solution

case (1):            a + b + c = n                condition a>b>c≥0

Number of possible intergral solutions
=  \(\left[ {\frac{{{n^2} + 6}}{{12}}} \right]\)    where [x] → Greatest integer function

case (2):         a + b + c = n                 condition a≥b≥c≥0
Number of possible integral solutions
=  \(\left[ {\frac{{{n^2} + 6}}{{12}}} \right] + \left[ {\frac{n}{2}} \right] + 1\)    where [x] → Greatest integer function

case (3):        |x| + |y| = n
Number of integral solution = 4n

case (4):         |x| + |y| < n
Number of integral solution ⟹ 1 + 4(1 + 2 + 3 + …… + (n-1))

case (5):         |x| + |y| ≤ n
Number of integral solution ⟹ 1 + 4(1 + 2 + 3 + 4 + …….. + n)

case (6):        |x| + |y| + |z| = n
Number of integral solution ⟹ 4n² + 2

case (7):        |x| + |y| + |z| + |w| = n
 Number of integral solution ⟹ \(\boldsymbol{\frac{{8n}}{3}.\left( {{n^2} + 2} \right)}\)

case (8):        x * y = n

If n is NOT a perfect square then number of positive integral solutions =  \(\frac{{\left( {number\;of\;factors\;of\;n} \right)}}{2}\)
& number of total integral solutions = 2*(number of positive integral solutions)
= 2*\(\frac{{\left( {number\;of\;factors\;of\;n} \right)}}{2}\)

If n is a perfect suqare
then number of positive integral solutions =  \(\frac{{\left( {number\;of\;factors\;of\;n \;+\; 1} \right)}}{2}\)

total integral soluions = 2*\(\frac{{\left( {number\;of\;factors\;of\;n \;+\; 1} \right)}}{2}\)

case (9):        x*y*z = n

Let n =  \({a^{{p_1}}}*{b^{{p_2}}}*{c^{{p_3}}}*…………..\)
then number of ORDERED POSITIVE integral solutions =

& number of ORDERED integral solutions = 4 * number of ordered positive integral solutions

case (10):        ax + by = n

⟹ First, reduce the given equation in lowest reducible form.
⟹ After reducing, if coefficients of x and y still have a factor in common, the equation will have no solutions.
⟹ if x & y are co-prime in lowest reducible form, find one solution of x. Then the other solutions can be listed as an arithmetic progression with common difference as the co-efficient of y which can be easily counted.
⟹ if equation is of the form ax+by=n then increase in x as coefficient of y will cause decrease in coefficint of y as a step of coefficient of x.
⟹ if equation is of the form ax-by=n then increase in x as a step of coefficient of y will cause an increase in coefficient of y as a step of coefficient of x.

⟹ Shortcut:→ if for ax+by=n either of a or b can divide n, then number of non negative integral solutions =  \(\left[ {\frac{n}{{L.C.M.(a,b)}}} \right] + 1\)

Let us understand this concept by example:-
Example: Find positive integral solution of 2x+3y = 30
Solution:- 

x = 0 ⟶ y = 10 ❌

x = 1 ⟶ y = \(\frac{{28}}{3}\) ❌

x = 2 ⟶ y = \(\frac{{26}}{3}\) ❌

x = 3 ⟶ y = \(\frac{{24}}{3}\) = 8 ✅

x = 6 ⟶ y = 6

x= 9 ⟶ y = 4

x = 12 ⟶ y = 2

x = 15 ⟶ y = 0 ❌ ⟶ not positive

So there are total 4 positive integral solutions.
& there are total 6 non-negative integral solutions of above equation as case( x=15, y=0) & (x=0, y=10) will also be counted.

Example:- Find number of positive & non-negative integral solution of equation 2x + 3y = 57
Solution:-

x = 0 ⟶ y = \(\frac{{57}}{3}\) = 19 

x = 1 ⟶ y = \(\frac{{55}}{3}\) ❌ 

x = 2 ⟶ y = \(\frac{{53}}{3}\)  ❌

x = 3 ⟶ y = \(\frac{{51}}{3}\) = 17

x = 4 ⟶ y = \(\frac{{49}}{3}\) ❌

x = 5 ⟶ y = \(\frac{{47}}{3}\) ❌

x = 6 ⟶ y = \(\frac{{45}}{3}\) = 15

x = 9 ⟶ y = 13

x = 12 ⟶ y = 11

x = 15 ⟶ y = 9

x = 18 ⟶ y = 7

x = 21 ⟶ y = 5

x = 24 ⟶ y = 3

x = 27 ⟶ y = 1

x = 30 ⟶ y = -1 ❌ 

Hence total number of non-negative integral solution = 10
& total number of positive integral solution = 9

Shortcut Since 57 is divisible by 3
Hence number of non-negative integral solution
=  \(\left[ {\frac{{57}}{{LCM(2,3)}}} \right] + 1\)

=  \(\left[ {\frac{{57}}{6}} \right] + 1\)

= 9 + 1

= 10 answer

case (11):        
\(\frac{a}{x} \pm \frac{b}{y} = \frac{1}{n}\)

\(\frac{a}{x} + \frac{b}{y} = \frac{1}{n}\)

F = factors of (a*b*n²)
Total integral solution = 2F – 1
Total positive integral solution = F
Total negative integral solution = 0

\(\frac{a}{x} – \frac{b}{y} = \frac{1}{n}\)

F = number of factors of (a*b*n²)
Total integral solution = 2F – 1
Total positive integral solution = \(\frac{{(F – 1)}}{2}\)

Total negative integral solution = \(\frac{{(F – 1)}}{2}\)

Example:- Find total integral & positive solution of equation \(\boldsymbol{\frac{{16}}{x} + \frac{5}{y} = \frac{1}{3}}\)
Solution:-

F = number of factors of (16×5×3²)
= number of factors of (2⁴×3²×5¹)

F = 5×3×2
= 30
∴ total integral solution = 2F – 1 = 60 – 1 = 59
& total positive integral solution = F = 30 Answer

Example:- Find total integral, positive & negative solution of equation  \(\boldsymbol{\frac{4}{x} – \frac{1}{y} = \frac{1}{5}}\)
Solution:-

F = number of factors of (4 * 1 * 5²)
= number of factors of (2² * 52)
= 3×3 = 9

∴ total integral solution = 2F – 1 = 18 – 1 = 17
total positive integral solution = \(\frac{{(F – 1)}}{2} \;=\; \frac{{(9 – 1)}}{2}\; = 4\)

total negative integral solution = \(\frac{{(F – 1)}}{2}\) =  \(\boldsymbol{\frac{{(9 – 1)}}{2}}\) = 4 Answer

                                            Application of Multinomial in Permutation with Repetition:-

⦿ Number of selection/combination of r things out of n things of which p are alike of one kind & q are alike of second kind and remaining (n-p-q) things are all different is given by
⟹ coefficient of xʳ in (1+x+x²+……..+xᵖ)(1+x+x²+……..+xᑫ){(1+x)(1+x)……… till (n-p-q) times}

⦿ The number of permutation/arrangement of r things out of n things of which p are alike of one kind & q are alike of second kind and so on……….

Example:- Let there are
                                p, q ━ 5
                                r, s ━ 4
                                    t ━ 3
                          u, v, w ━ 1
then find the number of permutation/arrangement of 5 letter words selected from given letters
Solution:- 

Using Multinomial theorem:-

Method(2):       Listing all cases: