A078100 1/6 of the number of ways of 3-coloring a 4 X n grid.

4, 27, 187, 1302, 9075, 63267, 441090, 3075255, 21440547, 149482638, 1042187067, 7266087315, 50658875658, 353191693599, 2462438631411, 17168025532662, 119694800484387, 834507453158019, 5818153224352338, 40563936024707079, 282810170576026755

Offset: 1

Author

N. J. A. Sloane, Dec 05 2002

Keywords

• nonn
• easy

Comments

Also the number of 3-colorings of the P_4 X P_n grid graph up to permutation of the colors. - Andrew Howroyd, Jun 26 2017

References

• Michael S. Paterson (Warwick), personal communication.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (9,-15,6).

Crossrefs

Row 4 of (1/2)*A078099.

Row 4 of A207997.

Programs

Magma

I:=[4,27,187]; [n le 3 select I[n] else 9*Self(n-1)-15*Self(n-2)+6*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Feb 13 2016

Maple

a:= n-> (Matrix([[27, 4, 2/3]]). Matrix([[9, 1, 0], [ -15, 0, 1], [6, 0, 0]])^n)[1, 3]: seq(a(n), n=1..30); # Alois P. Heinz, Mar 23 2009

Mathematica

LinearRecurrence[{9, -15, 6}, {4, 27, 187}, 21] (* Jean-François Alcover, Feb 13 2016 *)

Formula

See A078099 for formula.

G.f.: x*(9*x-4-4*x^2) / (6*x^3-15*x^2+9*x-1). - Alois P. Heinz, Mar 23 2009

Extensions

More terms from Alois P. Heinz, Mar 23 2009

Name clarified by Andrew Howroyd, Jun 26 2017