A231884 Number of maximal 2-independent sets in the 3-dimensional (2, 2, n) grid graph.
0, 4, 4, 20, 32, 80, 180, 408, 940, 2072, 4824, 10792, 24660, 55748, 126760, 287584, 652280, 1481184, 3359900, 7627296, 17305472, 39277688, 89131928, 202276640, 459045772, 1041743020, 2364140452, 5365103100, 12175556108, 27630957644, 62705400664, 142302685268
Offset: 0
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..200
- R. Euler, P. Oleksik, Z. Skupien, Counting Maximal Distance-Independent Sets in Grid Graphs, Discussiones Mathematicae Graph Theory. Volume 33, Issue 3, Pages 531-557, ISSN (Print) 2083-5892, July 2013; see also.
- Index entries for linear recurrences with constant coefficients, signature (0,3,4,4,0,-9,-3).
Programs
-
Mathematica
Join[{0}, LinearRecurrence[{0, 3, 4, 4, 0, -9, -3}, {4, 4, 20, 32, 80, 180, 408}, 31]] (* Jean-François Alcover, Nov 01 2017 *) -
PARI
concat(0, Vec(4*x*(1 + x)*(1 + 2*x^2 - x^3 - 2*x^4 - x^5) / (1 - 3*x^2 - 4*x^3 - 4*x^4 + 9*x^6 + 3*x^7) + O(x^40))) \\ Colin Barker, Oct 04 2017
Formula
Euler et al. give an explicit g.f. and recurrence.
From Colin Barker, Oct 04 2017: (Start)
G.f.: 4*x*(1 + x)*(1 + 2*x^2 - x^3 - 2*x^4 - x^5) / (1 - 3*x^2 - 4*x^3 - 4*x^4 + 9*x^6 + 3*x^7).
a(n) = 3*a(n-2) + 4*a(n-3) + 4*a(n-4) - 9*a(n-6) - 3*a(n-7) for n>7.
(End)
Extensions
Terms a(11) and beyond from Andrew Howroyd, Jun 10 2017