A368500 Table read by rows: T(n, k) is the number of permutations of size n whose incidence graph has treewidth k.

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

Table of n, a(n) for n=1..51.

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

Adjacent sequences: A368497 A368498 A368499 * A368501 A368502 A368503

Keyword

nonn,tabf

Author

Martín Muñoz, Dec 27 2023

Status

approved