# How many of the 9000 four digit integers have four digits that are increasing?

How to find the number of distinct four digit numbers that are increasing or decreasing?

The correct answer is $2{9 \choose 4} + {9 \choose 3} = 343$. How to get there?

-

For every collection of $4$ distinct digits, there is a unique way to arrange the digits so that they are decreasing, and a unique way to arrange them so that they are increasing. This gives $2 \binom{10}{4}$ different sequences that are increasing or decreasing, but not all correspond to a four-digit number. For increasing sequences, you cannot have $0$ as a first digit. This rules out $\binom{9}{3} = 84$ possibilities. So the total is $2(210) - 84=336 \neq 343$...?

-

The analysis that was used goes as follows:

Not using $0$: We choose $4$ non-zero digits. Once we have done that, we can arrange them in increasing order in $1$ way, and in decreasing order in $1$ way, for a total of $2\binom{9}{4}$.

Using $0$: They can only be decreasing. And we need to choose $3$ non-zero digits to go with the $0$. This can be done in $\binom{9}{3}$ ways.

I prefer Juanito's approach. Note that the sum is not $343$, so if the book got that, there is a computational error.

-
Strange, my textbook shows 343 and why is n = 9? Is it just 1 -9 or is there more meaning behind using 9 as n. I am probably overthinking this. – user3718584 Jul 21 '14 at 17:56
There are $9$ non-zero digits, so yes, it is $1,2,\dots,9$. – André Nicolas Jul 21 '14 at 17:58
Why is it that we are not allowed to start with 0 for an increasing 4 digit set? – user3718584 Jul 21 '14 at 18:01
Because we are using the $9000$ four-digit numbers. The number $0347$ is not a four-digit number. – André Nicolas Jul 21 '14 at 18:04

For decreasing numbers, we can also take zero as a possible candidate digit( $4320$ is ok, $0234$ not ok). Once we have a set of 4 digits(for example, $1-9-6-7$), the number is uniquely determined by the increasing/ decreasing order($1679$ or $9761$).

So, number of decreasing numbers

= numbers without $0$ as a digit + numbers with $0$ as one of the digits.

= all possible combinations of 4 digits from $\{1, ... 9 \}$ + all possible combinations of $3$ digits from $\{1, ... 9\}$, $0$ being the already selected digit.

= ${9 \choose 4} + {9 \choose 3}$.

Number of increasing numbers=all possible combinations of 4 digits from $\{1, ...9\} = {9 \choose 4}$.