A290056 Number of cliques in the n-triangular graph.

1, 2, 8, 27, 76, 192, 456, 1045, 2344, 5186, 11364, 24719, 53444, 114948, 246096, 524713, 1114640, 2359942, 4981516, 10486691, 22021196, 46138632, 96470488, 201328317, 419432376, 872417482, 1811941876, 3758099255, 7784631444, 16106130956, 33286000544

Offset: 1

Author

Andrew Howroyd, Jul 19 2017

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Clique
• Eric Weisstein's World of Mathematics, Johnson Graph
• Eric Weisstein's World of Mathematics, Triangular Graph
• Index entries for linear recurrences with constant coefficients, signature (8,-26,44,-41,20,-4).

Crossrefs

Cf. A000125 (maximal cliques), A000085 (independent vertex sets), A289837 (tetrahedral graph).

Programs

Mathematica

Table[1 + Binomial[n, 2] + Binomial[n, 3] + (2^(n - 1) - n) n, {n, 20}] (* Eric W. Weisstein, Jul 19 2017 *)
LinearRecurrence[{8, -26, 44, -41, 20, -4}, {1, 2, 8, 27, 76, 192}, 20] (* Eric W. Weisstein, Jul 19 2017 *)
CoefficientList[Series[(1 - 6 x + 18 x^2 - 29 x^3 + 21 x^4 - 4 x^5)/((-1 + x)^4 (-1 + 2 x)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 19 2017 *)

PARI

a(n) = 1 + binomial(n,2) + (2^(n-1)-n)*n + binomial(n,3);

PARI

Vec(x*(1 - 6*x + 18*x^2 - 29*x^3 + 21*x^4 - 4*x^5) / ((1 - x)^4*(1 - 2*x)^2) + O(x^40)) \\ Colin Barker, Jul 19 2017

Formula

a(n) = 1 + binomial(n,2) + (2^(n-1)-n)*n + binomial(n,3).

a(n) = 8*a(n-1)-26*a(n-2)+44*a(n-3)-41*a(n-4)+20*a(n-5)-4*a(n-6). - Eric W. Weisstein, Jul 29 2017

From Colin Barker, Jul 19 2017: (Start)

G.f.: x*(1 - 6*x + 18*x^2 - 29*x^3 + 21*x^4 - 4*x^5) / ((1 - x)^4*(1 - 2*x)^2).

a(n) = (6 + (-1+3*2^n)*n - 6*n^2 + n^3) / 6.

(End)