login
Row sums of triangle A132731.
4

%I #27 Mar 06 2022 00:20:59

%S 1,2,4,10,24,54,116,242,496,1006,2028,4074,8168,16358,32740,65506,

%T 131040,262110,524252,1048538,2097112,4194262,8388564,16777170,

%U 33554384,67108814,134217676,268435402,536870856,1073741766,2147483588,4294967234,8589934528

%N Row sums of triangle A132731.

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

%H G. C. Greubel, <a href="/A132732/b132732.txt">Table of n, a(n) for n = 0..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathComplementGraph.html">Path Complement Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).

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

%F a(n) = 2*(2^n-n) = 2*A000325(n), n>0. - _R. J. Mathar_, Sep 16 2017

%F G.f.: (1 - 2*x + x^2 + 2*x^3)/((1-x)^2 * (1-2*x)). - _Eric W. Weisstein_, Apr 11 2018

%F E.g.f.: -1 - 2*x*exp(x) + 2*exp(2*x). - _G. C. Greubel_, Feb 14 2021

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

%e a(3) = 10 = (1, 3, 3, 1) dot (1, 1, 1, 3) = (1 + 3 + 3 + 3).

%t Join[{1}, Table[2 (2^n - n), {n, 20}]] (* or *)

%t Join[{1}, LinearRecurrence[{4, -5, 2}, {2, 4, 10}, 20]] (* or *)

%t CoefficientList[Series[(1 -2x +x^2 +2x^3)/((1-x)^2 (1-2x)), {x, 0, 20}], x] (* _Eric W. Weisstein_, Apr 11 2018 *)

%o (PARI) a(n) = if(n==0, 1, 2*(2^n -n)); \\ _Altug Alkan_, Apr 12 2018

%o (Sage) [1]+[2*(2^n -n) for n in (1..30)] # _G. C. Greubel_, Feb 14 2021

%o (Magma) [1] cat [2*(2^n -n): n in [1..30]]; // _G. C. Greubel_, Feb 14 2021

%Y Cf. A132731.

%K nonn,easy

%O 0,2

%A _Gary W. Adamson_, Aug 26 2007