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

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

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.

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