1,2

Equally, number of different n-digit numbers, using only the digits 1 through n, where consecutive digits differ by 1. It is assumed that there are n different digits available even when n > 9.

Sr. Arworn, An algorithm for the number of endomorphisms on paths, Disc. Math., 309 (2009), 94-103 (see p. 95).

T. D. Noe, Table of n, a(n) for n=1..300

Joseph Myers, BMO 2008-2009 Round 1 Problem 1-Generalisation

It appears that the limit of a(n)/a(n-1) is decreasing towards 2. - Ben Thurston (benthurston27(AT)yahoo.com), Oct 04 2006

a(n) = (n+1)2^(n-1) - 4(n-1)binomial(n-2,(n-2)/2) for n even, a(n) = (n+1)2^(n-1) - (2n-1)binomial(n-1,(n-1)/2) for n odd. [From Joseph Myers (jsm(AT)polyomino.org.uk), Dec 23 2008]

For example, a(4)=16: the 16 strings are 1212, 1232, 1234, 2121, 2123, 2321, 2323, 2343, 3212, 3232, 3234, 3432, 3434, 4321, 4323, 4343.

p:= 0; paths := proc(m, n, s, t) global p; if(((t+1) <= m) and s <= (n)) then paths(m, n, s+1, t+1); end if; if(((t-1) > 0) and s <= (n)) then paths(m, n, s+1, t-1); end if; if(s = n) then p:=p+1; end if; end proc; sumpaths:=proc(j) global p; p:=0; sp:=0; for h from 1 to j do p:=0; paths(j, j, 1, h); sp:=sp+ p ; end do; sp; end proc; for l from 1 to 50 do sumpaths(l); end do; - Ben Thurston (benthurston27(AT)yahoo.com), Oct 04 2006

Sequence in context: A158920 A143123 A152089 this_sequence A156664 A025169 A111282

Adjacent sequences: A102696 A102697 A102698 this_sequence A102700 A102701 A102702

nonn

Don Rogers (donrogers42(AT)aol.com), Feb 07 2005

More terms from Ben Thurston (benthurston27(AT)yahoo.com), Oct 04 2006

a(20) onwards from David Wasserman (dwasserm(AT)earthlink.net), Apr 26 2008

Edited by N. J. A. Sloane (njas(AT)research.att.com), Jan 03 2009