# 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?

-
Are you assuming these are decimal digits (so each digit is $\le 9$)? – Robert Israel Apr 2 '12 at 18:24
Fine. Lets assume that n is between 1 and 9. – Manoj R Apr 2 '12 at 18:27

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$$
The name of $F(k,n)$ is 'Stirling numbers of the second kind' that is 'the number of ways to partition a set of n labelled objects into k nonempty unlabelled subsets' and the number of terms is given by 'Bell numbers' (corrected...). – Raymond Manzoni Apr 3 '12 at 7:40