A132732 Row sums of triangle A132731.

1, 2, 4, 10, 24, 54, 116, 242, 496, 1006, 2028, 4074, 8168, 16358, 32740, 65506, 131040, 262110, 524252, 1048538, 2097112, 4194262, 8388564, 16777170, 33554384, 67108814, 134217676, 268435402, 536870856, 1073741766, 2147483588, 4294967234, 8589934528

Offset: 0

Author

Gary W. Adamson, Aug 26 2007

Keywords

• nonn
• easy

Comments

a(n) is the number of connected induced subgraphs in the (n+1)-path complement graph. - Eric W. Weisstein, Apr 11 2018

Examples

			a(3) = 10 = sum of row 3 terms of triangle A132731: (1 + 4 + 4 + 1).
a(3) = 10 = (1, 3, 3, 1) dot (1, 1, 1, 3) = (1 + 3 + 3 + 3).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, Connected Graph
• Eric Weisstein's World of Mathematics, Path Complement Graph
• Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

Cf. A132731.

Programs

Magma

[1] cat [2*(2^n -n): n in [1..30]]; // G. C. Greubel, Feb 14 2021

Mathematica

Join[{1}, Table[2 (2^n - n), {n, 20}]] (* or *)
Join[{1}, LinearRecurrence[{4, -5, 2}, {2, 4, 10}, 20]] (* or *)
CoefficientList[Series[(1 -2x +x^2 +2x^3)/((1-x)^2 (1-2x)), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 11 2018 *)

PARI

a(n) = if(n==0, 1, 2*(2^n -n)); \\ Altug Alkan, Apr 12 2018

Sage

[1]+[2*(2^n -n) for n in (1..30)] # G. C. Greubel, Feb 14 2021

Formula

Binomial transform of [1, 1, 1, 3, 1, 3, 1, 3, 1, ... (3,1 repeated)].

a(n) = 2*(2^n-n) = 2*A000325(n), n>0. - R. J. Mathar, Sep 16 2017

G.f.: (1 - 2*x + x^2 + 2*x^3)/((1-x)^2 * (1-2*x)). - Eric W. Weisstein, Apr 11 2018

E.g.f.: -1 - 2*x*exp(x) + 2*exp(2*x). - G. C. Greubel, Feb 14 2021