A290710 Number of irredundant sets in the n-crown graph.

24, 77, 178, 373, 724, 1331, 2364, 4127, 7186, 12625, 22558, 41153, 76680, 145607, 280792, 547867, 1078006, 2133461, 4238634, 8442221, 16841500, 33630907, 67199188, 134323703, 268559034, 537014201, 1073907094, 2147673337, 4295184016, 8590181135

Offset

3,1

Comments

From Andrew Howroyd, Aug 11 2017: (Start)

For n > 3 the irredundant sets are:

- 2*(2^n-1): any number of vertices from one side of the graph

- n^2: any two vertices on opposite sides

- n*(n-1)*(n-2): two vertices on one side and one non-opposing on the other

- n*(n-1)*(n-2)*(n-3)/4: two non-opposing vertices from each side

- 1: the empty set

(End)

Links

Vincenzo Librandi, Table of n, a(n) for n = 3..1000

Eric Weisstein's World of Mathematics, Crown Graph

Eric Weisstein's World of Mathematics, Irredundant Set

Index entries for linear recurrences with constant coefficients, signature (7, -20, 30, -25, 11, -2).

Formula

a(n) = 2^(n+1) + n*(n^3 - 2*n^2 + 3*n + 2)/4 - 1 for n > 3. - Andrew Howroyd, Aug 11 2017

a(n) = 7*a(n-1) - 20*a(n-2) + 30*a(n-3) - 25*a(n-4) + 11*a(n-5) - 2*a(n-6) for n > 9.

G.f.: (x^3 (24 - 91 x + 119 x^2 - 53 x^3 - 37 x^4 + 44 x^5 - 12 x^6))/((-1 + x)^5 (-1 + 2 x)).

Mathematica

Table[If[n == 3, 24, 2^(n + 1) + n*(n^3 - 2 n^2 + 3 n + 2)/4 - 1], {n, 3, 20}]
Join[{24}, LinearRecurrence[{7, -20, 30, -25, 11, -2}, {77, 178, 373, 724, 1331, 2364}, 20]]
CoefficientList[Series[(24 - 91 x + 119 x^2 - 53 x^3 - 37 x^4 + 44 x^5 - 12 x^6)/((-1 + x)^5 (-1 + 2 x)), {x, 0, 20}], x]

Prog

(PARI) a(n)=if(n<4, [4, 9, 24][n], 2^(n+1) + n*(n^3 - 2*n^2 + 3*n + 2)/4 - 1); \\ Andrew Howroyd, Aug 11 2017
(Magma) [24] cat [2^(n+1)+n*(n^3-2*n^2+3*n+2)/4-1: n in [4..40]]; // Vincenzo Librandi, Mar 17 2018

Crossrefs

Sequence in context: A214397 A048352 A144459 * A206010 A124140 A206003

Adjacent sequences: A290707 A290708 A290709 * A290711 A290712 A290713

Keyword

nonn

Author

Eric W. Weisstein, Aug 09 2017

Extensions

a(13)-a(32) from Andrew Howroyd, Aug 11 2017

Status

approved