1
$\begingroup$

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?

  • 0
    Fine. Lets assume that n is between 1 and 9.2012-04-02

1 Answers 1

2

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$

  • 1
    The name of $F(k,n)$ is ['Stirling numbers of the second kind'](http://en.wikipedia.org/wiki/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'](http://en.wikipedia.org/wiki/Bell_number) (corrected...).2012-04-03