|
%I #21 Jan 12 2019 20:48:38
%S 1,1,2,16,76,261,757,2003,5035,12286,29426,69554,162670,376923,865971,
%T 1973941,4466853,10040524,22430584,49829116,110127536,242254321,
%U 530619937,1157676711,2516640751,5452664426,11777687182,25367246038,54492508610,116769551831
%N Number of cliques in the n-tetrahedral graph.
%C Here, "cliques" means complete subgraphs (not necessarily the largest).
%C Sequence extended to a(1) using formula. - _Andrew Howroyd_, Jul 18 2017
%C From _Gus Wiseman_, Jan 11 2019: (Start)
%C 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:
%C {}
%C {{1,2,3}}
%C {{1,2,4}}
%C {{1,3,4}}
%C {{2,3,4}}
%C {{1,2,3},{1,2,4}}
%C {{1,2,3},{1,3,4}}
%C {{1,2,3},{2,3,4}}
%C {{1,2,4},{1,3,4}}
%C {{1,2,4},{2,3,4}}
%C {{1,3,4},{2,3,4}}
%C {{1,2,3},{1,2,4},{1,3,4}}
%C {{1,2,3},{1,2,4},{2,3,4}}
%C {{1,2,3},{1,3,4},{2,3,4}}
%C {{1,2,4},{1,3,4},{2,3,4}}
%C {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
%C 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.
%C 1 X {}
%C 20 X {{1,2,3}}
%C 90 X {{1,3,4},{2,3,4}}
%C 60 X {{1,4,5},{2,4,5},{3,4,5}}
%C 60 X {{1,2,4},{1,3,4},{2,3,4}}
%C 15 X {{1,5,6},{2,5,6},{3,5,6},{4,5,6}}
%C 15 X {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
%C (End)
%H Andrew Howroyd, <a href="/A289837/b289837.txt">Table of n, a(n) for n = 1..200</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Clique.html">Clique</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TetrahedralGraph.html">Tetrahedral Graph</a>
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (11,-52,138,-225,231,-146,52,-8).
%F a(n) = 1 + binomial(n,3) + (2^(n-2)-n+1)*binomial(n,2) + 5*binomial(n,4). - _Andrew Howroyd_, Jul 18 2017
%F 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
%F From _Colin Barker_, Jul 19 2017: (Start)
%F 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).
%F a(n) = (24 - (34+3*2^n)*n + (67+3*2^n)*n^2 - 38*n^3 + 5*n^4) / 24.
%F (End)
%F Binomial transform of A323294. - _Gus Wiseman_, Jan 11 2019
%t Table[(2^(n - 2) - n + 1) Binomial[n, 2] + Binomial[n, 3] +
%t 5 Binomial[n, 4] + 1, {n, 20}] (* _Eric W. Weisstein_, Jul 21 2017 *)
%t LinearRecurrence[{11, -52, 138, -225, 231, -146, 52, -8}, {1, 1, 2, 16, 76, 261, 757, 2003}, 20] (* _Eric W. Weisstein_, Jul 21 2017 *)
%t 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 *)
%t 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]]]];
%t Table[Length[stableSets[Subsets[Range[n],{3}],Length[Intersection[#1,#2]]<=1&]],{n,6}] (* _Gus Wiseman_, Jan 11 2019 *)
%o (PARI) a(n) = 1 + binomial(n,3) + (2^(n-2)-n+1)*binomial(n,2) + 5*binomial(n,4); \\ _Andrew Howroyd_, Jul 18 2017
%o (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
%Y Cf. A055795 (maximal cliques), A287232 (independent vertex sets), A290056 (triangular graph).
%Y Cf. A000665, A125791, A299471, A302374, A302394, A322451, A323293, A323296, A323298.
%K nonn,easy
%O 1,3
%A _Eric W. Weisstein_, Jul 13 2017
%E a(1)-a(5) and a(21)-a(30) from _Andrew Howroyd_, Jul 18 2017
|
