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

Author

Andrew Howroyd, Jun 18 2025

Keywords

• nonn
• tabf

Comments

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

Examples

			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;
  ...
		

Links

• 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.

Crossrefs

Row sums are A001247.

Columns k=2..5 are A000012, A000918, A384980, A384981.

Cf. A008277, A212084, A274310.

Programs

PARI

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))))

Formula

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

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