Skip to content
GATETECH
Official PYQ · 2003Q34Combinatorics: Counting, Recurrence Relations, Generating FunctionsMCQ1 mark

GATE CS 2003 Q34 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Explain with AI

mm identical balls are to be placed in nn distinct bags. You are given that m≥knm \geq kn, where kk is a natural number ≥1\geq 1. In how many ways can the balls be placed in the bags if each bag must contain at least kk balls?

Choose one option
View worked solution

Answer: B

This problem can be modeled as finding the number of integer solutions to the equation:

x1+x2+⋯+xn=mx_1 + x_2 + \dots + x_n = m

where xix_i represents the number of identical balls placed in the ii-th distinct bag, subject to the constraint that each bag must contain at least kk balls, i.e., xi≥kx_i \geq k for all 1≤i≤n1 \leq i \leq n.

To solve this, we can define a new set of variables yiy_i such that:

yi=xi−kwhere yi≥0y_i = x_i - k \quad \text{where } y_i \geq 0

Substituting xi=yi+kx_i = y_i + k into our original equation gives:

(y1+k)+(y2+k)+⋯+(yn+k)=m(y_1 + k) + (y_2 + k) + \dots + (y_n + k) = m y1+y2+⋯+yn+kn=my_1 + y_2 + \dots + y_n + kn = m y1+y2+⋯+yn=m−kny_1 + y_2 + \dots + y_n = m - kn

Since each yi≥0y_i \geq 0, this is a standard stars-and-bars problem of distributing N=m−knN = m - kn identical items into nn distinct bins.

The number of non-negative integer solutions is given by the formula:

(N+n−1n−1)\binom{N + n - 1}{n - 1}

Substituting N=m−knN = m - kn:

(m−kn+n−1n−1)\binom{m - kn + n - 1}{n - 1}

This matches Option B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Combinatorics: Counting, Recurrence Relations, Generating Functions questions