A181208 Number of n X 4 binary matrices with no two 1's adjacent diagonally or antidiagonally.

16, 64, 484, 2704, 17424, 104976, 652864, 4000000, 24681024, 151782400, 934891776, 5754132736, 35428274176, 218096472064, 1342706197504, 8266039005184, 50888705511424, 313286601609216, 1928696564957184, 11873676328960000

Offset: 1

Author

R. H. Hardin, Oct 10 2010

Keywords

• nonn
• easy

Comments

Column 4 of A181212.

Links

• Robert Israel, Table of n, a(n) for n = 1..1265 (n = 1..325 from R. H. Hardin)
• Robert Israel, Maple-assisted proof of formula
• Index entries for linear recurrences with constant coefficients, signature (6,8,-48,24,32,-16).

Crossrefs

Cf. A181212.

Programs

Maple

f:= gfun:-rectoproc({a(n)=6*a(n-1)+8*a(n-2)-48*a(n-3)+24*a(n-4)+32*a(n-5)-16*a(n-6), a(1)=16, a(2)=64, a(3)=484, a(4)=2704, a(5)=17424, a(6)=104976},a(n),remember):
map(f, [$1..20]); # Robert Israel, Dec 25 2017

Mathematica

RecurrenceTable[{a[n] == 6*a[n-1] + 8*a[n-2] - 48*a[n-3] + 24*a[n-4] + 32*a[n-5] - 16*a[n-6], a[1] == 16, a[2] == 64, a[3] == 484, a[4] == 2704, a[5] == 17424, a[6] == 104976}, a, {n, 1, 20}] (* Jean-François Alcover, Aug 29 2022, after Robert Israel *)
LinearRecurrence[{6,8,-48,24,32,-16},{16,64,484,2704,17424,104976},30] (* Harvey P. Dale, Aug 29 2024 *)

PARI

Vec(4*x*(4 - 8*x - 7*x^2 + 14*x^3 + 4*x^4 - 4*x^5) / ((1 - 8*x + 12*x^2 - 4*x^3)*(1 + 2*x - 4*x^2 - 4*x^3)) + O(x^30)) \\ Colin Barker, Mar 26 2018

Formula

Empirical: a(n) = 6*a(n-1) + 8*a(n-2) - 48*a(n-3) + 24*a(n-4) + 32*a(n-5) - 16*a(n-6).

Formula confirmed by Robert Israel, Dec 25 2017 (see link).

G.f.: 4*x*(4 - 8*x - 7*x^2 + 14*x^3 + 4*x^4 - 4*x^5) / ((1 - 8*x + 12*x^2 - 4*x^3)*(1 + 2*x - 4*x^2 - 4*x^3)). - Colin Barker, Mar 26 2018