A179070 a(1)=a(2)=a(3)=1, a(4)=3; thereafter a(n) = a(n-1) + a(n-3).

1, 1, 1, 3, 4, 5, 8, 12, 17, 25, 37, 54, 79, 116, 170, 249, 365, 535, 784, 1149, 1684, 2468, 3617, 5301, 7769, 11386, 16687, 24456, 35842, 52529, 76985, 112827, 165356, 242341, 355168, 520524, 762865, 1118033, 1638557, 2401422, 3519455, 5158012, 7559434

Offset: 1

Author

Mark Dols, Jun 27 2010

Keywords

• easy
• nonn

Comments

Also (essentially), coordination sequence for (2,4,infinity) tiling of hyperbolic plane. - N. J. A. Sloane, Dec 29 2015

Column sums of shifted (1,2) Pascal array:

1 1 1 1 1 1 1 1 1

......2 3 4 5 6 7

............2 5 9

.................

----------------- +

1 1 1 3 4 5 8 ...

a(n+1) is the number of multus bitstrings of length n with no runs of 2 0's. - Steven Finch, Mar 25 2020

From Areebah Mahdia and Greg Dresden, Jun 13 2020: (Start)

For n >= 5, a(n) gives the number of ways to tile the following board of length n-3 with squares and trominos:

.

|||

|||_ _ _

|||_|||_|_| ... . (End)

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
• J. W. Cannon, P. Wagreich, Growth functions of surface groups, Mathematische Annalen, 1992, Volume 293, pp. 239-257. See Prop. 3.1.
• Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
• Index entries for linear recurrences with constant coefficients, signature (1,0,1).

Crossrefs

Cf. A000930, A029635, A097333, A214626.

Coordination sequences for triangular tilings of hyperbolic space: A001630, A007283, A054886, A078042, A096231, A163876, A179070, A265057, A265058, A265059, A265060, A265061, A265062, A265063, A265064, A265065, A265066, A265067, A265068, A265069, A265070, A265071, A265072, A265073, A265074, A265075, A265076, A265077.

Programs

Haskell

a179070 n = a179070_list !! (n-1)
a179070_list = 1 : zs where zs = 1 : 1 : 3 : zipWith (+) zs (drop 2 zs)
-- Reinhard Zumkeller, Jul 23 2012

Mathematica

Join[{1}, LinearRecurrence[{1, 0, 1}, {1, 1, 3}, 80]] (* Vladimir Joseph Stephan Orlovsky, Feb 15 2012 *)

PARI

a(n)=([0,1,0; 0,0,1; 1,0,1]^(n-1)*[1;1;1])[1,1] \\ Charles R Greathouse IV, Apr 08 2016

Formula

a(n) = A000930(n-1) + A000930(n-4).

G.f.: x - x^2*(1+2*x^2) / ( -1+x+x^3 ). - R. J. Mathar, Oct 30 2011

a(n) = A000930(n-2)+2*A000930(n-4) for n>3. - R. J. Mathar, May 19 2024

Extensions

Simpler definition from N. J. A. Sloane, Aug 29 2013