OFFSET
1,3
COMMENTS
Here, "cliques" means complete subgraphs (not necessarily the largest).
Sequence extended to a(1) using formula. - Andrew Howroyd, Jul 18 2017
From Gus Wiseman, Jan 11 2019: (Start)
The n-tetrahedral graph has all 3-subsets of {1,...,n} as vertices, and two are connected iff they share two elements. So a(n) is the number of 3-uniform hypergraphs on n labeled vertices where every two edges have two vertices in common. For example, the a(4) = 16 hypergraphs are:
{}
{{1,2,3}}
{{1,2,4}}
{{1,3,4}}
{{2,3,4}}
{{1,2,3},{1,2,4}}
{{1,2,3},{1,3,4}}
{{1,2,3},{2,3,4}}
{{1,2,4},{1,3,4}}
{{1,2,4},{2,3,4}}
{{1,3,4},{2,3,4}}
{{1,2,3},{1,2,4},{1,3,4}}
{{1,2,3},{1,2,4},{2,3,4}}
{{1,2,3},{1,3,4},{2,3,4}}
{{1,2,4},{1,3,4},{2,3,4}}
{{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
The following are non-isomorphic representatives of the 7 unlabeled 3-uniform cliques on 6 vertices, and their multiplicities in the labeled case, which add up to a(6) = 261.
1 X {}
20 X {{1,2,3}}
90 X {{1,3,4},{2,3,4}}
60 X {{1,4,5},{2,4,5},{3,4,5}}
60 X {{1,2,4},{1,3,4},{2,3,4}}
15 X {{1,5,6},{2,5,6},{3,5,6},{4,5,6}}
15 X {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
(End)
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Clique
Eric Weisstein's World of Mathematics, Tetrahedral Graph
Index entries for linear recurrences with constant coefficients, signature (11,-52,138,-225,231,-146,52,-8).
FORMULA
a(n) = 1 + binomial(n,3) + (2^(n-2)-n+1)*binomial(n,2) + 5*binomial(n,4). - Andrew Howroyd, Jul 18 2017
a(n) = 11*a(n-1)-52*a(n-2)+138*a(n-3)-225*a(n-4)+231*a(n-5)-146*a(n-6)+52*a(n-7)-8*a(n-8). - Eric W. Weisstein, Jul 21 2017
From Colin Barker, Jul 19 2017: (Start)
G.f.: x*(1 - 10*x + 43*x^2 - 92*x^3 + 91*x^4 - 25*x^5 - 5*x^6 - 8*x^7) / ((1 - x)^5*(1 - 2*x)^3).
a(n) = (24 - (34+3*2^n)*n + (67+3*2^n)*n^2 - 38*n^3 + 5*n^4) / 24.
(End)
Binomial transform of A323294. - Gus Wiseman, Jan 11 2019
MATHEMATICA
Table[(2^(n - 2) - n + 1) Binomial[n, 2] + Binomial[n, 3] +
5 Binomial[n, 4] + 1, {n, 20}] (* Eric W. Weisstein, Jul 21 2017 *)
LinearRecurrence[{11, -52, 138, -225, 231, -146, 52, -8}, {1, 1, 2, 16, 76, 261, 757, 2003}, 20] (* Eric W. Weisstein, Jul 21 2017 *)
CoefficientList[Series[(1 - 10 x + 43 x^2 - 92 x^3 + 91 x^4 - 25 x^5 - 5 x^6 - 8 x^7)/((-1 + x)^5 (-1 + 2 x)^3), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 21 2017 *)
stableSets[u_, Q_]:=If[Length[u]===0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r===w||Q[r, w]||Q[w, r]], Q]]]];
Table[Length[stableSets[Subsets[Range[n], {3}], Length[Intersection[#1, #2]]<=1&]], {n, 6}] (* Gus Wiseman, Jan 11 2019 *)
PROG
(PARI) a(n) = 1 + binomial(n, 3) + (2^(n-2)-n+1)*binomial(n, 2) + 5*binomial(n, 4); \\ Andrew Howroyd, Jul 18 2017
(PARI) Vec(x*(1 - 10*x + 43*x^2 - 92*x^3 + 91*x^4 - 25*x^5 - 5*x^6 - 8*x^7) / ((1 - x)^5*(1 - 2*x)^3) + O(x^40)) \\ Colin Barker, Jul 19 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Jul 13 2017
EXTENSIONS
a(1)-a(5) and a(21)-a(30) from Andrew Howroyd, Jul 18 2017
STATUS
approved