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
KEYWORD
nonn,tabl
AUTHOR
David Galvin, Jan 03 2022
STATUS
approved