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

0, 1, 11, 61, 275, 1141, 4571, 18061, 71075, 279781, 1103531, 4363261, 17292275, 68670421, 273152891, 1087959661, 4337751875, 17308485061, 69105848651, 276038071261, 1102994217875, 4408498475701, 17623550326811, 70462853802061, 281757339138275, 1126747061234341, 4506141224763371

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) counts the number of proper vertex colorings using exactly 4 colors; these are also the number of 4 partitions of the vertices of the 2n vertices. a(n) = 0 for n < 2.

Examples

			a(3) = 11 because K(3,3) has vertices {a1,a2,a3,b1,b2,b3} and there are 11 ways to color properly 6 vertices using all 4 colors.
		

Links

• Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
• Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Crossrefs

Column 4 of A384968.

Cf. A384981.

Programs

Mathematica

Table[2*StirlingS2[n, 3] + StirlingS2[n, 2]^2, {n, 1, 50}]

PARI

a(n) = 2*stirling(n,3,2) + stirling(n,2,2)^2

Formula

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

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

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

From Stefano Spezia, Jun 14 2025: (Start)

a(n) = 2 - 2^(n+2) + 3^n + 4^n.

E.g.f.: exp(x)*(2 - 4*exp(x) + exp(2*x) + exp(3*x)). (End)