login
A368500
Table read by rows: T(n, k) is the number of permutations of size n whose incidence graph has treewidth k.
0
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
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
Row sums give A000142.
Sequence in context: A332760 A199335 A141660 * A209699 A115273 A194759
KEYWORD
nonn,tabf
AUTHOR
Martín Muñoz, Dec 27 2023
STATUS
approved