login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 0
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 29 00:02 EST 2023. Contains 359905 sequences. (Running on oeis4.)