A290709 Number of irredundant sets in the complete tripartite graph K_{n,n,n}.

4, 22, 49, 94, 169, 298, 529, 958, 1777, 3370, 6505, 12718, 25081, 49738, 98977, 197374, 394081, 787402, 1573945, 3146926, 6292777, 12584362, 25167409, 50333374, 100665169, 201328618, 402655369, 805308718, 1610615257, 3221228170, 6442453825, 12884904958

Offset: 1

Author

Eric W. Weisstein, Aug 09 2017

Keywords

• nonn

Comments

When n > 1, the nonempty irredundant sets are those consisting of either any number of vertices from a single partition or otherwise exactly two vertices from different partitions. - Andrew Howroyd, Aug 10 2017

Links

• Eric Weisstein's World of Mathematics, Complete Tripartite Graph
• Eric Weisstein's World of Mathematics, Irredundant Set
• Index entries for linear recurrences with constant coefficients, signature (5, -9, 7, -2).

Crossrefs

Cf. A290707.

Programs

Mathematica

Table[If[n == 1, 4, 3 (2^n + n^2) - 2], {n, 20}]
Join[{4}, LinearRecurrence[{5, -9, 7, -2}, {22, 49, 94, 169}, 20]]
CoefficientList[Series[(4 + 2 x - 25 x^2 + 19 x^3 - 6 x^4)/((-1 + x)^3 (-1 + 2 x)), {x, 0, 20}], x]

PARI

a(n) = if(n==1, 4, 3*(2^n + n^2) - 2); \\ Andrew Howroyd, Aug 10 2017

Formula

a(n) = 3*(2^n + n^2) - 2 for n > 1. - Andrew Howroyd, Aug 10 2017

a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n > 5.

G.f.: (x (4 + 2 x - 25 x^2 + 19 x^3 - 6 x^4))/((-1 + x)^3 (-1 + 2 x)).

Extensions

a(7)-a(32) from Andrew Howroyd, Aug 10 2017