|
%I #41 Sep 24 2020 04:15:49
%S 0,1,7,2,15,26,3,23,53,63,4,31,80,127,124,5,39,107,191,249,215,6,47,
%T 134,255,374,431,342,7,55,161,319,499,647,685,511,8,63,188,383,624,
%U 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
%N Table read by antidiagonals upwards: T(n,k) = (n - 1)*k^3 - 1, with n > 1 and k > 0.
%C 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.).
%C 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.
%H Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé and Nicolas Trotignon, <a href="https://arxiv.org/abs/2001.01607">(Theta, triangle)-free and (even hole, K4)-free graphs. Part 2 : bounds on treewidth</a>, arXiv:2001.01607 [cs.DM], 2020. See p. 7.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>.
%F O.g.f.: x^2*y*(y*(7 - 2*y + y^2) + x*(1 - y)^3)/((1 - x)^2*(1 - y)^4).
%F 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)).
%F T(n, k) = n*A000578(k) - A001093(k).
%F T(n, n) = A085537(n) - 1 for n > 1.
%F T(n, k) = T(n+1, 1)*T(2, k) + T(n, 1).
%e The table starts at row n = 2 and column k = 1 as:
%e 0 7 26 63 124 215 ...
%e 1 15 53 127 249 431 ...
%e 2 23 80 191 374 647 ...
%e 3 31 107 255 499 863 ...
%e 4 39 134 319 624 1079 ...
%e 5 47 161 383 749 1295 ...
%e ...
%t T[n_,k_]:=(n-1)*k^3-1; Flatten[Table[T[n+1-k,k],{n,2,12},{k,1,n-1}]]
%o (PARI) T(n, k) = (n - 1)*k^3 - 1
%Y Cf. A000578, A001093, A001477 (k = 1), A004771 (k = 2), A068601 (n = 2), A085537, A109129, A123865 (main diagonal), A325543, A325612.
%K nonn,easy,tabl
%O 2,3
%A _Stefano Spezia_, Jul 11 2020
|
