A348436 Triangle read by rows. T(n,k) is the number of labeled threshold graphs on n vertices with k components, for 1 <= k <= n.

1, 1, 1, 4, 3, 1, 23, 16, 6, 1, 166, 115, 40, 10, 1, 1437, 996, 345, 80, 15, 1, 14512, 10059, 3486, 805, 140, 21, 1, 167491, 116096, 40236, 9296, 1610, 224, 28, 1, 2174746, 1507419, 522432, 120708, 20916, 2898, 336, 36, 1, 31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1

Offset

1,4

Comments

The class of threshold graphs is the smallest class of graphs that includes K1 and is closed under adding isolated vertices and dominating vertices.

Links

Table of n, a(n) for n=1..55.

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.

Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.

Formula

T(1,1) = 1; for n >= 2, T(n,1) = A005840(n)/2; for n >= 3 and 2 <= k <= n-1, T(n,k) = binomial(n,k-1)*T(n-k+1,1); and for n >= 2, T(n,n)=1.

T(n, k) = binomial(n, k-1)*A053525(n - k + 1) if k != n, otherwise 1. - Peter Luschny, Oct 24 2021

Example

Triangle begins:
         1;
         1,        1;
         4,        3,       1;
        23,       16,       6,       1;
       166,      115,      40,      10,      1;
      1437,      996,     345,      80,     15,     1;
     14512,    10059,    3486,     805,    140,    21,    1;
    167491,   116096,   40236,    9296,   1610,   224,   28,   1;
   2174746,  1507419,  522432,  120708,  20916,  2898,  336,  36,  1;
  31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1;
...

Maple

T := (n, k) -> `if`(n = k, 1, binomial(n, k-1)*A053525(n-k+1)):
for n from 1 to 10 do seq(T(n, k), k=1..n) od; # Peter Luschny, Oct 24 2021

Mathematica

eulerian[0, 0] := 1; eulerian[n_, m_] := eulerian[n, m] =
Sum[((-1)^k)*Binomial[n + 1, k]*((m + 1 - k)^n), {k, 0, m + 1}];
(* t[n] counts the labeled threshold graphs on n vertices *)
t[0] = 1; t[1] = 1;
t[n_] := t[n] = Sum[(n - k)*eulerian[n - 1, k - 1]*(2^k), {k, 1, n - 1}];
T[1, 1] := 1; T[n_, 1] := T[n, 1] = (1/2)*t[n]; T[n_, n_] := T[n, n] = 1;
T[n_, k_] := T[n, k] = Binomial[n, k - 1]*T[n - k + 1, 1];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten

Crossrefs

Cf. A005840 (row sums), A317057 (column k=1), A053525.

Sequence in context: A181355 A128320 A189507 * A350528 A208057 A298673

Adjacent sequences: A348433 A348434 A348435 * A348437 A348438 A348439

Keyword

nonn,tabl

Author

David Galvin, Oct 18 2021

Status

approved