A289837 Number of cliques in the n-tetrahedral graph.

1, 1, 2, 16, 76, 261, 757, 2003, 5035, 12286, 29426, 69554, 162670, 376923, 865971, 1973941, 4466853, 10040524, 22430584, 49829116, 110127536, 242254321, 530619937, 1157676711, 2516640751, 5452664426, 11777687182, 25367246038, 54492508610, 116769551831

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

Cf. A055795 (maximal cliques), A287232 (independent vertex sets), A290056 (triangular graph).

Cf. A000665, A125791, A299471, A302374, A302394, A322451, A323293, A323296, A323298.

Sequence in context: A207839 A216424 A212897 * A323297 A034581 A356372

Adjacent sequences: A289834 A289835 A289836 * A289838 A289839 A289840

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