A384981 Number of proper vertex colorings of the n-complete bipartite graph using exactly 5 interchangeable colors.

0, 0, 6, 86, 770, 5710, 38626, 248766, 1558290, 9603470, 58604546, 355460446, 2147773810, 12945690030, 77907271266, 468366848126, 2813865797330, 16897768573390, 101444650414786, 608899287739806, 3654318951308850, 21929599650541550, 131592320786851106, 789612753560503486

Offset: 1

Author

Julian Allagan, Jun 14 2025

Keywords

• nonn
• easy

Comments

The complete bipartite graph K(n,n) has 2n vertices partitioned into two sets of size n each, with edges between every pair of vertices from different sets. a(n) = 0 for n < 3 because K(n,n) with n < 3 cannot be partitioned into 5 nonempty independent sets. a(n) counts ways to create exactly 3 additional independent sets beyond the original 2-partite sets by splitting some of the 2-partite sets.

Examples

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

Links

• Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
• Index entries for linear recurrences with constant coefficients, signature (16,-95,260,-324,144).

Crossrefs

Column 5 of A384968.

Cf. A008277, A384980.

Programs

Mathematica

Table[2StirlingS2[n, 4] + 2StirlingS2[n, 3]StirlingS2[n, 2], {n, 1, 30}]

Formula

a(n) = Sum_{j = 1..4} Stirling2(n, j) * Stirling2(n, 5-j).

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

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

E.g.f.: (exp(x) - 1)^3*(2*exp(3*x) + 6*exp(2*x) + 7*exp(x) - 3)/12. - Stefano Spezia, Jun 15 2025