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

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.

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.

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

n-th row polynomial R(n, x) = Bell(n, x)^2, where Bell(n, x) is the n-th row polynomial of the triangle of Stirling numbers of the second kind A008277. - Peter Bala, Nov 11 2025

Example

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

Maple

A384968 := proc (n, k) local j;
with(combinat):
   add(Stirling2(n, j)*Stirling2(n, k-j), j = 1..k-1);
end proc:
for n from 1 to 10 do
   seq(A384968(n, k), k = 2..2*n);
end do; # Peter Bala, Nov 11 2025

Prog

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

Crossrefs

Row sums are A001247.

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

Cf. A008277, A212084, A274310.

Sequence in context: A172107 A349226 A165891 * A039763 A094262 A123554

Adjacent sequences: A384965 A384966 A384967 * A384969 A384970 A384971

Keyword

nonn,tabf,easy

Author

Andrew Howroyd, Jun 18 2025

Status

approved