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,2

Comments

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

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).

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

Example

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).

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 *)

Prog

(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
(Magma) [1] cat [2*(2^n -n): n in [1..30]]; // G. C. Greubel, Feb 14 2021

Crossrefs

Cf. A132731.

Sequence in context: A018114 A356695 A089484 * A275447 A095214 A002525

Adjacent sequences: A132729 A132730 A132731 * A132733 A132734 A132735

Keyword

nonn,easy

Author

Gary W. Adamson, Aug 26 2007

Status

approved