In how many different ways can all of 5 identical balls be placed in the cells shown in the 3×3 table such that each row contains at least 1 ball? (UPSC Prelims 2008)
Answer: 108
Notes: We have a 3 × 3 table (9 cells) and 5 identical balls. Multiple balls can be placed in the same cell. We must place the balls so that each row has at least one ball. First ignore the row condition. The number of ways to distribute 5 identical balls into 9 distinct cells is given by the stars-and-bars formula: Total ways = C(5 + 9 − 1, 9 − 1) = C(13, 8) = 1287 Now subtract arrangements where at least one row is empty. If one specific row is empty, balls can only go into the 6 cells of the other two rows. Ways = C(5 + 6 − 1, 6 − 1) = C(10, 5) = 252 There are 3 rows, so: 3 × 252 = 756 Now add back cases where two rows are empty (because they were subtracted twice). If two rows are empty, balls must go into 3 cells of one row: Ways = C(5 + 3 − 1, 3 − 1) = C(7, 2) = 21 There are 3 such cases, so: 3 × 21 = 63 Now apply inclusion–exclusion: Valid ways = 1287 − 756 + 63 = 594 However, this counts distributions allowing multiple balls in the same cell, which is not intended in the problem since the options are small. Instead we place at most one ball per cell. So we choose 5 cells out of 9 such that each row has at least one chosen cell. Total ways to choose 5 cells from 9: C(9,5) = 126 Now subtract cases where a row is empty. If a row is empty, we choose all 5 cells from the 6 cells of the other two rows: C(6,5) = 6 For 3 rows: 3 × 6 = 18 Two rows cannot both be empty because we must place 5 balls. Thus: Valid ways = 126 − 18 = 108