After doing some more research, I think there may actually be a mathematical approach after all, although the math is advanced for me. Douglas S. Stones pointed me in the direction of Joseph Myers' (2008) article, BMO 2008–2009 Round 1 Problem 1—Generalisation, which derives formulas for calculating the number of zig-zag paths across a rectangular board.

As I understand it, in Anirudh's example, our board would have 6 rows of length 3 (I believe this would mean n=3 and r=6 in the article's terms). We can visualize our board so:

0 1 2 example zig-zag path: 0 0 1 2 1 0 1 2 0 0 1 2 1 0 1 2 2 0 1 2 1 

Since Myers' formula m(n,r) would generate the number for all the zig-zag paths, that is, the number of all 6-digit numbers where all adjacent digits are consecutive and digits are chosen from (0,1,2), we would still need to determine and subtract those that begin with zero and those that do not include all digits.

If I understand correctly, we may do this in the following way for our example, although generalizing the concept to arbitrary m and n may prove more complicated:

Let m(3,6) equal the number of 6-digit numbers where all adjacent digits are consecutive and digits are chosen from (0,1,2). According to Myers, m(3,r) is given by formula and also equals OEIS sequence A029744 at index r+2, so we have m(3,6) = 16 How many of these numbers start with zero? Myers describes c(n,r) as the number of zig-zag paths whose colour is that of the square in the top right corner of the board. In our case, c(3,6) would include the total for starting-digit 0 as well as starting-digit 2. He gives c(3,2r) as 2^r, so we have c(3,6) = 8. For starting-digit 0 only, we divide by two to get 4. Now we need to obtain only those numbers that include all the digits in the range, but how? We can do this be subtracting m(n-1,r) from m(n,r). In our case, we have all the m(2,6) that would include only 0's and 1's, and all the m(2,6) that would include 1's and 2's. Myers gives m(2,anything) as 2, so we have 2*m(2,6) = 2*2 = 4 But we must remember that one of the zero-starting numbers is included in our total for 2*m(2,6), namely 010101. So all together we have m(3,6) - c(3,6)/2 - 4 + 1 = 16 - 4 - 4 + 1 = 9 To complete our example, we must follow a similar process for m(3,5), m(3,4) and m(3,3). Since it's late here, I might follow up tomorrow... 

One approach could be to program it recursively, calling the function to add as well as subtract from the last digit.

Haskell code:

import Data.List (sort,nub) f n m = concatMap (combs n) [n..m] combs n m = concatMap (\x -> combs' 1 [x]) [1..n - 1] where combs' count result | count == m = if test then [concatMap show result] else [] | otherwise = combs' (count + 1) (result ++ [r + 1]) ++ combs' (count + 1) (result ++ [r - 1]) where r = last result test = (nub . sort $ result) == [0..n - 1] 

Output:

*Main> f 3 6 ["210","1210","1012","2101","12101","10121","21210","21012" ,"21010","121210","121012","121010","101212","101210","101012" ,"212101","210121","210101"] 

In response to Anirudh Rayabharam's comment, I hope the following code will be more 'pseudocode' like. When the total number of digits reaches m, the function g outputs 1 if the solution has hashed all [0..n-1], and 0 if not. The function f accumulates the results for g for starting digits [1..n-1] and total number of digits [n..m].

Haskell code:

import qualified Data.Set as S g :: Int -> Int -> Int -> Int -> (S.Set Int, Int) -> Int g n m digitCount lastDigit (hash,hashCount) | digitCount == m = if test then 1 else 0 | otherwise = if lastDigit == 0 then g n m d' (lastDigit + 1) (hash'',hashCount') else if lastDigit == n - 1 then g n m d' (lastDigit - 1) (hash'',hashCount') else g n m d' (lastDigit + 1) (hash'',hashCount') + g n m d' (lastDigit - 1) (hash'',hashCount') where test = hashCount' == n d' = digitCount + 1 hash'' = if test then S.empty else hash' (hash',hashCount') | hashCount == n = (S.empty,hashCount) | S.member lastDigit hash = (hash,hashCount) | otherwise = (S.insert lastDigit hash,hashCount + 1) f n m = foldr forEachNumDigits 0 [n..m] where forEachNumDigits numDigits accumulator = accumulator + foldr forEachStartingDigit 0 [1..n - 1] where forEachStartingDigit startingDigit accumulator' = accumulator' + g n numDigits 1 startingDigit (S.empty,0) 

Output:

*Main> f 3 6 18 (0.01 secs, 571980 bytes) *Main> f 4 20 62784 (1.23 secs, 97795656 bytes) *Main> f 4 25 762465 (11.73 secs, 1068373268 bytes) 

model your problem as 2 superimposed lattices in 2 dimensions, specifically as pairs (i,j) interconnected with oriented edges ((i0,j0),(i1,j1)) where i1 = i0 + 1, |j1 - j0| = 1, modified as follows:

• dropping all pairs (i,j) with j > 9 and its incident edges
• dropping all pairs (i,j) with i > m-1 and its incident edges
• dropping edge ((0,0), (1,1))

this construction results in a structure like in this diagram:

:

the requested numbers map to paths in the lattice starting at one of the green elements ((0,j), j=1..min(n-1,9)) that contain at least one pink and one red element ((i,0), i=1..m-1, (i,n-1), i=0..m-1 ). to see this, identify the i-th digit j of a given number with point (i,j). including pink and red elements ('extremal digits') guarantee that all available diguts are represented in the number.

Analysis

for convenience, let q1, q2 denote the position-1.

let q1 be the position of a number's first digit being either 0 or min(n-1,9). let q2 be the position of a number's first 0 if the digit at position q1 is min(n-1,9) and vv.

case 1: first extremal digit is 0

the number of valid prefixes containing no 0 can be expressed as sum_{k=1..min(n-1,9)} (paths_to_0(k,1,q1), the function paths_to_0 being recursively defined as

paths_to_0(0,q1-1,q1) = 0; paths_to_0(1,q1-1,q1) = 1; paths_to_0(digit,i,q1) = 0; if q1-i < digit; paths_to_0(x,_,_) = 0; if x >= min(n-1,9) // x=min(n-1,9) mustn't occur before position q2, // x > min(n-1,9) not at all paths_to_0(x,_,_) = 0; if x <= 0; // x=0 mustn't occur before position q1, // x < 0 not at all and else paths_to_0(digit,i,q1) = paths_to_0(digit+1,i+1,q1) + paths_to_0(digit-1,i+1,q1); 

similarly we have

paths_to_max(min(n-1,9),q2-1,q2) = 0; paths_to_max(min(n-2,8),q2-1,q2) = 1; paths_to_max(digit,i,q2) = 0 if q2-i < n-1; paths_to_max(x,_,_) = 0; if x >= min(n-1,9) // x=min(n-1,9) mustn't occur before // position q2, // x > min(n-1,9) not at all paths_to_max(x,_,_) = 0; if x < 0; and else paths_to_max(digit,q1,q2) = paths_max(digit+1,q1+1,q2) + paths_to_max(digit-1,q1+1,q2); 

and finally

paths_suffix(digit,length-1,length) = 2; if digit > 0 and digit < min(n-1,9) paths_suffix(digit,length-1,length) = 1; if digit = 0 or digit = min(n-1,9) paths_suffix(digit,k,length) = 0; if length > m-1 or length < q2 or k > length paths_suffix(digit,k,0) = 1; // the empty path and else paths_suffix(digit,k,length) = paths_suffix(digit+1,k+1,length) + paths_suffix(digit-1,k+1,length); 

... for a grand total of

number_count_case_1(n, m) = sum_{first=1..min(n-1,9), q1=1..m-1-(n-1), q2=q1..m-1, l_suffix=0..m-1-q2} ( paths_to_0(first,1,q1) + paths_to_max(0,q1,q2) + paths_suffix(min(n-1,9),q2,l_suffix+q2) ) 

case 2: first extremal digit is min(n-1,9)

case 2.1: initial digit is not min(n-1,9) this is symmetrical to case 1 with all digits d replaced by min(n,10) - d. as the lattice structure is symmetrical, this means number_count_case_2_1 = number_count_case_1.

case 2.2: initial digit is min(n-1,9) note that q1 is 1 and the second digit must be min(n-2,8). thus

number_count_case_2_2 (n, m) = sum_{q2=1..m-2, l_suffix=0..m-2-q2} ( paths_to_max(1,1,q2) + paths_suffix(min(n-1,9),q2,l_suffix+q2) ) 

so the grand grand total will be

number_count ( n, m ) = 2 * number_count_case_1 (n, m) + number_count_case_2_2 (n, m); 

Code

i don't know whether a closed expression for number_count exists, but the following perl code will compute it (the code is but a proof of concept as it does not use memoization techniques to avoid recomputing results already obtained):

use strict; use warnings; my ($n, $m) = ( 5, 7 ); # for example $n = ($n > 10) ? 10 : $n; # cutoff sub min sub paths_to_0 ($$$) { my ( $d , $at , $until ) = @_; # if (($d == 0) && ($at == $until - 1)) { return 0; } if (($d == 1) && ($at == $until - 1)) { return 1; } if ($until - $at < $d) { return 0; } if (($d <= 0) || ($d >= $n))) { return 0; } return paths_to_0($d+1, $at+1, $until) + paths_to_0($d-1, $at+1, $until); } # paths_to_0 sub paths_to_max ($$$) { my ( $d , $at , $until ) = @_; # if (($d == $n-1) && ($at == $until - 1)) { return 0; } if (($d == $n-2) && ($at == $until - 1)) { return 1; } if ($until - $at < $n-1) { return 0; } if (($d < 0) || ($d >= $n-1)) { return 0; } return paths_to_max($d+1, $at+1, $until) + paths_to_max($d-1, $at+1, $until); } # paths_to_max sub paths_suffix ($$$) { my ( $d , $at , $until ) = @_; # if (($d < $n-1) && ($d > 0) && ($at == $until - 1)) { return 2; } if ((($d == $n-1) && ($d == 0)) && ($at == $until - 1)) { return 1; } if (($until > $m-1) || ($at > $until)) { return 0; } if ($until == 0) { return 1; } return paths_suffix($d+1, $at+1, $until) + paths_suffix($d-1, $at+1, $until); } # paths_suffix # # main # number_count = sum_{first=1..min(n-1,9), q1=1..m-1-(n-1), q2=q1..m-1, l_suffix=0..m-1-q2} ( paths_to_0(first,1,q1) + paths_to_max(0,q1,q2) + paths_suffix(min(n-1,9),q2,l_suffix+q2) ) my ($number_count, $number_count_2_2) = (0, 0); my ($first, $q1, i, $l_suffix); for ($first = 1; $first <= $n-1; $first++) { for ($q1 = 1; $q1 <= $m-1 - ($n-1); $q1++) { for ($q2 = $q1; $q2 <= $m-1; $q2++) { for ($l_suffix = 0; $l_suffix <= $m-1 - $q2; $l_suffix++) { $number_count = $number_count + paths_to_0($first,1,$q1) + paths_to_max(0,$q1,$q2) + paths_suffix($n-1,$q2,$l_suffix+$q2) ; } } } } # # case 2.2 # for ($q2 = 1; $q2 <= $m-2; $q2++) { for ($l_suffix = 0; $l_suffix <= $m-2 - $q2; $l_suffix++) { $number_count_2_2 = $number_count_2_2 + paths_to_max(1,1,$q2) + paths_suffix($n-1,$q2,$l_suffix+$q2) ; } } $number_count = 2 * $number_count + number_count_2_2;