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.

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

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,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

Adjacent sequences: A350528 A350529 A350530 * A350532 A350533 A350534

Keyword

nonn,tabl

Author

David Galvin, Jan 03 2022

Status

approved