A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it, counting repetitions. What is the number of multisets of size 4 that can be constructed from n distinct elements so that at least one element occurs exactly twice?

GATE 2000 · Discrete Mathematics · Combinatorics · medium

Answer: n(n-1)^2 / 2

1. Identify valid multiplicity patterns: For size 4, the partitions of 4 that include at least one part equal to 2 are: (2,2) and (2,1,1). Patterns (4), (3,1), and (1,1,1,1) have no part equal to 2, so they are excluded.
2. Count pattern (2,2): Choose 2 elements from n to each appear twice: C(n,2) = n(n-1)/2.
3. Count pattern (2,1,1): Choose 1 element from n to appear twice (n ways), then choose 2 distinct elements from the remaining n-1 to appear once each: C(n-1, 2) = (n-1)(n-2)/2. Total: n(n-1)(n-2)/2.
4. Sum both cases and simplify: Total = n(n-1)/2 + n(n-1)(n-2)/2 = n(n-1)/2 * [1 + (n-2)] = n(n-1)/2 * (n-1) = n(n-1)^2 / 2.