number of ways to form a specific number with n digits I'm trying to find the number of ways to form a number with certain properties.
The number has following properties. 
The first digit is always 1. 
The $n$th digit can take values from 1 to k+1 where k is the maximum digit that is appearing in 1st to (n-1)th digit. 
so when n = 1 you only have 1. when n = 2 you have 11 and 12. when n = 3 you have 111, 112, 121, 122, 123, but you cant have 113. for n=4, you have 1111, 1112, 1121, 1122, 1123, 1211,1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1234. 
any help in form of any direct formula and recursive formula? 

Let $F(k,n)$ be the number of your $n$-digit numbers where the maximum digit that appears is $k$ (so you are interested in $\sum_{k=1}^9 F(k,n)$).
The initial conditions are 
$F(1,1) = 1$ and $F(k,1) = 0$ otherwise.
The recurrence is $F(k,n+1) = F(k-1,n) + k F(k,n)$.
I get $$F(k,n) = \sum_{j=1}^k \frac{(-1)^{k-j}}{(k-j)!j!} j^n$$  
And then $$\sum_{k=1}^9 F(k,n) = \frac{2119}{5760} + \frac{103}{560} 2^n + \frac{53}{864} 3^n + \frac{11}{720} 4^n + \frac{1}{320} 5^n + \frac{1}{2160} 6^n + \frac{1}{10080} 7^n +\frac{1}{362880} 9^n$$
