# How many numbers are there where the digits increase from left to right?

Part (a): How many positive integers are there whose digits strictly increase from left to right? (For example, $$28$$, $$13589$$, and $$4$$ are all such integers. "Strictly" means no two digits can be equal, so $$15668$$ wouldn't count.)

Part (b): Among the positive integers whose digits strictly increase from left to right, how many have at most one even digit?

I don't know how to start part (a) but for part (b) I think I can just choose 1 of the digits to be even and there are 5 choices (0, 2, 4, 6 ,8), unless the first digit is even, then there is no 0.

• For part (b) I think you also need to consider where to place the even digit – 132479 Jul 12 at 18:04
• If 0 is the first digit, then it will be omitted in the standard form of the number. If 0 appears elsewhere, then all the digits to the left of it must be smaller than 0. – Acccumulation Jul 13 at 3:11
• What have you tried explicitly for (a)? Where are you stuck? See How to ask a good question. – Saad Jul 14 at 2:40

Selecting a positive integer whose digits increase strictly from left to right is the same thing as selecting a non-empty subset $$A$$ of $$\{1,\dots, 9\}$$. Simply arrange the elements of $$A$$ in increasing order. So the answer to your first question is $$2^9 - 1 = 511$$.
For the second part, selecting a number of the required form is the same thing as selecting a subset $$A$$ of $$\{1, 3, 5, 7, 9 \}$$ and a subset $$B$$ of $$\{2, 4, 6, 8\}$$, subject to the conditions $$\operatorname{Card}(B) \leq 1$$ and $$A \cup B \ne \varnothing$$. Thus we find that there are $$5 \cdot 2^5 - 1 = 159$$ numbers that answer the question.
The maximum length of such a number is $$9$$ (why?), so you can answer the first question by figuring out how many such numbers there are of each length from $$1$$ through $$9$$. HINT: For a given set of, say, $$5$$ different digits, how many ways are there to arrange those digits to form a number whose digits increase from left to right?
The second part is a bit trickier: you’ll have to take into account not only which even digit you’re using, but also where in the number it occurs. And where it can’t occur: can $$2$$ be anything but the first or second digit, for instance?
So for part (a), you just need to know the number of nonempty subsets of $$\{1,\ldots,9\}$$, which is $$2^9-1$$. For part (b), it is sufficient to first count the number of subsets of $$\{3,5,7,9\}$$ from which you subtract $$1$$ from one of the numbers. This is $$\binom{4}{1}+2\binom{4}2+3\binom 43+4\binom 44$$ Then, allowing $$1$$, we have $$1$$ as the first digit and subtract $$1$$ from one of the following digits. To get the total we just double the preceding number, to get $$2\binom 41+4\binom 42+6\binom 43+8\binom 44$$