A384988 a(n) = Stirling2(n,2)^2 + Stirling2(n,3).

0, 1, 10, 55, 250, 1051, 4270, 17095, 68050, 270451, 1075030, 4276735, 17030650, 67881451, 270777790, 1080817975, 4316294050, 17244046051, 68912400550, 275457464815, 1101251874250, 4403270396251, 17607863991310, 70415790601255, 281616141147250, 1126323450484051

Offset: 1

Author

Julian Allagan, Jun 14 2025

Keywords

• nonn
• easy

Comments

Also, one third of the number of proper vertex colorings of the n-complete tripartite graph using exactly 5 interchangeable colors.

The complete 3-partite graph K(n,n,n) has 3n vertices partitioned into three sets of size n each, with edges between every pair of vertices from different sets. 3*a(n) = 0 for n < 2 because we need at least 2 vertices per partition to create 5 nonempty independent sets.

Examples

			3*a(2) = 3 because K(2,2,2) can be partitioned into 5 nonempty independent sets in exactly 3 ways.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..500
• Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press.
• Eric Weisstein's World of Mathematics, Complete Multipartite Graph.
• Eric Weisstein's World of Mathematics, Stirling Number of the Second Kind.
• Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Crossrefs

Cf. A000392, A000453, A060867, A385432.

Programs

Magma

[(6 - 3*2^(n+1) + 2*3^(n-1) + 4^n)/4: n in [1..30]]; // Vincenzo Librandi, Jul 24 2025

Mathematica

Table[(StirlingS2[n, 3] + StirlingS2[n, 2]^2), {n, 1, 20}]

Formula

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

G.f.: 1/(4*(1 - 4*x)) + 1/(6*(1 - 3*x)) - 3/(2*(1 - 2*x)) + 3/(2*(1 - x)).

a(n) = A385432(n, 5) / 3 = A060867(n-1) + A000392(n).

From Stefano Spezia, Jun 14 2025: (Start)

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

E.g.f.: (exp(x) - 1)^2*(3*exp(2*x) + 8*exp(x) - 5)/12. (End)

a(n) = A000453(n+2) -10*A000453(n). - R. J. Mathar, Jul 20 2025