|
%I #54 Nov 13 2022 12:29:44
%S 1,1,2,6,16,42,104,252,592,1370,3112,6996,15536,34244,74832,162616,
%T 351136,754938,1615208,3443940,7314928,15493676,32714992,68918856,
%U 144815456,303703972,635554064,1327816392,2769049312,5766417480,11989472672,24897569648
%N Number of strings of length n, using as symbols numbers from the set {1, 2, ..., n}, in which consecutive symbols differ by exactly 1.
%C 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.
%C Number of endomorphisms of a path P_n. - _N. J. A. Sloane_, Sep 20 2009
%C 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
%H Alois P. Heinz, <a href="/A102699/b102699.txt">Table of n, a(n) for n = 0..3311</a> (terms n = 1..300 from T. D. Noe)
%H Sr. Arworn, <a href="http://dx.doi.org/10.1016/j.disc.2007.12.049">An algorithm for the number of endomorphisms on paths</a>, Disc. Math., 309 (2009), 94-103 (see p. 95).
%H Zhicong Lin and Jiang Zeng, <a href="http://arxiv.org/abs/1112.4026">On the number of congruence classes of paths</a>, arXiv preprint arXiv:1112.4026 [math.CO], 2011.
%H M. A. Michels and U. Knauer, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.022">The congruence classes of paths and cycles</a>, Discr. Math., 309 (2009), 5352-5359. See p. 5356. [From _N. J. A. Sloane_, Sep 20 2009]
%H Joseph Myers, <a href="http://www.polyomino.org.uk/publications/2008/bmo1-2009-q1.pdf">BMO 2008-2009 Round 1 Problem 1-Generalisation</a>
%F It appears that the limit of a(n)/a(n-1) is decreasing towards 2. - _Ben Paul Thurston_, Oct 04 2006
%F 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
%F a(n) = 2 * Sum_{k=1..n-1} k*A110971(n,k). - _N. J. A. Sloane_, Sep 20 2009
%F G.f.: x * (2*(1 - x) - sqrt(1 - 4*x^2)) / (1 - 2*x)^2. - _Michael Somos_, Mar 17 2014
%F 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
%F 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
%e 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.
%e G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 104*x^6 + 252*x^7 + 592*x^8 + ...
%p 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
%p # second Maple program:
%p a:= proc(n) option remember;
%p `if`(n<5, [1, 1, 2, 6, 16][n+1], ((2*n^2-6*n-4) *a(n-1)
%p +(56-32*n+4*n^2) *a(n-2) -8*(n-3)^2 *a(n-3))/ ((n-1)*(n-4)))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 23 2012
%t 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_ *)
%o (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
%Y Cf. A110971, A152086.
%Y Main diagonal of A220062. - _Alois P. Heinz_, Dec 03 2012
%K nonn
%O 0,3
%A Don Rogers (donrogers42(AT)aol.com), Feb 07 2005
%E More terms from _Ben Paul Thurston_, Oct 04 2006
%E a(20) onwards from _David Wasserman_, Apr 26 2008
%E Edited by _N. J. A. Sloane_, Jan 03 2009 and Sep 23 2010
%E a(0)=1 prepended by _Alois P. Heinz_, Apr 17 2017
|
