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


  • Director, Genius Tutorials, Karnal ( Haryana ) & Delhi | MSc (Mathematics)


    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

    1. 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.

    2. 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


 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.