|
%I #80 Mar 02 2024 13:14:19
%S 1,2,5,13,35,95,259,707,1931,5275,14411,39371,107563,293867,802859,
%T 2193451,5992619,16372139,44729515,122203307,333865643,912137899,
%U 2492007083,6808289963,18600594091,50817768107,138836724395,379308985003,1036291418795,2831200807595
%N Number of base-5 (n+1)-digit numbers starting with a zero and with adjacent digits differing by one or less.
%C Or, number of three-choice paths along a corridor of width 5 and length n, starting from one side.
%C If b(n) is the number of three-choice paths along a corridor of width 5 and length n, starting from any of the five positions at the beginning of the corridor, then b(n) = a(n+2) for n >= 0. - _Pontus von Brömssen_, Sep 06 2021
%H Vincenzo Librandi, <a href="/A057960/b057960.txt">Table of n, a(n) for n = 0..1000</a>
%H Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1803.06706">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, arXiv:1803.06706 [math.CO], 2018.
%H Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, and Helmut Prodinger, <a href="http://arxiv.org/abs/0809.0551">Smooth words and Chebyshev polynomials</a>, arXiv:0809.0551v1 [math.CO], 2008.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-2).
%F a(n) = Sum_{0 <= i <= 6} b(n, i) where b(n, 0) = b(n, 6) = 0, b(0, 1) = 1, b(0, n) = 0 if n <> 1 and b(n+1, i) = b(n, i-1) + b(n, i) + b(n, i+1) if 1 <= i <= 5.
%F a(n) = 3*a(n-1) - 2*a(n-3) = 2*A052948(n) - A052948(n-2).
%F a(n) = ceiling((1+sqrt(3))^(n+2)/12). - _Mitch Harris_, Apr 26 2006
%F a(n) = floor(a(n-1)*(a(n-1) + 1/2)/a(n-2)). - _Franklin T. Adams-Watters_ and _Max Alekseyev_, Apr 25 2006
%F a(n) = floor(a(n-1)*(1+sqrt(3))). - _Philippe Deléham_, Jul 25 2003
%F From _Paul Barry_, Sep 16 2003: (Start)
%F G.f.: (1-x-x^2)/((1-x)*(1-2*x-2*x^2));
%F a(n) = 1/3 + (2+sqrt(3))*(1+sqrt(3))^n/6 + (2-sqrt(3))*(1-sqrt(3))^n/6.
%F Binomial transform of A038754 (with extra leading 1). (End)
%F More generally, it appears that a(base,n) = a(base-1,n) + 3^(n-1) for base >= n; a(base,n) = a(base-1,n) + 3^(n-1)-2 when base = n-1. - _R. H. Hardin_, Dec 26 2006
%F a(n) = A188866(4,n-1) for n >= 2. - _Pontus von Brömssen_, Sep 06 2021
%F a(n) = 2*a(n-1) + 2*a(n-2) - 1 for n >= 2, a(0) = 1, a(1) = 2. - _Philippe Deléham_, Mar 01 2024
%F E.g.f.: exp(x)*(1 + 2*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x))/3. - _Stefano Spezia_, Mar 02 2024
%e a(6) = 259 since a(5) = 21 + 30 + 25 + 14 + 5 so a(6) = (21+30) + (21 + 30 + 25) + (30+25+14) + (25+14+5) + (14+5) = 51 + 76 + 69 + 44 + 19.
%p with(combstruct): ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), b): ZL1:=Prod(begin_blockP, Z, end_blockP): ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL1, ZL2, ZL3), b=ZL3], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n+2), n=0..28); # _Zerinvary Lajos_, Mar 08 2008
%t Join[{a=1,b=2},Table[c=(a+b)*2-1;a=b;b=c,{n,0,50}]] (* _Vladimir Joseph Stephan Orlovsky_, Nov 22 2010 *)
%t CoefficientList[Series[(1-x-x^2)/((1-x)*(1-2*x-2*x^2)),{x,0,100}],x] (* _Vincenzo Librandi_, Aug 13 2012 *)
%o (S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-2](($[i]`-$[i+1]`>1)+($[i+1]`-$[i]`>1)) # _R. H. Hardin_, Dec 26 2006
%o (Python)
%o from functools import cache
%o @cache
%o def B(n, j):
%o if not 0 <= j < 5:
%o return 0
%o if n == 0:
%o return j == 0
%o return B(n - 1, j - 1) + B(n - 1, j) + B(n - 1, j + 1)
%o def A057960(n):
%o return sum(B(n, j) for j in range(5))
%o print([A057960(n) for n in range(30)]) # _Pontus von Brömssen_, Sep 06 2021
%Y The "three-choice" comes in the recurrence b(n+1, i) = b(n, i-1) + b(n, i) + b(n, i+1) if 1 <= i <= 5. Narrower corridors produce A000012, A000079, A000129, A001519. An infinitely wide corridor (i.e., just one wall) would produce A005773. Two-choice corridors are A000124, A000125, A000127.
%Y Cf. A038754, A052948, A155020 (first differences), A188866.
%K nonn,base,easy
%O 0,2
%A _Henry Bottomley_, May 18 2001
%E This is the result of merging two identical entries submitted by _Henry Bottomley_ and _R. H. Hardin_. - _N. J. A. Sloane_, Aug 14 2012
%E Name clarified by _Pontus von Brömssen_, Sep 06 2021
|
