A290056 -id:A290056 - cp's OEIS frontend

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

Eric W. Weisstein, Jul 13 2017

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)

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

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

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

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

a(n) = 1 + binomial(n,3) + (2^(n-2)-n+1)*binomial(n,2) + 5*binomial(n,4); \\ Andrew Howroyd, Jul 18 2017

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

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

a(1)-a(5) and a(21)-a(30) from Andrew Howroyd, Jul 18 2017

A290847 Number of dominating sets in the n-triangular graph.

Original entry on oeis.org

1, 7, 57, 973, 32057, 2079427, 267620753, 68649126489, 35172776136145, 36025104013571583, 73784683970720501897, 302228664636911612364581, 2475873390079769597467385417, 40564787539999607393632514635067, 1329227699017403425105119604848703905

Offset: 2

Andrew Howroyd, Aug 12 2017

nonn

A dominating set on the triangular graph corresponds with an edge cover on the complete graph with optionally one vertex removed.

Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Johnson Graph
Eric Weisstein's World of Mathematics, Triangular Graph

Cf. A000085, A006129, A193154, A287231, A287689, A290056, A290716.

b[n_]:=Sum[(-1)^(n - k)*Binomial[n, k]*2^Binomial[k, 2], {k, 0, n}]; a[n_]:=b[n] + n*b[n - 1]; Table[a[n], {n, 2, 20}] (* Indranil Ghosh, Aug 12 2017 *)

\\ here b(n) is A006129
b(n) = sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2));
a(n) = b(n) + n*b(n-1);

from sympy import binomial
def b(n): return sum((-1)**(n - k)*binomial(n, k)*2**binomial(k, 2) for k in range(n + 1))
def a(n): return b(n) + n*b(n - 1)
print([a(n) for n in range(2, 21)]) # Indranil Ghosh, Aug 13 2017

a(n) = A006129(n) + n * A006129(n-1).

a(n) = 2^binomial(n,2) - Sum_{k=2..n} binomial(n,k)*A006129(n-k).

cp's OEIS Frontend

A289837 Number of cliques in the n-tetrahedral graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A290847 Number of dominating sets in the n-triangular graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula