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

Author

Eric W. Weisstein, Aug 09 2017

Keywords

• nonn

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

Programs

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

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]

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

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

Extensions

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