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.

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

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

Adjacent sequences: A350525 A350526 A350527 * A350529 A350530 A350531

Keyword

nonn,tabl

Author

David Galvin, Jan 03 2022

Status

approved