login
A350528
Triangle read by rows: T(n,k) is the number of labeled quasi-threshold 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
OFFSET
1,4
COMMENTS
The family of quasi-threshold 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
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)^(n-j)*Stirling2(n, j)*k*binomial(j, k)*j^(j-k-1) 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
KEYWORD
nonn,tabl
AUTHOR
David Galvin, Jan 03 2022
STATUS
approved