Caculating total combinations

Question

I don't know how to go about this programming problem.

Given two integers n and m, how many numbers exist such that all numbers have all digits from 0 to n-1 and the difference between two adjacent digits is exactly 1 and the number of digits in the number is atmost 'm'.

What is the best way to solve this problem? Is there a direct mathematical formula?

Edit: The number cannot start with 0.

Example: for n = 3 and m = 6 there are 18 such numbers (210, 2101, 21012, 210121 ... etc)

Update (some people have encountered an ambiguity): All digits from 0 to n-1 must be present.

Answer 1

This Python code computes the answer in O(nm) by keeping track of the numbers ending with a particular digit.

Different arrays (A,B,C,D) are used to track numbers that have hit the maximum or minimum of the range.

n=3
m=6
A=[1]*n # Number of ways of being at digit i and never being to min or max
B=[0]*n # number of ways with minimum being observed
C=[0]*n # number of ways with maximum being observed
D=[0]*n # number of ways with both being observed
A[0]=0 # Cannot start with 0
A[n-1]=0 # Have seen max so this 1 moves from A to C
C[n-1]=1 # Have seen max if start with highest digit
t=0
for k in range(m-1):
    A2=[0]*n
    B2=[0]*n
    C2=[0]*n
    D2=[0]*n
    for i in range(1,n-1):
        A2[i]=A[i+1]+A[i-1]
        B2[i]=B[i+1]+B[i-1]
        C2[i]=C[i+1]+C[i-1]
        D2[i]=D[i+1]+D[i-1]
    B2[0]=A[1]+B[1]
    C2[n-1]=A[n-2]+C[n-2]
    D2[0]=C[1]+D[1]
    D2[n-1]=B[n-2]+D[n-2]
    A=A2
    B=B2
    C=C2
    D=D2
    x=sum(d for d in D2)
    t+=x
print t