

A350528


Triangle read by rows: T(n,k) is the number of labeled quasithreshold graphs on vertex set [n] with k components, for n >= 1 and 1 <= k <= n.


0



1, 1, 1, 4, 3, 1, 23, 19, 6, 1, 181, 155, 55, 10, 1, 1812, 1591, 600, 125, 15, 1, 22037, 19705, 7756, 1750, 245, 21, 1, 315569, 286091, 116214, 27741, 4270, 434, 28, 1, 5201602, 4766823, 1983745, 493794, 81291, 9198, 714, 36, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

The family of quasithreshold graphs is the smallest family of graphs that contains K_1 (a single vertex), and is closed under taking unions and adding dominating vertices (adjacent to all other vertices).


LINKS

Table of n, a(n) for n=1..45.
D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.


FORMULA

T(n,k) = Sum_{j=1..n} (1)^(nj)*Stirling2(n, j)*k*binomial(j, k)*j^(jk1) for n >= 1, 1 <= k <= n.


EXAMPLE

Triangle begins:
1;
1, 1;
4, 3, 1;
23, 19, 6, 1;
181, 155, 55, 10, 1;
1812, 1591, 600, 125, 15, 1;
22037, 19705, 7756, 1750, 245, 21, 1;
315569, 286091; 116214, 27741, 4270, 434, 28, 1;
...


MATHEMATICA

T[n_, k_] := T[n, k] = Sum[((1)^(n  j))*StirlingS2[n, j]*k*Binomial[j, k]*(j^(j  k  1)), {j, 1, n}]; Table[T[n, k], {n, 1, 12}, {k, 1, n}]


CROSSREFS

First column is A058863.
Row sums are A058864.
Cf. A008277.
Sequence in context: A128320 A189507 A348436 * A208057 A298673 A245732
Adjacent sequences: A350525 A350526 A350527 * A350529 A350530 A350531


KEYWORD

nonn,tabl


AUTHOR

David Galvin, Jan 03 2022


STATUS

approved



