cp's OEIS Frontend

A350060 Triangle read by rows: T(n,k) is the number of labeled threshold graphs on vertex set [n] in which k dominating vertices are added in standard iterative construction, n >= 1 and 0 <= k <= n-1.

%I A350060 #12 Jan 12 2022 21:41:05
%S A350060 1,1,1,1,6,1,1,22,22,1,1,65,200,65,1,1,171,1265,1265,171,1,1,420,6566,
%T A350060 15050,6566,420,1,1,988,30156,136346,136346,30156,988,1,1,2259,127632,
%U A350060 1039878,2009952,1039878,127632,2259,1
%N A350060 Triangle read by rows: T(n,k) is the number of labeled threshold graphs on vertex set [n] in which k dominating vertices are added in standard iterative construction, n >= 1 and 0 <= k <= n-1.
%C A350060 Threshold graphs are constructed from a single vertex by iteratively adding isolated vertices (adjacent to nothing previously added) and dominating vertices (adjacent to everything previously added). The initial vertex is not considered to be a dominating vertex.
%H A350060 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.
%F A350060 T(n,0) = 1 for n >= 1; T(2,1) = 1; T(n,k) = (Sum_{j=1..k} binomial(n, k+1)*A348576(k+1, j)*((j-1)!*A008277(n-k-1, j-1) + j!*A008277(n-k-1, j))) + (Sum_{j=1..n-k-1} binomial(n, k)*j!*A008277(k, j)*(A348576(n-k, j+1) + A348576(n-k, j))) for n >= 3, k >= 1. (See also equation (7) of paper by Galvin, Wesley and Zacovic.)
%e A350060 Triangle begins:
%e A350060   1;
%e A350060   1,     1;
%e A350060   1,     6,      1;
%e A350060   1,    22,     22,       1;
%e A350060   1,    65,    200,      65,       1;
%e A350060   1,   171,   1265,    1265,     171,       1;
%e A350060   1,   420,   6566,   15050,    6566,     420,      1;
%e A350060   1,   988,  30156,  136346,  136346,   30156,    988,    1;
%e A350060   1,  2259, 127632, 1039878, 2009952, 1039878, 127632,  2259,  1;
%e A350060   ...
%t A350060 eulerian[n_,m_] := eulerian[n,m] =
%t A350060   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 A350060 op2[n_,k_] := op2[n,k] =
%t A350060    Sum[(n-j)*eulerian[n-1,j-1]*Binomial[j-1,n-k-1], {j,1,n-1}] (* op2[n,k] counts ordered partitions of [n] with k parts, with first part having size at least 2 *);
%t A350060 T[n_, 0] := T[n, 0] = 1; T[2, 1] = 1; T[2, k_] := T[2, k] = 0;
%t A350060 T[n_, k_] :=
%t A350060 T[n, k] =
%t A350060   Sum[Binomial[n, k + 1]*
%t A350060      op2[k + 1,
%t A350060       l]*(Factorial[l - 1]*StirlingS2[n - k - 1, l - 1] +
%t A350060        Factorial[l]*StirlingS2[n - k - 1, l]) +
%t A350060     Binomial[n, k]*Factorial[l]*
%t A350060      StirlingS2[k, l]*(op2[n - k, l + 1] + op2[n - k, l]), {l, 1,
%t A350060     n}] (* T[n, k] is number of threshold graphs on n vertices with k dominating vertices added in construction*);
%t A350060 Table[T[n, k],{n,1,12},{k,0,n-1}]
%Y A350060 Row sums are A005840.
%Y A350060 Cf. A348576.
%K A350060 nonn,tabl
%O A350060 1,5
%A A350060 _David Galvin_, Dec 11 2021