

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



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



STATUS

approved



