Number of elements in a set with increasing digits

Question

For the set $S$ which consists of all positive integers whose digits strictly increase from left to right. I have to find the median of this set.

Here is what I have done so far.

I identified the number of elements of this set as $511$. ($2^9-1$) $1$ for the empty set. The median is $256$. I am on the right track? How do I find the $256$th number?

Answer 1

Hint: Look at smaller bases and see if you can spot a meaningful pattern.

In base 2 we have only 1 element that does this. Namely, $1$

In base 3 we have 3 elements. $1,2,12$

$2 \choose 1$ elements with length 1 and $2 \choose 2$ elements with length 2.

In base 4 we have 7 such elements. $1,2,3,12,13, 23, 123$

$3 \choose 1$ elements with length 1 and $3 \choose 2$ elements with length 2 and $3 \choose 3$ elements with length 3.

In base 5, we have 15 such elements:

$1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234$

$4 \choose 1$ elements with length 1 and $4 \choose 2$ elements with length 2 and $4 \choose 3$ elements with length 3 and $4 \choose 4$ elements with length 4.

I think this pattern should prove useful.

Answer 2

There are $9\choose 1$ element of $S$ with $1$ digit.

There are $9 \choose 2$ elements of $2$ with $S$ digits.

.....

There are ${9\choose 7}= {9\choose 2}$ elements of $S$ with $7$ digits.

There are ${9\choose 8} = {9\choose 1}$ elements of $S$ with $8$ digits.

And $1$ element with nine digits.

Let's ignore the single nine digit one for now.

The $1$ digits elements are paired up with the $8$ digits. The $2$ digits elements are paired up with the $7$ digits. And so on. So the $4$ digit elements are paired up with the $5$ digits.

So if we did not include the $9$ digit number the last $4$ digit number ($6789$) would be paired with the first $5$ digit number $12345$. And the "center" number would be between those two.

But if we include the $9$ digit number so there is an odd number of elements then the center is the first $5$ digit number ($12345$).

So that is the median.

If we had a odd rather than even base $b$ (rather than base $10$) then we'd be dealing with an even number of digits from $1$ to $b-1$. Then of the matching $1$ digits with $b-2$ digits and $2$ with $b-3$ digits, the group of $\frac {b-1}2$ digits are the "center" group and don't match up. The number then would be one more then the first half of them. Which one is that? That's little harder to figure out.

Now the mean. That's a different question altogether....

Answer 3

Let's forget about number with 9 digits {123456789}.

Now we will have 510 number and 255 and 256 will be in the middle of this new set and 256th is 12345 the first number with 5 digits and 255th is the last number with four digits. so all you need is to add {123456789} to the end of the set and your median will be 12345 or the first number with five digits. The answer is 12345

Sorry for my bad English, I can Explain more if you need.