login
A350531
Triangle read by rows: T(n,k) is the number of labeled loop-threshold graphs on vertex set [n] with k components, for n >= 1 and 1 <= k <= n.
1
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
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
Row sums are A000629.
Except at n = 1, first column is A000670.
Essentially the same as A154921 --- in A350531 (this triangle), replace the last nonzero entry in row m (this entry is m+1) with the two entries m, 1 to get A154921.
Cf. A173018.
Sequence in context: A127003 A211673 A184178 * A039793 A106243 A109203
KEYWORD
nonn,tabl
AUTHOR
David Galvin, Jan 03 2022
STATUS
approved