A381451 Triangle read by rows: T(n,k) is the clique covering number of the Johnson graph J(n, k), n >= 2, 0 < k < n.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 9, 9, 5, 1, 1, 6, 12, 14, 12, 6, 1, 1, 7, 16, 25, 25, 16, 7, 1, 1, 8, 20, 40, 46, 40, 20, 8, 1, 1, 9, 25, 56

Offset: 2

Author

Søren Fuglede Jørgensen, Feb 24 2025

Keywords

• nonn
• tabl
• hard
• more

Comments

T(2*k, k) = C(k) = A000108(k), the k-th Catalan number, for k = 1, 2, 4, 6, 8, 16; whether this holds for other values of k is an open question.

Examples

			Triangle begins:
   n\k  1  2  3  4  5  6  7  8  9 10
   2:   1
   3:   1  1
   4:   1  2  1
   5:   1  3  3  1
   6:   1  4  6  4  1
   7:   1  5  9  9  5  1
   8:   1  6 12 14 12  6  1
   9:   1  7 16 25 25 16  7  1
  10:   1  8 20 40 46 40 20  8  1
  11:   1  9 25 56  ?  ? 56 25  9  1
  ...
		

Links

• Søren Fuglede Jørgensen, On the clique covering numbers of Johnson graphs, Des. Codes Cryptogr. (2025); arXiv:2502.15019 [math.CO], 2025.
• Eric Weisstein's World of Mathematics, Clique Covering Number.
• Eric Weisstein's World of Mathematics, Johnson Graph.
• Wikipedia, Johnson graph.

Crossrefs

Cf. A002620 (column 3).

Formula

T(n, k) = T(n, n - k).

T(n, 1) = 1.

T(n, 2) = n - 2.

T(n, 3) = A002620(n-1), for n >= 6.

T(n, k) <= T(n - 1, k - 1) + T(n - 1, k).