A318111 Number of maximal 1-intersecting families of 2-sets of [n] = {1,2,...,n}.

1, 1, 1, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160, 1351, 1562, 1794, 2048, 2325, 2626, 2952, 3304, 3683, 4090, 4526, 4992, 5489, 6018, 6580, 7176, 7807, 8474, 9178, 9920, 10701, 11522, 12384, 13288, 14235, 15226

Offset

1,4

Comments

a(n) = C(n,3) + n except for n = 2, 3 because all 1-intersecting families of 2-sets of size n > 3 can be interpreted as graphs with no independent edges. On n > 3 nodes, the only possibilities are triangles (C(n,3) possibilities) and stars (n possibilities, except for n=2,3).

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

From Colin Barker, Aug 31 2018: (Start)

G.f.: x*(1 - 3*x + 3*x^2 + 6*x^3 - 14*x^4 + 11*x^5 - 3*x^6)/(1 - x)^4.

a(n) = n*(8 - 3*n + n^2)/6 for n>3.

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n>7.

(End)

Maple

A318111 := n -> `if`(n<=3, 1, n*(8 - 3*n + n^2)/6):
seq(A318111(n), n=1..30); # Peter Luschny, Sep 05 2018

Mathematica

CoefficientList[Series[x*(1 - 3*x + 3*x^2 + 6*x^3 - 14*x^4 + 11*x^5 - 3*x^6) / (1 - x)^4, {x, 0, 50}], x] (* Stefano Spezia, Aug 31 2018 *)

Prog

(PARI) Vec(x*(1 - 3*x + 3*x^2 + 6*x^3 - 14*x^4 + 11*x^5 - 3*x^6)/(1 - x)^4 + O(x^50)) \\ Colin Barker, Aug 31 2018

Crossrefs

a(n) = A000125(n-1) except for n = 2,3.

Cf. A318112.

Sequence in context: A292949 A072177 A169875 * A240522 A132298 A188558

Adjacent sequences: A318108 A318109 A318110 * A318112 A318113 A318114

Keyword

nonn,easy

Author

Manfred Scheucher and Felix Schroeder, Aug 17 2018

Status

approved