OFFSET
0,2
COMMENTS
Or, number of three-choice paths along a corridor of width 5 and length n, starting from one side.
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
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, and Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.
Index entries for linear recurrences with constant coefficients, signature (3,0,-2).
FORMULA
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.
a(n) = ceiling((1+sqrt(3))^(n+2)/12). - Mitch Harris, Apr 26 2006
a(n) = floor(a(n-1)*(a(n-1) + 1/2)/a(n-2)). - Franklin T. Adams-Watters and Max Alekseyev, Apr 25 2006
a(n) = floor(a(n-1)*(1+sqrt(3))). - Philippe Deléham, Jul 25 2003
From Paul Barry, Sep 16 2003: (Start)
G.f.: (1-x-x^2)/((1-x)*(1-2*x-2*x^2));
a(n) = 1/3 + (2+sqrt(3))*(1+sqrt(3))^n/6 + (2-sqrt(3))*(1-sqrt(3))^n/6.
Binomial transform of A038754 (with extra leading 1). (End)
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
a(n) = A188866(4,n-1) for n >= 2. - Pontus von Brömssen, Sep 06 2021
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
E.g.f.: exp(x)*(1 + 2*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x))/3. - Stefano Spezia, Mar 02 2024
EXAMPLE
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.
MAPLE
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
MATHEMATICA
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 *)
CoefficientList[Series[(1-x-x^2)/((1-x)*(1-2*x-2*x^2)), {x, 0, 100}], x] (* Vincenzo Librandi, Aug 13 2012 *)
PROG
(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
(Python)
from functools import cache
@cache
def B(n, j):
if not 0 <= j < 5:
return 0
if n == 0:
return j == 0
return B(n - 1, j - 1) + B(n - 1, j) + B(n - 1, j + 1)
def A057960(n):
return sum(B(n, j) for j in range(5))
print([A057960(n) for n in range(30)]) # Pontus von Brömssen, Sep 06 2021
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Henry Bottomley, May 18 2001
EXTENSIONS
This is the result of merging two identical entries submitted by Henry Bottomley and R. H. Hardin. - N. J. A. Sloane, Aug 14 2012
Name clarified by Pontus von Brömssen, Sep 06 2021
STATUS
approved