A384968 -id:A384968 - cp's OEIS frontend

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

Julian Allagan, Jun 14 2025

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.

			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.

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

Column 4 of A384968.

Cf. A384981.

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

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

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)

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

Original entry on oeis.org

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

Julian Allagan, Jun 14 2025

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.

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

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

Column 5 of A384968.

Cf. A008277, A384980.

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula