A183712 1/20 of the number of (n+1) X 3 0..4 arrays with every 2 X 2 subblock strictly increasing clockwise or counterclockwise with one decrease.

5, 17, 54, 174, 559, 1797, 5776, 18566, 59677, 191821, 616574, 1981866, 6370351, 20476345, 65817520, 211558554, 680016837, 2185791545, 7025832918, 22583273462, 72589861759, 233327025821, 749987665760, 2410700161342, 7748761123965, 24906995867477

Offset

1,1

Comments

Column 2 of A183719. [Corrected by M. F. Hasler, Oct 07 2014]

This sequence counts closed walks of length (n+2) at the vertex of a triangle, to which a loop has been added to one of the remaining vertices and two loops has been added to the third vertex. - David Neil McGrath, Sep 04 2014

Links

R. H. Hardin, Table of n, a(n) for n = 1..200

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

Formula

a(n) = 3*a(n-1) + a(n-2) - a(n-3).

The top left element of A^(n+2) where A=(0,1,1;1,1,1;1,1,2). - David Neil McGrath, Sep 04 2014

a(n) ~ c*k^n where k = 1.629316... is the largest root of x^3 - 3x^2 - x + 1 and c = 1.6293... is conjecturally the largest root of 148x^3 - 296x^2 + 90x - 1. - Charles R Greathouse IV, Sep 15 2014

G.f.: x*(5+2*x-2*x^2) / (1-3*x-x^2+x^3). - Colin Barker, Mar 16 2016

Example

Some solutions for 5 X 3:
..0..1..4....1..2..0....4..0..4....4..3..4....4..0..4....1..4..0....3..4..2
..3..2..3....0..3..4....2..1..3....0..2..0....3..2..3....2..3..1....1..0..1
..4..1..0....1..2..1....4..0..4....4..3..4....0..1..0....0..4..0....2..4..3
..3..2..3....0..3..4....3..2..3....0..2..1....4..2..3....1..3..1....1..0..1
..4..0..4....1..2..1....4..1..0....4..3..0....0..1..0....0..4..0....2..3..2
...
...R..L.......R..L.......R..L.......L..R.......R..L.......L..R.......R..L...
...L..R.......L..R.......L..R.......R..L.......L..R.......R..L.......L..R...
...R..L.......R..L.......R..L.......L..R.......R..L.......L..R.......R..L...
...L..R.......L..R.......L..R.......R..L.......L..R.......R..L.......L..R...

Prog

(PARI) a(n)=([0, 1, 1; 1, 1, 1; 1, 1, 2]^(n+2))[1, 1] \\ Charles R Greathouse IV, Sep 15 2014
(PARI) Vec(x*(5+2*x-2*x^2)/(1-3*x-x^2+x^3) + O(x^50)) \\ Colin Barker, Mar 16 2016

Crossrefs

Cf. A183727, A183719.

Sequence in context: A034346 A055419 A027091 * A244235 A081495 A191645

Adjacent sequences: A183709 A183710 A183711 * A183713 A183714 A183715

Keyword

nonn,walk,easy

Author

R. H. Hardin, Jan 06 2011

Status

approved