login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 23 21:46 EDT 2024. Contains 374575 sequences. (Running on oeis4.)