A126358 Number of base 4 n-digit numbers with adjacent digits differing by one or less.

1, 4, 10, 26, 68, 178, 466, 1220, 3194, 8362, 21892, 57314, 150050, 392836, 1028458, 2692538, 7049156, 18454930, 48315634, 126491972, 331160282, 866988874, 2269806340, 5942430146, 15557484098, 40730022148, 106632582346, 279167724890, 730870592324

Offset

0,2

Comments

[Empirical] 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

a(n) is the number of quaternary sequences of length n such that no two adjacent terms differ by exactly 1. - David Nacin, May 31 2017

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Index entries for linear recurrences with constant coefficients, signature (3,-1).

Formula

a(n) = 2*F(2*n+1) = A052995(n+1) for n>0, F(n)=A000045(n) and a(0)=1. - Mircea Merca, Jun 28 2012

G.f.: (1+x-x^2)/(1-3*x+x^2). - Bruno Berselli, Jun 28 2012

From David Nacin, May 31 2017: (Start)

For n>2, a(n) = 3*a(n-1)-a(n-2), a(0)=1, a(1)=4, a(2)=10.

For n>0, a(n) = (1-1/sqrt(5))(3/2-sqrt(5)/2)^n + (1+1/sqrt(5))(3/2+sqrt(5)/2)^n. (End)

Mathematica

Join[{1}, Table[2*Fibonacci[2*n+1], {n, 1, 1001}]] (* Vincenzo Librandi, Jun 28 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))
(Magma) [1] cat [(2*Fibonacci(2*n+1)): n in [1..30]]; // Vincenzo Librandi, Jun 28 2012

Crossrefs

Sequence in context: A277236 A218208 A207095 * A200051 A200663 A200464

Adjacent sequences: A126355 A126356 A126357 * A126359 A126360 A126361

Keyword

nonn,base,easy

Author

R. H. Hardin, Dec 26 2006

Status

approved