A057960 Number of base-5 (n+1)-digit numbers starting with a zero and with adjacent digits differing by one or less.
1, 2, 5, 13, 35, 95, 259, 707, 1931, 5275, 14411, 39371, 107563, 293867, 802859, 2193451, 5992619, 16372139, 44729515, 122203307, 333865643, 912137899, 2492007083, 6808289963, 18600594091, 50817768107, 138836724395, 379308985003, 1036291418795, 2831200807595
Offset: 0
Examples
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.
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.
- Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
- 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).
Crossrefs
Programs
-
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 *) -
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
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
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
Comments