Martín Muñoz - cp's OEIS frontend

User: Martín Muñoz

Martín Muñoz has authored 1 sequences.

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

Martín Muñoz, Dec 27 2023

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.

			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;
  ...

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

Row sums give A000142.

cp's OEIS Frontend

User: Martín Muñoz

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs