十進法表記で考えてください．($1$) の条件は，$0$ となる桁がないということです． ($2$) の条件は，右にいくにつれて桁の数が小さくなっていくということです．
場合分けをすれば基本的な組合せの知識で解けますが，実は，発想の転換によって，エレガントに解くことができます．
ヒント
まずは桁数について考えてみましょう．どのような桁の数が条件を満たすでしょうか．同じ数が $2$ 度現れるような数は条件 $(2)$ を満たさないことに注意してください．
エレガントな解答
まず，$987654321$ という数を考えます．この数は $2$ 条件を満たしています．つぎに，この自然数から幾つかの数を消去して得られる自然数を考えます．たとえば，$2,3,5$ を消去すると，$987641$ が得られます，$9,8,7,6,5,2,1$ を消去すると，$743$ が得られます．このようにして得られた数たちは，また $2$ 条件を満たしています．特に，$987654321$ からいくつかの数を消去して得られる数たちと，$2$ 条件を満たす数たちは一対一に対応します．
したがって，$987654321$ から数を消す方法を考えれば良いです．ある数について，それを消去するかしないかの $2$ 通りが考えられることと，すべての数を消去してはいけないことを考慮すると，消去する方法の総数は， $$2^9-1=511$$ よって，$511$ 通りです．
別解
桁数で場合分けして解くこともできます．
求める自然数の桁数は $1$ 以上 $9$ 以下です．自然数 $k\ (1\le k \le 9)$ について，$1,2,3,4,5,6,7,8,9$ から $k$ 個の異なる数字を選ぶ方法は ${}_9 \mathrm{C} _{k}$ 通りあります．選んだ $k$ 個の数について，条件 ($2$) を満たすような並べかたは $1$ 通りしかありません．(大きい順に並べるしかない) つまり，条件を満たす $k$ 桁の自然数の総数は，${}_9 \mathrm{C} _k$ です．よって，求めるべき数は $$\sum_{k=1}^9 {}_9 \mathrm{C} _k=(1+1)^9-1=511$$ です．ここで，最初の等号は二項定理を用いています．
