Use PIE to count the number of $6$-multisets of $[6]$ in which no digit occurs more than twice.

124 Views Asked by At

This is one of a set of several problems in my book I am having difficulty not just solving, but also understanding the provided solutions.

The given answer is $462 - 336 + 15 = 141.$

I'll try and see where the terms of the equality above come from.

$[6] = \{1, 2, 3, 4, 5, 6\}.$

The number of all multisets of size six sourced out of $[6]$ is $\binom{6 + 6 -1}{6} = \binom{11}{6} = 462,$ so that's where the first term of $462 - 336 + 15$ come from.

All the multisets of size six where each one contains a digit that occurs at least three times can be rewritten in their type form like so: $$(3, 3), (3, 2, 1), (3, 1, 1, 1), (4, 2), (4, 1, 1), (5, 1), (6)$$

Then,

$|(3, 3)| + |(3, 2, 1)| + |(3, 1, 1, 1)| + |(4, 2)| + |(4, 1, 1)| + |(5, 1)| + |(6)| \\ = (6 \cdot 5) + (6 \cdot 5 \cdot 4) + (6 \cdot \binom 53) + (6 \cdot 5) + (6 \cdot \binom 52) + (6 \cdot 5) + 6 \\ = 30 + 120 + 60 + 30 + 60 + 30 + 6 \\ = 336.$

So that's where the second term of $462 - 336 + 15$ must come from.

I am not clear on where $15$ in $462 - 336 + 15$ come from. So, that's what I'd like to know. Thanks.