|
|
A290710
|
|
Number of irredundant sets in the n-crown graph.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|