4.19*. (Jury, Finland, 82). Determine the sum of all natural numbers, each of which has digits in its decimal representation that form an increasing or decreasing sequence.
4.19. Let $A$ and $B$ be the sets of natural numbers with strictly increasing and strictly decreasing digits, respectively. The sum of all numbers in a set $M$ will be denoted by $S(M)$. We will partition the set $B$ into two non-intersecting subsets $B_{0}$ and $B_{1}$, consisting of numbers that end in the digit 0 and those that do not, respectively; thus,

$$
S(B)=S\left(B_{0}\right)+S\left(B_{1}\right) .
$$

If we pair the numbers $b \in B_{1}$ and $(10 b) \in B_{0}$, we obtain a one-to-one correspondence between the sets $B_{1}$ and $B_{0}$; in this case,

$$
\begin{aligned}
& S\left(B_{0}\right)=10 S\left(B_{1}\right) \\
& S(B)=11 S\left(B_{1}\right)
\end{aligned}
$$

Furthermore, if we pair the numbers

$$
a=\overline{a_{1} \ldots a_{k}} \in A \quad \text { and } \quad b=\overline{\left(10-a_{1}\right) \ldots\left(10-a_{k}\right)} \in B_{1}
$$

(then

$$
\left.=a+b=(10 / 9)\left(10^{k}-1\right)\right)
$$

we obtain a one-to-one correspondence between the sets $A$ and $B_{1}$. Since each number in the set $A$ is obtained from the number 123456789 by removing some digits, and for each value of $k=1,2, \ldots, 9$ there are exactly $C_{9}^{k}$ $k$-digit numbers in the set $A$, then

$$
\begin{aligned}
& l=S(A)+S\left(B_{1}\right)=\sum_{k=1}^{9} C_{9}^{k}(10 / 9)\left(10^{k}-1\right)= \\
&=(10 / 9)\left(\sum_{k=0}^{9} C_{9}^{k} 10^{k}-\sum_{k=0}^{9} C_{9}^{k}\right)=(10 / 9)\left((1+10)^{9}-(1+1)^{9}\right)= \\
&=(10 / 9)\left(11^{9}-2^{9}\right)
\end{aligned}
$$

Let $B_{2}$ be the subset of numbers in the set $B$ that start with the digit 9, and let the set of all other numbers in the set $B$ together with the number 0 be denoted by $B_{3}$ (then $S(B)=S\left(B_{2}\right)+$ $+S\left(B_{3}\right)$ ). Then there is a one-to-one correspondence between the numbers

$$
a=\overline{a_{1} \ldots a_{k}} \in A \quad \text { and } \quad b=\overline{\left(9-a_{1}\right) \ldots\left(9-a_{k}\right)} \in B_{3}
$$

such that $a+b=$ $=10^{k}-1$. Therefore,

$$
m=S(A)+S\left(B_{3}\right)=\sum_{k=1}^{9} C_{9}^{k}\left(10^{k}-1\right)=11^{9}-2^{9}
$$

Finally, if we pair each number

$$
b=\overline{9 b_{1} \ldots b_{k}} \in B_{2}
$$

with the number

$$
a=\overline{\left(9-b_{1}\right) \ldots\left(9-b_{k}\right)} \in A
$$

for $k \geqslant 1$ and the number 0 for $k=0$, we obtain a one-to-one correspondence between the sets $B_{2}$ and $A \cup\{0\}$, such that $a+b=$ $=10^{k+1}-1$. Therefore,

$$
n=S(A)+S\left(B_{2}\right)=\sum_{k=0}^{9} C_{9}^{k}\left(10^{k+1}-1\right)=10 \cdot 11^{9}-2^{9}
$$

and

$$
m+n=S(A)+S\left(B_{3}\right)+S(A)+S\left(B_{2}\right)=2 S(A)+S(B) .
$$

Thus, we obtain the system

$$
\left\{\begin{aligned}
S(A)+(1 / 11) S(B) & =l=(10 / 9)\left(11^{9}-2^{9}\right) \\
2 S(A)+S(B) & =m+n=11^{10}-2^{10}
\end{aligned}\right.
$$

from which we find

$$
S(A)=(1 / 9)(11 l-m-n), \quad S(B)=(11 / 9)(m+n-2 l) .
$$

The sets $A$ and $B$ have 9 common elements, namely, the single-digit numbers, the sum of which is 45. Therefore, the desired sum is

$$
\begin{aligned}
& S(A)+S(B)-45=\frac{10}{9}(m+n)-\frac{11}{9} l-45= \\
& \quad=\frac{10}{9}\left(11^{10}-2^{10}\right)-\frac{10}{81} \cdot 11^{10}+\frac{55}{81} \cdot 2^{10}-45=\frac{80}{81} \cdot 11^{10}-\frac{35}{81} \cdot 2^{10}-45
\end{aligned}
$$