How many total monotonous numbers are there?

Question

Question: Call a positive integer monotonous if it is a one-digit number or its digits, when read from left to right, form either a strictly increasing or decreasing sequence. For example, 3, 23578, and 987620 are monotonous, but 88, 7434, and 23557 are not. How many monotonous positive integers are there?

I attempted to solve the following problem by finding out how many 2-digit and 3-digit monotonous numbers there are and then finding the pattern within them and applying them all the way to the max number of digits in a monotonous number - 9. I figured that when the tens digit is 0, there are 9 possible combinations for the ones digit, when the tens digit is 1, there are 8 possible combinations, and so forth. Thus with 1+2+3+4+5+6+7+8+9 I arrived at 45 increasing monotonous numbers for 2-digit numbers. Then as there is one decreasing monotonous number for every increasing monotonous number, I multiplied it by 2 to get 90 total 2-digit monotonous numbers. However I can not figure out how to accomplish this for 3-digit numbers. Can someone please help me with this, or if there is a more efficient method, could you please explain it? Thanks a lot!

Answer 1

Consider the string $9876543210$. We can choose or ignore each digit from this string to get decreasing monotonous numbers for a total of $2^{10}=1024$ options. Since that includes ignoring all of the digits and only choosing $0$, there are $1022$ valid choices that yield positive numbers.

Similarly we can choose from the string $123456789$ to get $2^9-1=511$ options for increasing monotonous numbers.

Finally, noting that the $9$ single-digit numbers belong to both groups, the total count of different monotonous numbers is $1022+511-9=1524$.

Answer 2

There are $10$ digits and $10 \choose n$ ways to choose $n$ distinct digits (which must be distinct to preserve strict monotonicity). There is exactly one way to arrange those $n$ digits in decreasing order. Thus there are \begin{align*} {10\choose1}+\dots+{10\choose10}&={10\choose0}1^01^{10-0}+\dots+{10\choose10}1^{10}1^{10-10}-1\\ &=(1+1)^{10}-1\\ &=2^{10}-1\\ &=1023\\ \end{align*} strictly decreasing non-negative integers. This counted the number $0$, so subtract one from our result for $1022$ strictly decreasing positive integers.

Next consider increasing integers. Anything with $1$ digit has already been counted, so we only want numbers with $2$ or more digits. Additionally, none of these integers will have the digit $0$, since it would be the first digit, yielding a result with a smaller number of digits. We similarly find \begin{align*} {9\choose2}+\dots+{9\choose9}&=2^9-10\\ &=502\\ \end{align*} additional strictly increasing positive integers.

Adding these two results together yields $\boxed{1524}$ total monotonous positive integers.

Answer 3

side fun note : 1,524 could also be weirdly expressed as

a chain of 2s and 8s

(     2 ^ 8 ) * ( 8 - 2 ) - 8 - 2 - 2
( 2 ^ 8 - 2 ) * ( 8 - 2 )
( 2 - 2 ^ 8 ) * ( 2 - 8 )

a chain of 2s and 6s

 6 * (6 ^ 2 + 6 * 6 ^ 2 + 2 )

a chain of only 3s

(3 + 3) * (3 + 3 ^ 3 + 3 ^ (3 + 3) + 3) / 3

a partially-symmetrical chain of 2s and 3s

(2 ^ 3 ^ 2 - 2 * 3 + 2) * 3

a grouped chain of 4s and 5s

4 * ( 4 ^ 4 + 5 * 5 * 5 )

an up-down double straight

( 1 * 2^3 + 4 )*( 4^3 * 2 - 1 )

and finally, the most elegant form :::

[ 12 * 127 ]