OFFSET
0,3
COMMENTS
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.
Number of endomorphisms of a path P_n. - N. J. A. Sloane, Sep 20 2009
a(n) is also the number of distinct paths of length n starting from the bottom row of an n X n chess board and ending at the top row, such that all the n squares traversed in the path are of the same color. - Kiran Ananthpur Bacche, Oct 25 2022
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..3311 (terms n = 1..300 from T. D. Noe)
Sr. Arworn, An algorithm for the number of endomorphisms on paths, Disc. Math., 309 (2009), 94-103 (see p. 95).
Zhicong Lin and Jiang Zeng, On the number of congruence classes of paths, arXiv preprint arXiv:1112.4026 [math.CO], 2011.
M. A. Michels and U. Knauer, The congruence classes of paths and cycles, Discr. Math., 309 (2009), 5352-5359. See p. 5356. [From N. J. A. Sloane, Sep 20 2009]
Joseph Myers, BMO 2008-2009 Round 1 Problem 1-Generalisation
FORMULA
It appears that the limit of a(n)/a(n-1) is decreasing towards 2. - Ben Paul Thurston, 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. - Joseph Myers, Dec 23 2008
a(n) = 2 * Sum_{k=1..n-1} k*A110971(n,k). - N. J. A. Sloane, Sep 20 2009
G.f.: x * (2*(1 - x) - sqrt(1 - 4*x^2)) / (1 - 2*x)^2. - Michael Somos, Mar 17 2014
0 = a(n) * 8*n^2 - a(n+1) * 4*(n^2 - 2*n - 1) - a(n+2) * 2*(n^2 + 3*n - 2) + a(n+3) * (n-1)*(n+2) for n>0. - Michael Somos, Mar 17 2014
0 = a(n) * (16*a(n+1) - 16*a(n+2) + 4*a(n+3)) + a(n+1) * (-16*a(n+1) + 20*a(n+2) - 4*a(n+3)) + a(n+2) * (-4*a(n+2) + a(n+3)) for n>0. - Michael Somos, Mar 17 2014
EXAMPLE
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.
G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 104*x^6 + 252*x^7 + 592*x^8 + ...
MAPLE
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 Paul Thurston, Oct 04 2006
# second Maple program:
a:= proc(n) option remember;
`if`(n<5, [1, 1, 2, 6, 16][n+1], ((2*n^2-6*n-4) *a(n-1)
+(56-32*n+4*n^2) *a(n-2) -8*(n-3)^2 *a(n-3))/ ((n-1)*(n-4)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Nov 23 2012
MATHEMATICA
a[n_] := a[n] = If[n <= 4, n*((n-3)*n+4)/2, ((2*n^2 - 6*n - 4)*a[n-1] + (4*n^2 - 32*n + 56)*a[n-2] - 8*(n-3)^2*a[n-3])/((n-1)*(n-4))]; Table[ a[n], {n, 1, 30}] (* Jean-François Alcover, Nov 10 2015, after Alois P. Heinz *)
PROG
(PARI) x='x+O('x^55); Vec(x*(2*(1-x)-sqrt(1-4*x^2))/(1-2*x)^2) \\ Altug Alkan, Nov 10 2015
(Python)
from math import comb
def A102699(n): return ((n+1<<n-1)-(((n<<1)-1)*comb(n-1, n-1>>1) if n&1 else (n-1)*comb(n-2, n-2>>1)<<2)) if n else 1 # Chai Wah Wu, Oct 28 2024
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Don Rogers (donrogers42(AT)aol.com), Feb 07 2005
EXTENSIONS
More terms from Ben Paul Thurston, Oct 04 2006
a(20) onwards from David Wasserman, Apr 26 2008
Edited by N. J. A. Sloane, Jan 03 2009 and Sep 23 2010
a(0)=1 prepended by Alois P. Heinz, Apr 17 2017
STATUS
approved