login
A336194
Table read by antidiagonals upwards: T(n,k) = (n - 1)*k^3 - 1, with n > 1 and k > 0.
0
0, 1, 7, 2, 15, 26, 3, 23, 53, 63, 4, 31, 80, 127, 124, 5, 39, 107, 191, 249, 215, 6, 47, 134, 255, 374, 431, 342, 7, 55, 161, 319, 499, 647, 685, 511, 8, 63, 188, 383, 624, 863, 1028, 1023, 728, 9, 71, 215, 447, 749, 1079, 1371, 1535, 1457, 999, 10, 79, 242, 511, 874, 1295, 1714, 2047, 2186, 1999, 1330
OFFSET
2,3
COMMENTS
T(n, k) is a sharp upper bound of the tree width of a graph G that does not contain a clique on n vertices nor a minimal separator of size larger than k (see Theorem 2.1 in Pilipczuk et al.).
All the square matrices starting at top left of the table T are singular except for the 2 X 2 submatrix: det([0, 7; 1, 15]) = -7.
LINKS
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé and Nicolas Trotignon, (Theta, triangle)-free and (even hole, K4)-free graphs. Part 2 : bounds on treewidth, arXiv:2001.01607 [cs.DM], 2020. See p. 7.
FORMULA
O.g.f.: x^2*y*(y*(7 - 2*y + y^2) + x*(1 - y)^3)/((1 - x)^2*(1 - y)^4).
E.g.f.: -1 + exp(x) - x + exp(y)*x + exp(y)*(1 + y + 3*y^2 + y^3) + exp(x + y)*(-1 +(-1 + x)*y*(1 + 3*y + y^2)).
T(n, k) = n*A000578(k) - A001093(k).
T(n, n) = A085537(n) - 1 for n > 1.
T(n, k) = T(n+1, 1)*T(2, k) + T(n, 1).
EXAMPLE
The table starts at row n = 2 and column k = 1 as:
0 7 26 63 124 215 ...
1 15 53 127 249 431 ...
2 23 80 191 374 647 ...
3 31 107 255 499 863 ...
4 39 134 319 624 1079 ...
5 47 161 383 749 1295 ...
...
MATHEMATICA
T[n_, k_]:=(n-1)*k^3-1; Flatten[Table[T[n+1-k, k], {n, 2, 12}, {k, 1, n-1}]]
PROG
(PARI) T(n, k) = (n - 1)*k^3 - 1
CROSSREFS
Cf. A000578, A001093, A001477 (k = 1), A004771 (k = 2), A068601 (n = 2), A085537, A109129, A123865 (main diagonal), A325543, A325612.
Sequence in context: A050092 A293452 A030406 * A332209 A239975 A279807
KEYWORD
nonn,easy,tabl
AUTHOR
Stefano Spezia, Jul 11 2020
STATUS
approved