Solution
Digits That Never Decrease
Show the problem again
How many six-digit positive integers (from 100000 to 999999) have digits that are non-decreasing from left to right, such as 112399 or 555555? Give an integer.
Worked solution
The answer is 3003. The leading digit is at least 1, and the digits never decrease, so no digit can be 0. A non-decreasing string of six digits from {1, ..., 9} is determined entirely by how many times each digit appears, so these numbers correspond exactly to multisets of size 6 drawn from 9 types. By stars and bars there are C(6 + 9 − 1, 6) = C(14, 6) = 3003.
Source: Classic counting exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.