Strictly Increasing Digits

Question

How many 5-digit numbers have strictly increasing digits, like 13589?

Accepted Answer

The bijection: a strictly increasing 5-digit number is completely determined by its set of digits, there is exactly one way to write a set in increasing order. And 0 can never appear: it would have to be the leading digit (it's smaller than everything), which is forbidden. So valid numbers correspond exactly to 5-element subsets of 1, 2, dots, 9: binom95 = 126. Why this is asked: the killer move is realizing that the ordering constraint removes the ordering choice, you're counting sets, not sequences. Candidates who start placing digits position-by-position drown in cases. The trap: including 0 and answering binom105 = 252. The leading-digit rule quietly excludes it here, but not in the decreasing version (see follow-up), which is exactly why interviewers ask both back-to-back.

Strictly Increasing Digits

Problem

Your answer

Hints