A368500 - OEIS

%I #15 Jan 01 2024 09:12:35

%S 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,

%T 32388,5556,0,2,6938,236966,118974,0,2,19778,1652490,1952530,4000,0,2,

%U 55222,11173264,28078784,609528,0,2,151462,74003396,370327224,34519516

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

%C 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).

%C 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.

%H S. Ahal and Y. Rabinovich, <a href="https://doi.org/10.1137/S0895480104444776">On complexity of the subpattern problem</a>, SIAM J. Discrete Math., Vol. 22, No. 2 (2008), pp. 629-649.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Treewidth">Treewidth</a>

%e 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.

%e Table begins at row n = 1 and column k = 0 as:

%e   1;

%e   0,      2;

%e   0,      2,       4;

%e   0,      2,      20,        2;

%e   0,      2,      76,       42;

%e   0,      2,     252,      466;

%e   0,      2,     788,     4110,       140;

%e   0,      2,    2374,    32388,      5556;

%e   0,      2,    6938,   236966,    118974;

%e   0,      2,   19778,  1652490,   1952530,     4000;

%e   0,      2,   55222, 11173264,  28078784,   609528;

%e   0,      2,  151462, 74003396, 370327224, 34519516;

%e   ...

%Y Row sums give A000142.

%K nonn,tabf

%O 1,3

%A _Martín Muñoz_, Dec 27 2023