login
Triangle read by rows: T(n,k) is the number of graphs with n vertices and treewidth k.
3

%I #40 Jan 01 2024 09:11:16

%S 1,1,1,1,2,1,1,5,4,1,1,9,17,6,1,1,19,72,53,10,1,1,36,323,501,168,14,1,

%T 1,75,1639,5889,4163,557,21,1,1,152,9203,81786,138923,42596,1977,29,1

%N Triangle read by rows: T(n,k) is the number of graphs with n vertices and treewidth k.

%C A graph without edges has treewidth 0, any other forest has treewidth 1, any other series parallel graph has treewidth 2. - _Martin Rubey_, May 10 2023

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000272">The treewidth of a graph</a>.

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

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 5, 4, 1;

%e 1, 9, 17, 6, 1;

%e 1, 19, 72, 53, 10, 1;

%e 1, 36, 323, 501, 168, 14, 1;

%e 1, 75, 1639, 5889, 4163, 557, 21, 1;

%e 1, 152, 9203, 81786, 138923, 42596, 1977, 29, 1;

%e ...

%Y Columns k=2..3 are A362908, A362907.

%Y Partial row sums include A000012, A005195, A000041.

%Y Row sums are A000088.

%Y T(n,n-2) = A000065(n).

%K nonn,tabl,more

%O 1,5

%A _Christian Stump_, Oct 13 2015

%E Corrected and extended by _Martin Rubey_, May 10 2023