Median of the set of numbers which consists of all positive integers whose digits strictly increase from left to right

Consider the set $$S=\{1,2,3,4,5,6,7,8,9,12,13,14,15,16,17,18,19,23,24,\ldots,123456789\},$$ which consists of all positive integers whose digits strictly increase from left to right. This set is finite. What is the median of the set?

This problem is harder than I thought at first. I first simply though the solution was $\frac{123456789+1}{2}=61728395.$ Turns out I'm wrong! Where am I going wrong? I checked my work and $61728395-1+1=61728395.$ Also,

$123456789-61728395+1=61728395.$ These are equal, so the distance should also be equal. Where am I going wrong?

Solution 1:

There are 9 of these numbers having 1 digit, $\binom{9}{2}$ having 2 digits, and in general $\binom{9}{k}$ having $k$ digits. The total number of elements in this set is thus $\binom{9}{1} + \binom{9}{2} + \cdots + \binom{9}{9} = 2^9-1$, by the binomial theorem, so the median is the $2^8$-th element.

The binomial theorem and symmetry of binomial coefficients also tells us $$\binom{9}{0} + \binom{9}{1} + \binom{9}{2} + \binom{9}{3} + \binom{9}{4} = \binom{9}{5} + \binom{9}{6} + \binom{9}{7} + \binom{9}{8} + \binom{9}{9} = 2^8$$

Hence $\binom{9}{1} + \binom{9}{2} + \binom{9}{3} + \binom{9}{4} = 2^8-1$. So the median is the first element having 5 digits, which is $12345$.