A385437 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph with a perfect matching removed using exactly k interchangeable colors, for n >= 1 and 2 <= k <= 2n.

1, 2, 4, 1, 1, 10, 20, 9, 1, 1, 18, 92, 146, 80, 16, 1, 1, 35, 355, 1146, 1492, 850, 220, 25, 1, 1, 68, 1336, 7590, 17831, 19740, 11052, 3230, 490, 36, 1, 1, 133, 5026, 47278, 181251, 332039, 320763, 172788, 53417, 9520, 952, 49, 1, 1, 262, 19097, 287126, 1710016, 4809728, 7204912, 6180858, 3177106, 1003940, 196728, 23660, 1680, 64, 1

Offset: 1

Author

Julian Allagan, Jun 28 2025

Keywords

• nonn
• tabf

Comments

Permuting the colors does not change the coloring. T(n,k) is the number of ways to partition the vertex set of the n-complete bipartite graph with a perfect matching removed into k nonempty independent sets, for n >= 1 and 2 <= k <= 2n. T(n,2) = 1 for all n >= 1, corresponding to the partition into the two vertex sets. T(n,2n) = 1 for all n >= 1, corresponding to the partition where each vertex forms its own independent set.

Examples

			Triangle begins (n >= 1, k >= 2):
  n = 1:  [1]
  n = 2:  [2, 4, 1]
  n = 3:  [1, 10, 20, 9, 1]
  n = 4:  [1, 18, 92, 146, 80, 16, 1]
  n = 5:  [1, 35, 355, 1146, 1492, 850, 220, 25, 1]
  n = 6:  [1, 68, 1336, 7590, 17831, 19740, 11052, 3230, 490, 36, 1]
  n = 7:  [1, 133, 5026, 47278, 181251, 332039, 320763, 172788, 53417, 9520, 952, 49, 1]...
For n=2, k=3: T(2,3) = 4. The graph K_{2,2} - M has vertices {a_1, a_2, b_1, b_2} with edges {a_1,b_2}, {a_2,b_1}, {a_2,b_2}, {a_1,b_1} (assuming the perfect matching M = {{a_1,b_1}, {a_2,b_2}} is removed). The 4 ways to partition into 3 independent sets are: {{a_1},{a_2},{b_1,b_2}}, {{a_1},{b_1},{a_2,b_2}}, {{a_2},{b_2},{a_1,b_1}}, {{b_1},{b_2},{a_1,a_2}}.
		

Links

• Eric Weisstein's World of Mathematics, Independent Vertex Set.

Programs

PARI

T(n, k) = sum(s=0, n, binomial(n, s)*sum(j=0, k - n + s, stirling(s, j, 2)*stirling(s, k - n + s - j, 2)));
for(n=1, 10, print(vector(2*n - 1, k, T(n, k + 1))))

Formula

T(n,k) = Sum[Binomial[n, s]*Sum[StirlingS2[s, j]*StirlingS2[s, k - n + s - j], {j, 0, k - n + s}], {s, 0, n}].