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,3

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.

Links

Table of n, a(n) for n=1..27.

Julian Allagan, Gabrielle Morgan, and Deonna Sinclair, Bell Numbers and Stirling Numbers of the Mycielskian of Trees, arXiv:2512.06980 [math.CO], 2025. See pp. 1, 8, 10-11.

Eric Weisstein's World of Mathematics, Complete Bipartite Graph.

Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

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)

Example

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.

Mathematica

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

Prog

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

Crossrefs

Column 4 of A384968.

Cf. A384981.

Sequence in context: A023298 A320145 A106992 * A115565 A137410 A268863

Adjacent sequences: A384977 A384978 A384979 * A384981 A384982 A384983

Keyword

nonn,easy

Author

Julian Allagan, Jun 14 2025

Status

approved