A291706 Number of connected dominating sets in the n-ladder graph.

3, 9, 24, 56, 136, 328, 792, 1912, 4616, 11144, 26904, 64952, 156808, 378568, 913944, 2206456, 5326856, 12860168, 31047192, 74954552, 180956296, 436867144, 1054690584, 2546248312, 6147187208, 14840622728, 35828432664, 86497488056, 208823408776, 504144305608

Offset: 1

Author

Eric W. Weisstein, Aug 30 2017

Keywords

• nonn
• easy

Links

• Eric Weisstein's World of Mathematics, Connected Dominating Set
• Eric Weisstein's World of Mathematics, Ladder Graph
• Index entries for linear recurrences with constant coefficients, signature (2, 1).

Crossrefs

Row 2 of A291872.

Programs

Mathematica

Table[Piecewise[{{3^n, n == 1 || n == 2}}, 4 LucasL[n - 1, 2]], {n, 20}]
Join[{3, 9}, LinearRecurrence[{2, 1}, {24, 56}, 20]]
CoefficientList[Series[(-3 - 3 x - 3 x^2 + x^3)/(-1 + 2 x + x^2), {x, 0, 20}], x]

Formula

a(n) = 4 lucas(n - 1, 2) for n > 2.

a(n) = 2*a(n-1) + a(n-2) for n > 4.

G.f.: (x (-3 - 3 x - 3 x^2 + x^3))/(-1 + 2 x + x^2).