OFFSET
1,3
COMMENTS
The incidence graph of a permutation p is the union of the two path graphs 1 - 2 - ... - n and p(1) - p(2) - ... - p(n).
Column k = 0 is all zeros except for n = 1. Column k = 1 is all twos because the only permutations that have an incidence graph with no cycles are the identity permutation and its reverse.
LINKS
S. Ahal and Y. Rabinovich, On complexity of the subpattern problem, SIAM J. Discrete Math., Vol. 22, No. 2 (2008), pp. 629-649.
Wikipedia, Treewidth
EXAMPLE
T(4, 3) is 2 because there are two permutations of size 4 with an incidence graph of treewidth 3. Namely, (2,4,1,3) and (3,1,4,2): these have K_4 as their incidence graphs.
Table begins at row n = 1 and column k = 0 as:
1;
0, 2;
0, 2, 4;
0, 2, 20, 2;
0, 2, 76, 42;
0, 2, 252, 466;
0, 2, 788, 4110, 140;
0, 2, 2374, 32388, 5556;
0, 2, 6938, 236966, 118974;
0, 2, 19778, 1652490, 1952530, 4000;
0, 2, 55222, 11173264, 28078784, 609528;
0, 2, 151462, 74003396, 370327224, 34519516;
...
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Martín Muñoz, Dec 27 2023
STATUS
approved