cp's OEIS Frontend

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.

%I A348436 #35 Nov 24 2021 01:01:16
%S A348436 1,1,1,4,3,1,23,16,6,1,166,115,40,10,1,1437,996,345,80,15,1,14512,
%T A348436 10059,3486,805,140,21,1,167491,116096,40236,9296,1610,224,28,1,
%U A348436 2174746,1507419,522432,120708,20916,2898,336,36,1,31374953,21747460,7537095,1741440,301770,41832,4830,480,45,1
%N 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.
%C A348436 The class of threshold graphs is the smallest class of graphs that includes K1 and is closed under adding isolated vertices and dominating vertices.
%H A348436 D. Galvin, G. Wesley and B. Zacovic, <a href="https://arxiv.org/abs/2110.08953">Enumerating threshold graphs and some related graph classes</a>, arXiv:2110.08953 [math.CO], 2021.
%H A348436 Sam Spiro, <a href="https://arxiv.org/abs/1909.06518">Counting Threshold Graphs with Eulerian Numbers</a>, arXiv:1909.06518 [math.CO], 2019.
%F A348436 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.
%F A348436 T(n, k) = binomial(n, k-1)*A053525(n - k + 1) if k != n, otherwise 1. - _Peter Luschny_, Oct 24 2021
%e A348436 Triangle begins:
%e A348436          1;
%e A348436          1,        1;
%e A348436          4,        3,       1;
%e A348436         23,       16,       6,       1;
%e A348436        166,      115,      40,      10,      1;
%e A348436       1437,      996,     345,      80,     15,     1;
%e A348436      14512,    10059,    3486,     805,    140,    21,    1;
%e A348436     167491,   116096,   40236,    9296,   1610,   224,   28,   1;
%e A348436    2174746,  1507419,  522432,  120708,  20916,  2898,  336,  36,  1;
%e A348436   31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1;
%e A348436 ...
%p A348436 T := (n, k) -> `if`(n = k, 1, binomial(n, k-1)*A053525(n-k+1)):
%p A348436 for n from 1 to 10 do seq(T(n, k), k=1..n) od; # _Peter Luschny_, Oct 24 2021
%t A348436 eulerian[0, 0] := 1; eulerian[n_, m_] := eulerian[n, m] =
%t A348436 Sum[((-1)^k)*Binomial[n + 1, k]*((m + 1 - k)^n), {k, 0, m + 1}];
%t A348436 (* t[n] counts the labeled threshold graphs on n vertices *)
%t A348436 t[0] = 1; t[1] = 1;
%t A348436 t[n_] := t[n] = Sum[(n - k)*eulerian[n - 1, k - 1]*(2^k), {k, 1, n - 1}];
%t A348436 T[1, 1] := 1; T[n_, 1] := T[n, 1] = (1/2)*t[n]; T[n_, n_] := T[n, n] = 1;
%t A348436 T[n_, k_] := T[n, k] = Binomial[n, k - 1]*T[n - k + 1, 1];
%t A348436 Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten
%Y A348436 Cf. A005840 (row sums), A317057 (column k=1), A053525.
%K A348436 nonn,tabl
%O A348436 1,4
%A A348436 _David Galvin_, Oct 18 2021