A393467 Number of maximum irredundant sets in the n-necklace graph.

6, 4, 4, 75, 24, 330, 16, 1400, 96, 4176, 64, 13200, 384, 34528, 256, 96000, 1536, 235008, 1024, 608000, 6144, 1430016, 4096, 3532800, 24576, 8089600, 16384, 19353600, 98304, 43474944, 65536, 101580800, 393216, 224919552, 262144, 516096000, 1572864, 1129971712, 1048576, 2555904000, 6291456

Offset

0,1

Comments

The sequence has been extended to a(0) using the formula. - Andrew Howroyd, Feb 15 2026

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Eric Weisstein's World of Mathematics, Maximum Irredundant Vertex Set.

Eric Weisstein's World of Mathematics, Necklace Graph.

Index entries for linear recurrences with constant coefficients, signature (0,2,0,8,0,-16,0,-16,0,32).

Formula

From Andrew Howroyd, Feb 15 2026: (Start)

a(2*n) = 4*2^n + 2*(-2)^n; a(2*n+1) = (100*n^2 + 132*n + 41)*2^(n-3) + 9*(2*n + 1)*(-2)^(n-3).

G.f.: (6 + 4*x - 8*x^2 + 67*x^3 - 32*x^4 + 148*x^5 + 32*x^6 + 204*x^7 + 32*x^8)/((1 - 2*x^2)^3*(1 + 2*x^2)^2). (End)

Mathematica

Table[2^((n - 11)/2) (Sqrt[2] (1 + (-1)^n) (n - 1) (25 n - 9 + 9 Cos[3 n Pi/2]) + 32 (-1 + (-1)^n) (-2 + Sin[3 n Pi/2])), {n, 20}]
(* or *)
LinearRecurrence[{0, 2, 0, 8, 0, -16, 0, -16, 0, 32}, {6, 4, 4, 75, 24, 330, 16, 1400, 96, 4176}, 20] (* Eric W. Weisstein, Feb 16 2026 *)
CoefficientList[Series[(-6 - 4 x + 8 x^2 - 67 x^3 + 32 x^4 - 148 x^5 - 32 x^6 - 204 x^7 - 32 x^8)/((-1 + 2 x^2)^3 (1 + 2 x^2)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Feb 16 2026 *)

Prog

(PARI) a(n)=my(m=n\2); if(n%2==0, 4*2^m + 2*(-2)^m, ((100*m^2 + 132*m + 41)*2^m - 9*(2*m + 1)*(-2)^m)/8) \\ Andrew Howroyd, Feb 15 2026

Crossrefs

Cf. A393349, A393463.

Sequence in context: A019174 A019166 A058158 * A249185 A021159 A106332

Adjacent sequences: A393464 A393465 A393466 * A393468 A393469 A393470

Keyword

nonn,easy

Author

Eric W. Weisstein, Feb 15 2026

Extensions

a(0) prepended and a(9) onward from Andrew Howroyd, Feb 15 2026

Status

approved