GATE 2022 CS Q.32: solution and answer

GATE 2022 · CSQ.32 · 1 mark · NAT

The number of arrangements of six identical balls in three identical bins is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

There are 7 arrangements.

Official answer: 7Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

Balls are identical and bins are identical, so an arrangement is determined only by the multiset of bin contents. We therefore count the partitions of $6$ into at most $3$ parts. A bin may be empty, so fewer than $3$ non-zero parts is allowed.
One non-empty bin: $6$ . This gives $1$ arrangement.
Two non-empty bins: $5 + 1$ , $4 + 2$ , $3 + 3$ . The order of the parts does not matter, so there are no others. This gives $3$ arrangements.
Three non-empty bins: $4 + 1 + 1$ , $3 + 2 + 1$ , $2 + 2 + 2$ . The largest part can be at most $4$ , since the other two parts are each at least $1$ . With largest part $4$ the rest is $1 + 1$ . With largest part $3$ the rest is $2 + 1$ . With largest part $2$ the rest is $2 + 2$ . This gives $3$ arrangements.
Total $= 1 + 3 + 3 = 7$ .

KEY IDEA

With identical balls and identical bins, only the unordered list of bin counts matters. The count is the number of partitions of 6 into at most 3 parts, which is 7.

WATCH OUT FOR

Counting ordered distributions (distinct bins) gives $(2 8) = 28$ instead of 7. Another slip is leaving out the case with empty bins, such as the single bin holding all $6$ balls.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 6 Counting questions, with notes

GATE 2022 CS Q.32: solution and answer

Answer and solution

More Counting questions