login
Number of connected induced subgraphs on the n-crown graph.
0

%I #6 Mar 03 2024 23:49:40

%S 0,2,6,31,167,806,3588,15233,62973,256504,1036274,4167659,16719843,

%T 66985946,268173264,1073184709,4293787577,17177378732,68714233758,

%U 274866896783,1099488558975,4397998276462,17592085380956,70368534462281,281474540502837,1125899000872736

%N Number of connected induced subgraphs on the n-crown graph.

%C Extended to a(0)-a(2) using the closed form.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CrownGraph.html">Crown 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_06">Index entries for linear recurrences with constant coefficients</a>, signature (11, -47, 101, -116, 68, -16).

%F a(n) = (-1+2^n)^2-(n*(-7+2^(1+n)+n))/2.

%F a(n) = 11*a(n-1)-47*a(n-2)+101*a(n-3)-116*a(n-4)+68*a(n-5)-16*a(n-6).

%F G.f.: (x*(2-16*x+59*x^2-94*x^3+52*x^4))/((1-2*x)^2*(-1+x)^3*(-1+4*x)).

%t Table[(2^n - 1)^2 - 1/2 n (2^(n + 1) + n - 7), {n, 0, 20}]

%t LinearRecurrence[{11, -47, 101, -116, 68, -16}, {2, 6, 31, 167, 806,

%t 3588}, {0, 20}]

%t CoefficientList[Series[(x (2 - 16 x + 59 x^2 - 94 x^3 + 52 x^4))/((1 - 2 x)^2 (-1 + x)^3 (-1 + 4 x)), {x, 0, 20}], x]

%K nonn,easy

%O 0,2

%A _Eric W. Weisstein_, May 26 2017