A384981 -id:A384981 - cp's OEIS frontend

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

1, 1, 2, 1, 1, 6, 11, 6, 1, 1, 14, 61, 86, 50, 12, 1, 1, 30, 275, 770, 927, 530, 150, 20, 1, 1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1, 1, 126, 4571, 38626, 134981, 228382, 209428, 110768, 34902, 6580, 721, 42, 1, 1, 254, 18061, 248766, 1367310, 3553564, 4989621, 4093126, 2061782, 655788, 132958, 16996, 1316, 56, 1

Offset: 1

Andrew Howroyd, Jun 18 2025

Permuting the colors does not change the coloring. T(n,k) is the number of ways to partition the vertices into k independent sets.

			Triangle begins (n >= 1, k >= 2):
  1;
  1,  2,    1;
  1,  6,   11,    6,     1;
  1, 14,   61,   86,    50,    12,    1;
  1, 30,  275,  770,   927,   530,  150,   20,   1;
  1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2500 (rows 1..50)
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Vertex Coloring.

Row sums are A001247.
Columns k=2..5 are A000012, A000918, A384980, A384981.
Cf. A008277, A212084, A274310.

T(n,k) = sum(j=1, k-1, stirling(n,j,2)*stirling(n,k-j,2))
for(n=1, 7, print(vector(2*n-1,k,T(n,k+1))))

T(n,k) = Sum_{j=1..k-1} Stirling2(n,j)*Stirling2(n,k-j).

T(n,k) = A274310(2*n-1, k-1).

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

Original entry on oeis.org

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)

cp's OEIS Frontend

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula