A295271 Number of n X 4 0..1 arrays with each 1 horizontally or vertically adjacent to 0, 1 or 4 1s.

13, 98, 811, 6659, 54773, 449827, 3697742, 30386185, 249719021, 2052217315, 16865303569, 138600705864, 1139033988179, 9360690397437, 76927054505407, 632193927094967, 5195430458657358, 42696546916624813, 350884326612255131, 2883601123790880675, 23697711212919539231, 194750068617952556626, 1600474783664067960559, 13152855612946330563815, 108091431705620580695441

Offset: 1

Author

R. H. Hardin, Nov 19 2017

Keywords

• nonn
• easy

Comments

Column 4 of A295275.

Examples

			Some solutions for n=4:
..1..1..0..1....1..0..1..0....0..0..0..1....0..1..0..1....0..1..0..0
..0..0..1..0....0..0..0..1....0..0..0..0....1..0..1..0....1..0..1..0
..1..0..1..0....0..0..0..0....1..0..0..0....0..1..1..1....0..0..0..1
..0..0..0..0....0..0..0..1....0..1..0..1....1..0..1..0....0..1..0..1
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..210
• Robert Israel, Maple-assisted proof of formula
• Index entries for linear recurrences with constant coefficients, signature (4,27,63,14,-110,-43,-45,89,-150,89,-126,72,-30,8,-2,1).

Crossrefs

Cf. A295275.

Programs

Maple

R:= [13, 98, 811, 6659, 54773, 449827, 3697742, 30386185, 249719021, 2052217315, 16865303569, 138600705864, 1139033988179, 9360690397437, 76927054505407, 632193927094967]:
rec:= a(n) = 4*a(n-1) +27*a(n-2) +63*a(n-3) +14*a(n-4) -110*a(n-5) -43*a(n-6) -45*a(n-7) +89*a(n-8) -150*a(n-9) +89*a(n-10) -126*a(n-11) +72*a(n-12) -30*a(n-13) +8*a(n-14) -2*a(n-15) +a(n-16):
f:= gfun:-rectoproc({rec,seq(a(i)=R[i],i=1..16)},a(n),remember):
map(f, [$1..40]); # Robert Israel, Nov 19 2017

Mathematica

a = DifferenceRoot[Function[{a, n},
{-a[n] + 2 a[n+1] - 8 a[n+2] + 30 a[n+3] - 72 a[n+4] + 126 a[n+5] - 89 a[n+6] + 150 a[n+7] - 89 a[n+8] +
   45 a[n+9] + 43 a[n+10] + 110 a[n+11] - 14 a[n+12] - 63 a[n+13] - 27 a[n+14] - 4 a[n+15] + a[n+16] == 0,
   a[1] == 13, a[2] == 98, a[3] == 811, a[4] == 6659,
   a[5] == 54773, a[6] == 449827, a[7] == 3697742, a[8] == 30386185,
   a[9] == 249719021, a[10] == 2052217315, a[11] == 16865303569, a[12] == 138600705864,
   a[13] == 1139033988179, a[14] == 9360690397437, a[15] == 76927054505407, a[16] == 632193927094967}]];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Aug 27 2022, after Robert Israel *)

Formula

Empirical: a(n) = 4*a(n-1) +27*a(n-2) +63*a(n-3) +14*a(n-4) -110*a(n-5) -43*a(n-6) -45*a(n-7) +89*a(n-8) -150*a(n-9) +89*a(n-10) -126*a(n-11) +72*a(n-12) -30*a(n-13) +8*a(n-14) -2*a(n-15) +a(n-16).

From Robert Israel, Nov 19 2017: (Start)

Empirical formula confirmed (see link).

G.f.: (13*x + 46*x^2 + 68*x^3 - 50*x^4 - 116*x^5 - 93*x^6 + 31*x^7 - 28*x^8 - 60*x^9 + 2*x^10 - 73*x^11 + 51*x^12 - 22*x^13 + 7*x^14 - x^15 + x^16) / (1 - 4*x - 27*x^2 - 63*x^3 - 14*x^4 + 110*x^5 + 43*x^6 + 45*x^7 - 89*x^8 + 150*x^9 - 89*x^10 + 126*x^11 - 72*x^12 + 30*x^13 - 8*x^14 + 2*x^15 - x^16).

(End)