GATE CS 2022 Q22 — Combinatorics: Counting, Recurrence Relations, Generating Functions

This problem asks for the number of ways to distribute $6$ identical balls into $3$ identical bins. Since both the balls and the bins are identical, this is equivalent to finding the number of partitions of the integer $6$ into at most $3$ parts (where parts can be zero).

Let the number of balls in the three bins be $x_1, x_2,$ and $x_3$. Since the bins are identical, we can assume without loss of generality that:

We can systematically list all such non-negative integer partitions:

1. $(6, 0, 0)$
2. $(5, 1, 0)$
3. $(4, 2, 0)$
4. $(4, 1, 1)$
5. $(3, 3, 0)$
6. $(3, 2, 1)$
7. $(2, 2, 2)$

Counting these configurations, we find there are exactly 7 possible arrangements.