OFFSET
1,1
COMMENTS
Loop-threshold graphs are constructed from either a single unlooped vertex or a single looped vertex by iteratively adding isolated vertices (adjacent to nothing previously added) and looped dominating vertices (looped, and adjacent to everything previously added).
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,n) = n+1 for n >= 1; T(n,1) = Sum_{j=0..n-1} A173018(n,j)*2^j for n >= 2; T(n,k) = binomial(n, k-1)*T(n-k+1,1) for n >= 3, 2 <= k <= n-1.
EXAMPLE
Triangle begins:
2;
3, 3;
13, 9, 4;
75, 52, 18, 5;
541, 375, 130, 30, 6;
4683, 3246, 1125, 260, 45, 7;
47293, 32781, 11361, 2625, 455, 63, 8;
545835, 378344, 131124, 30296, 5250, 728, 84, 9;
7087261, 4912515, 1702548, 393372, 68166, 9450, 1092, 108, 10;
...
MATHEMATICA
eulerian[n_, m_] := eulerian[n, m] =
Sum[((-1)^k)*Binomial[n+1, k]*((m+1-k)^n), {k, 0, m+1}] (* eulerian[n, m] is an Eulerian number, counting the permutations of [n] with m descents *); T[1, 1] = 2; T[n_, 1] := T[n, 1] = Sum[eulerian[n, k]*(2^k), {k, 0, n - 1}]; T[n_, n_] := T[n, n] = n + 1; T[n_, k_] := T[n, k] = Binomial[n, k - 1]*T[n - k + 1, 1]; Table[T[n, k], {n, 1, 12}, {k, 1, n}]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
David Galvin, Jan 03 2022
STATUS
approved