Permutation & Combination Concepts by Gaurav Sharma - Part (2/2)

gaurav_sharma

Direct Method : Number of ways to distribute n identical things to r persons such that anyone can get any number of things is (n+r-1)C(r-1)

Example : Number of ways to distribute 15 ladoos among 5 persons is (15 + 5 – 1) C (5-1) = 19C4

If we have to distribute 15 ladoos among 5 persons such that all of them get atleast one ladoo, then
we have the equation: A + B + C + D + E = 15
Now, give one ladoo to each one of them so put A = a + 1, B = b + 1, C = c + 1, D = d + 1 and E = e + 1
We get, a + b + c + d + e = 10
This case is the same as the case where we have to distribute 500 ladoos among 26 persons such that each person can get any number of ladoos.
So, the number of solutions are (n + r – 1 ) C (r -1 )
N = 10 and r = 5, so (10 + 5 – 1) C ( 5 – 1) = 14C4

Direct method : Number of ways of distributing n things to r persons such that all get atleast one are: (n – 1)C(r – 1)

Positive integral solutions: Where the variables can be any natural number
Non negative integral solution: Where the variables can be any whole number
Integral solution: where the variable can be any integer

Find the number of positive integral solutions of a + b + c + d = 500?

We have to find the POSITIVE integral solutions of a + b + c + d = 500 which means we have to find the natural number of solutions for the equation.

This case is the same as the case where we have to distribute 500 ladoos among 4 persons such that each gets atleast 1 ladoo.

So the number of solutions are (n – 1) C (r – 1)

Here n = 500 and r = 4

So, (500 – 1) C (4 – 1) = 499 C 3

Find the non negative integral solutions of a + b + c + d + e .. + z = 500

We have to find non negative integral solutions for the equations a + b + c + d + .. + z = 500, which means we have to find the whole number solutions for the equation.

This case is the same as the case where we have to distribute 500 ladoos among 26 persons such that each person can get any number of ladoos.

So, the number of solutions are (n + r – 1 ) C (r -1 )

Here, n = 500 and r = 26

So, (500 + 26 – 1)C(26 – 1) = 525C25

Find the number of even natural solutions of a + b + c = 100

a + b + c = 100

So, put a = 2x, b = 2y and c = 2z

So 2x + 2y + 2z = 100

x + y + z = 50

We need to find even natural solutions of the equation x + y + z = 50

So the number of solutions = (50 – 1)C(3 – 1) = 49C2

Find the number of even non negative solutions of a + b + c + d + e = 200

Put a = 2x, b = 2y and c = 2z, d = 2w and e = 2v

2x + 2y + 2z + 2w + 2v = 100

x + y + z + w + v = 100

So the number of solutions = 100 + 5 – 1 C 5 – 1 = 104C4

Find the odd non negative integral solutions of a + b + c = 159

Put a = 2x + 1, b = 2y + 1 and c = 2z + 1

2x + 2y + 2z + 3 = 159

2 ( x + y + z) = 156

x + y + z = 78

Where x, y and z can take values which belong to whole numbers.

So the number of solutions: (n + r – 1)C(r – 1)

n = 78 and r = 3

So, ( 78 + 3 – 1)C(3-1) = 80C2

Find the number of odd solutions of a + b + c + d = 100

Put a = 2x + 1, b = 2y + 1, c = 2z + 1 and d = 2v + 1

2x + 2y + 2z + 2v + 4 = 100

2 (x + y + z + v) = 96

x + y + z + v = 48

Where x, y, z and v can take values which belong to whole numbers because when x = 0 we get a = 1, which is natural number. So the number of solutions: (n + r – 1)C(r – 1)

Where n = 48 and r =4

So (48 + 4 – 1)C(4 -1) = 51C3

Find the number of odd natural solutions of a + b + c + d + e = 200

Odd numbers added even number of times = Even number
Odd numbers added odd number of times = Odd number

So number of solutions for this equation is Zero.

Find the number of integral solutions of a + b + c + d = 50 such that each variable is greater than 5

Put a = A + 5, b = B + 5, c = C + 5 and d = D + 5

We get A + B + C + D = 50 – 5 x 4 = 30

So, now we have to find positive solutions for

A + B + C + D = 30

Which is (n – 1)C(r – 1), where n = 30 and r = 4

We get, (30 – 1)C(4 – 1) = 29C3

Find the number of positive solutions of a + b + c = 40 such that they all are distinct

We need to find Total Solutions – ( Number of solutions where any 2 of the variables are equal + Number of solutions where all 3 variables are equal)

Total positive solutions = (40 – 1)C(3 – 1) = 39C2

Number of solutions where any 2 of the variables are equal:

If a = b we get 2a + c = 40 Where a can take any value from 1 – 19. So, 19 cases.

If a = 20 then c = 0 which is not considered as a positive solution. Similarly when b = c ( 19 cases ) and c = a ( 19 cases )

And all three of them cannot be equal because 40 is not a multiple of 3

So distinct solutions = 39C2 – ( 19 x 3 ) = 684

Find the number of non-negative integral solutions of a + b + c = 28 such that they all are distinct

We need to find Total solutions – ( Number of solutions where any 2 of the variables are equal + Number of solutions where all three are equal )

Total positive solutions = (28 + 3 – 1) C (3 – 1) = 30C2

Number of the solutions where any 2 of the variables are equal:

If a = b, we get 2a + c = 28, where a can take any value from 0 – 14. so 15 cases.

If a = 14 then c = 0 which is considered a non-negative solution.

Similarly when b = c ( 15 cases) and c = a (15 cases)

And all three of them cannot be equal because 28 is not a multiple of 3

So distinct solutions = 30C2 – (15 x 3) = 390

How many terms are in the expansion of (a + b + c + d)^20

Sum of powers of each variable in the expansion of (a+b+c+d)^20 will be 20.

We have to find the number of ways in which 20 can be divided among 4 variables

So non negative solutions of a + b + c + d = 20

(n + r – 1)C(r – 1) where n = 20 and r = 4

S0 ( 20 + 4 – 1)C(4 – 1) = 23C3 = 1771

Number of terms in the expansion of (a + b + c + d)^20 = 1771

Find the number of ways of distributing 27 ladoos to Swetabh, Raman and Gaurav such that number of ladoos Swetabg gets are more than the number of ladoos Raman gets which in turn is more than the number of ladoos Gaurav gets

S + R + G = 27

S > R > G

So S, R and G are distinct

So total solutions – (cases where 2 are equal + cases where all 3 are equal)

Now total non-negative solutions: (27 + 3 – 1)C(3 – 1) = 29C2

Number of solutions where any 2 of the variables are equal: If S = R, we get 2S + R = 27 where S can take any value from 0 – 13. So, 14 cases but this includes cases where S = R = G, so 14 – 1 = 13 cases.

Similarly when R=G (13 cases) and when S = G (13 cases)

And 1 case where S = R = G = 9

So distinct solutions = 29C2 – ( 13 x 3 ) – 1 = 366

And for cases where S > R > G we divide 366 by 3! (Because we want only one of the 6 arrangements possible)

So answer: 366/6 = 61

In how many ways can 3 boys and 15 girls sit together in a row such that between any 2 boys at least 2 girls can sit?

Firstly, 3 boys can be arranged in 3! Ways
(X ) [B] (Y) [B] (Z) [B] (W)

After arranging the boys 4 gaps are created. Let in these gaps x, y, z and w girls sit.
Now y, z ≥ 2 and x, w ≥ 0
x + y + z + w = 15
Let y = y1 + 2 and z = z1 + 2 (where y1, z1 ≥ 0)
x + y1 + z1 + w = 11
Number of solutions = (11 + 4 – 1)C(4-1) = 14C3

Now the girls can be arranged in 15! Ways

So total ways are 14C3 * 3! * 15!

Between 2 junctions A and B there are 12 intermediate stations. The number of ways in which a train can be made to stop at 4 of these stations, so that no two halting stations are consecutive is

(A) [X1] (1) [X2] (2) [X3] (3) [X4] (4) [X5] (B )

Here x1 + x2 + x3 + x4 + x5 = 8 -- > (1)

x1, x2, x3, x4, x5 is the number of intermediate stations.

1, 2, 3, 4 are the stations.

Here x1 ≥ 0; x5 ≥ 0; x2, x3, x4 ≥ 1

The total number of ways is the number of solutions of the above equation.

Let v = x2 – 1, u = x3 – 1, w = x4 – 1

We get, x1 + v + u + w + x5 = 5 (from equation 1)

Where v, u, w ≥ 0

The number of solutions = (5 + 5 – 1)C(5-1) = 9C4

If n objects are arranged in a row, the number of ways of selecting r items such that no two items are consecutive is (n – r + 1) C r
Note : Coefficient of x^n in (1-x)^(-r) is (n + r – 1)C(r – 1)

In how many ways can a sum of 10 be obtained by three persons, each throwing a single dice once?

Method 1:
A + B + C = 10 where 1 ≤ A, B, C ≤ 6
Now let A = a + 1, B = b + 1 and C = c + 1 where 0 ≤ a, b, c ≤ 5
So a + 1 + b + 1 + c + 1 = 10
a + b + c = 7
Number of non-negative solutions for the equation = (7 + 3 – 1)C(3 – 1) = 9C2
Now this will include case when a > 5, so put a = 6 + a1
6 + a1 + b + c = 7
a1 + b + c = 1
Number of non-negative solutions for the equation = ( 1 + 3 – 1) C (3 – 1) = 3
Similarly for b and c also there will be 3 cases each
So total solutions = 9C2 – 9 = 36 – 9 = 27

Method 2 :
A + B + C = 10
Put A = 6 – a, B = 6 – b, C = 6 – c
We get 6 – a + 6 – b + 6 – c = 10
a + b + c = 8
Total 10C2 = 45
Subtract cases where a ≥ 6, put a = 6 + a1
a1 + b + c = 2
Total 6 cases
Similarly for b ≥ 6 and c ≥ 6, 6 cases each.
So total cases = 45 – ( 6 * 3 ) = 45 – 18 = 27

In how many ways can a sum of 15 be obtained by three persons, each throwing a single dice once?

Let A, B and C be the three persons.
Now A + B + C = 15
Also, A ≤ 6, B ≤ 6 and C ≤ 6
So, put A = 6 – a, B = 6 – b and C = 6 – c
6 – a + 6 – b + 6 – c = 15
a + b + c = 3
Hence number of non-negative solutions of a + b + c = 3 are
(3 + 3 – 1) C (3 – 1) = 5C2 = 10

In how many ways can a sum of 11 be obtained by three persons, each throwing a single dice once?

Let A, B and C are the three persons
Now, A + B + C = 11
Also, A ≤ 6, B ≤ 6 and C ≤ 6
So, put A = 6 – a, B = 6 – b and C = 6 – c
6 – a + 6 – b + 6 – c = 11
a + b + c = 7
Hence number of non-negative solutions of a + b + c = 7 are
(7 + 3 – 1) C (3 – 1) = 9C2 = 36

But if (a =0, b=1,c=6) then C = 6 – c = 0
Which is not possible and there are 9 such cases
So number of ways = 36 – 9 = 27

Find the number of ways in which a score of 21 can be made from a throw by 4 persons, each throwing a single dice.

We have A + B + C + D = 21
So, put A = 6 – a, B = 6 – b, C = 6 – c and D = 6 - d
6 – a + 6 – b + 6 – c + 6 - d = 21
a + b + c + d = 3
Hence number of non-negative solutions of a + b + c + d = 3 are
(3 + 4 – 1) C (4 – 1) = 6C3 = 20

Find the number of ways in which we can get a sum greater than 17 by throwing six distinct dice.

Let a, b, c, d, e and f be the numbers that appear on the six dice.
Here 1 ≤ a,b,c,d,e,f ≤ 6
Total number of solutions = 6^6
To find solutions for a + b + c + d + e + f > 17
Number of ways to get the sum less than or equal to 17 = 17C11 – 6 * 11C5
So number of ways to get the sum greater than 17 is 6^6 – (17C11 – 6 * 11C5)

Find the total number of triangles with integral sides and perimeter 122

Let A, B and C be the sides of a triangle.
A + B + C = 122
Also, A + B > C, B + C > A, A + C > B (sum of two sides > third side)
So maximum value of any side will be (122/2) – 1 = 60
S0, (60 – a) + (60 – b) + (60 – c) = 122 [0 ≤ a, b, c ≥ 59]
a + b + c = 58
So, total cases will be (58 + 3 – 1) C (3 – 1) = 60C2 = 30 x 59

This will include cases where ( a = 19, b = 18, c = 21) , ( a = 18, b = 19, c = 21) … but all of the cases are forming the same triangles. So we need to subtract the repetitions.

Now, a + b + c = 58

Where any two of a, b and c are the same.
2a + c = 58, here a can take values from 0 to 29 so 30 cases.
Similarly for b = c and c = a hence total 30 x 3 = 90 cases.
When a = b = c, not possible as a + b + c = 58

So, cases where all are different will be (59 x 30) – 90 = 1680

For distinct cases we will divide this by 3! = 6
We will get 1680/6 = 280
Cases where two are the same = 90
For distinct cases we will divide this by 3, 90/3 = 30
Total cases = 280 + 30 = 310

Short cut:
Total number of triangles with integral sides and perimeter n

When n is odd : [ (n + 3)^2/48]
Where n is even : [n^2/48]

Where [.] is the nearest integer (Don’t confuse with greatest integer function)

Applying for the above problem, [122^2]/48 = [310.08] = 310

To find the number of scalene triangles with integral sides and perimeter n
Put ( n – 6) instead of n in the above formula (for all triangles)

When n is Odd : [(n – 3)^2/48]
When n is even : [(n – 6) ^2/48]

Where [.] is the nearest integer

Example: Perimeter of a triangle is 150. Find the number of scalene triangles possible with integral sides

Using short cut – n = 150 (even)
Number of scalene triangles = [(150 – 6)^2/48] = 432

Detailed approach:
A + B + C = 150. Max value of any side can be 74
So, (74 – a) + ( 74 – b) + (74 – c) = 150
a + b + c = 72
Total cases ( 72 + 3 – 1) C ( 3 – 1) = 74C2 = 37 * 73

When two of them are same:
2a + c = 72, where a goes from 0 to 36 but if a = 24 then b = c = a
So 36 cases
Similarly 36 cases for b = c and c = a each

Also where a = b = c = 24 - > 1 case
(37 * 73) – ( 36 * 3) – 1 = 2592

Now divide this by 3! = 6 to find distinct cases
Number of scalene triangles = 2592/6 = 432

How many scalene triangles are possible if all the sides are integers and the perimeter of a triangle is 24 units?

OA: 7

Make sure that it is not greatest integer function here. We have to take nearest value

The perimeter of a triangle is 150. Find the number of isosceles triangles possible with integral sides.

A + B + C = 150
Max value of any side can be 74
So, (74 – a) + ( 74 – b) + (74 – c) = 150
a + b + c = 72
Total cases ( 72 + 3 – 1) C ( 3 – 1) = 74C2 = 37 * 73

When two of them are same
2a + c = 72, where a goes from 0 to 36 but if a = 24 then b = c = a
So 36 cases
Similarly 36 cases each for b = c and c = a each
Total 36 x 3 = 108 triangles.

But we have to exclude the repetitions
So 108/3 = 36 triangles.

Short cut:
To find the number of isosceles triangles with integral sides and perimeter n
No. of total triangles – no. of scalene triangles – no. of equilateral triangles
Here perimeter = 150
Total triangles = [n^2/48] = [468.75] = 469
Scalene triangles = [(n – 6)^2/48] = [432] = 432
Isosceles triangles = 469 – 432 – 1 = 36

The number of integral even sided triangle with perimeter 180
A + B + C = 180
Max value of any side can be 89
But sides are even so max value will be 88
Also, A, B and C are even so put A = 88 – 2a, B = 88 – 2b, C = 88 – 2c
(88 – 2a) + (88 – 2b) + (88 – 2c) = 180
2(a + b + c) = 84
a + b + c = 42
Total cases : (42 + 3 – 1)C(3 – 1) = 44C2 = 946
When two of them are same:
2a + c = 42, where a goes from 0 to 21 but if a = 14 then a = b = c. so, 21 cases
Similarly 21 cases for b = c and c = a each
Also, where a = b = c = 24 – 1 case
946 – ( 21 x 3) – 1 = 882
Divide by 3! To get distinct cases
Number of scalene triangles = 2592/6 = 147
Number of isosceles triangles = 21 x 3 / 3 = 21
Number of equilateral triangles = 1
Total 147 + 21 + 1 = 169

Short cut:
Number of triangles with all sides (integral) EVEN
Total number of triangles with integral sides and perimeter n (n is even) = n^2/48
[When all sides are even perimeter will also be even]
But, here we have to find number of triangles with all sides even so put n/2 instead of n in the above formula
Required number of triangles – n^2/(4 x 48 )
Here, perimeter = 180 and all sides should be even
Number of triangles = [n^2/( 4 x 48 )] = [180^2/ ( 4 x 48 )] = [168.75] = 169

Find the number of triangle having odd integral sides of perimeter equal to 153

A + B + C = 153
max value can be 76
put A = 76-(2a-1)
similarly for B & C

So, [76 - (2a-1) ] + [76 - (2b-1)] + [76-(2c-1)] = 153
2(a+b+c)+3=76(3) - 153
a + b + c = 36

total (36 + 3 - 1)C(3 - 1) = 38C2 ways = 703 ways

when a = b
2a + c = 36
a goes from 0 - 18 but this includes case where a = b = c
so 19 - 1 = 18 cases
similarly 18 cases for b = c & c = a each
and 1 case of equilateral triangle

Scalene - > (703- (38 * 3) - 1) /6 = 648/2 = 108
isosceles - > 18
equilateral - > 1
total 108 + 18 + 1 = 127

Or Apply formula (n + 3)^2/48 = [126.75] = 127