I was reading over a combinatorics textbook and came across an example with a somewhat vague explanation:
$\textit{How many 5-digit zip codes can exist where the digits are nondecreasing (like 12358 or 03399)?}$
The solution provided was,
These are just the size-5 multisets of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. For example, the zip code 03399 is represented by the multiset {0, 3, 3, 9, 9}, so the answer is $\left(\binom{10}{5}\right) = \binom{14}{5} = 2002.$
My understanding of "multichoosing" is that it represents the number of ways to select $k$ indistinguishable objects amongst $n$ distinguishable ones. For instance, the number of ways to distribute $k$ identical candies to $n$ people is $\left(\binom{n}{k}\right) = \binom{n+k-1}{k}$.
How does this connect with the zip-code question? Wouldn't a zip code containing decreasing digits i.e. 30398 also be included as a size-5 multiset?
Thanks in advance for your help! I'd love to get some clarity on this issue.
Multisets can have equal entries, but they have no order of the entries. The point is that given any multiset of digits you can find exactly one nondecreasing order of those digits. You do that by sorting them. Given the multiset $\{9,0,3,9,3\}$, which is the same as $\{0,3,3,9,9\}$, there is only one nondecreasing five digit sequence, which is $03399$, so if we can count the multisets we have a count of the nondecreasing zip codes.