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

1, 1, 3, 3, 1, 1, 9, 30, 45, 30, 9, 1, 1, 21, 165, 598, 1032, 939, 471, 129, 18, 1, 1, 45, 750, 5655, 19653, 36465, 39250, 25560, 10278, 2545, 375, 30, 1, 1, 93, 3153, 46726, 295905, 978588, 1881306, 2232798, 1704405, 858530, 288768, 64743, 9495, 870, 45, 1, 1, 189, 12810, 364875, 3988530, 21976122, 69388462, 134794821, 1

Offset: 1

Author

Julian Allagan, Jun 28 2025

Keywords

• nonn
• tabf
• easy

Comments

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

Examples

			Triangle begins (n >= 1, k >= 3):
  n = 1: [1]
  n = 2: [1, 3, 3, 1]
  n = 3: [1, 9, 30, 45, 30, 9, 1]
  n = 4: [1, 21, 165, 598, 1032, 939, 471, 129, 18, 1]
  n = 5: [1, 45, 750, 5655, 19653, 36465, 39250, 25560, 10278, 2545, 375, 30, 1]
  n = 6: [1, 93, 3153, 46726, 295905, 978588, 1881306, 2232798, 1704405, 858530, 288768, 64743, 9495, 870, 45, 1]...
		

Links

• Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press.
• Eric Weisstein's World of Mathematics, Complete Multipartite Graph.
• Eric Weisstein's World of Mathematics, Stirling Number of the Second Kind.

Crossrefs

Column k=3 is A384988.

Programs

PARI

T(n, k) = sum(j1=1, k-2, sum(j2=1, k-j1-1, my(j3 = k - j1 - j2); if(j3 >= 1, stirling(n, j1, 2)*stirling(n, j2, 2)*stirling(n, j3, 2))));
for(n=1, 8, print(vector(3*n - 2, k, T(n, k + 2))))

Formula

T(n,k)=Sum[StirlingS2[n, j1] * StirlingS2[n, j2] * StirlingS2[n, k - j1 - j2],{j1, 1, k - 2}, {j2, 1, k - j1 - 1}]