login
Triangle read by rows: T(n,k) = Sum_{i=0..n-1} binomial(n-1, i)*T(n-1-i,k-1) - Sum_{i=1..n-1} binomial(n-1,i)*T(n-1-i,k) for 1 <= k <= n+1 with T(0,1) = 1 (and T(n,k) = 0 otherwise).
3

%I #60 Apr 20 2022 12:58:21

%S 1,0,1,-1,1,1,-1,-2,3,1,2,-9,1,6,1,9,-9,-25,15,10,1,9,50,-104,-20,50,

%T 15,1,-50,267,-98,-364,105,119,21,1,-267,413,1163,-1610,-539,574,238,

%U 28,1,-413,-2180,7569,-1511,-6636,903,1806,426,36,1,2180,-17731,17491,29580,-32570,-12957,8757,4500,705,45,1

%N Triangle read by rows: T(n,k) = Sum_{i=0..n-1} binomial(n-1, i)*T(n-1-i,k-1) - Sum_{i=1..n-1} binomial(n-1,i)*T(n-1-i,k) for 1 <= k <= n+1 with T(0,1) = 1 (and T(n,k) = 0 otherwise).

%C To agree with Knopfmacher and Mays (2001), the rows start at n = 0 while the columns start at k = 1.

%C The row sums equal 1.

%C "Let G be a labeled graph, with edge set E(G) and vertex set V(G). A composition of G is a partition of V(G) into vertex sets of connected induced subgraphs of G." "We will denote by C(G) the number of distinct compositions that exist for a given graph G." By Theorem 10 in Knofmacher and Mays (2001), C(K_{n,k}) = Sum_{i=1..n+1} T(n,i)*i^k, where K_{n,k} is the bipartite graph with n+k vertices and n*k edges. For values of C(K_{n,k}), see the table on p. 10 of the paper.

%C We have C(K_{n,k}) = A265417(n,k).

%C By symmetry, Sum_{i=1..n+1} T(n,i)*i^k = C(K_{n,k}) = C(K_{k,n}) = Sum_{i=1..k+1} T(k,i)*i^n for n, k >= 1.

%C Denote the bivariate e.g.f.-o.g.f by A(x,y) = Sum_{n>=0,k>=1} T(n,k)*(x^n/n!)*y^k. Using the definition of T(n,k) and standard manipulations of generating functions, one can prove that A(x,y) = y + int_{w=0..x} A(w,y)*((y-1)*exp(w) + 1) dw. This leads to the initial condition A(0,y) = y and the differential equation dA(x,y)/dx = A(x,y)*((y-1)*exp(x) + 1). Solving this differential equation (for a fixed y), we get A(x,y) = y*exp((1 - y)*(1 - exp(x)) + x). (The bivariate e.g.f.-o.g.f was originally guessed due to the contributions of _Seiichi Manyama_ in A335977.)

%H Aminul Huq, <a href="https://doi.org/10.37236/1016">Compositions of graphs revisited</a>, The Electronic Journal of Combinatorics, Vol. 14 (2007), Article N15.

%H A. Knopfmacher and M. E. Mays, <a href="http://math.colgate.edu/~integers/b4/b4.pdf">Graph compositions I: Basic enumerations</a>, Integers, Vol. 1 (2001), Article A4. (See p. 9 for the table and p. 8 for the recurrence.)

%F Sum_{k=1..n+1} (-1)^(k-1)*T(n,k) = A309775(n) for n >= 0.

%F Sum_{k=1..n+1} (-m)^(k-1)*T(n,k) = A335977(n,m+1) for m >= 1 and n >= 0.

%F T(n,n+1) = 1 and T(n,n) = A000217(n-1) = n*(n-1)/2 for n >= 1.

%F T(n,1) = -A000587(n+1) for n >= 0 (complementary Bell numbers).

%F T(n,2) = -T(n+1,1) for n >= 1.

%F Bivariate e.g.f.-o.g.f: Sum_{n>=0,k>=1} T(n,k)*(x^n/n!)*y^k = y*exp((1 - y)*(1 -exp(x)) + x).

%F T(n,k) = Sum_{j=1..n+1} binomial(j - 1, k - 1)*(-1)^(j - k)*Stirling2(n + 1, j) for n >= 0 and 1 <= k <= n+1, where Stirling2(n,k) = A048993(n,k). (This is a modification of a formula in Section 4 of Huq (2007).)

%F From _Mélika Tebni_, Apr 20 2022: (Start)

%F T(n, k) = Sum_{j=0..n} A129334(n, j)*Stirling2(j+1, k) for n >= 0 and 1 <= k <= n+1.

%F E.g.f. column k: (exp(x) - 1)^(k-1) / (k-1)!*exp(x - (exp(x) - 1)), k >= 1. (End)

%e Triangle T(n,k) with rows n >= 0 and columns 1 <= k <= n+1 begins:

%e 1,

%e 0, 1,

%e -1, 1, 1,

%e -1, -2, 3, 1,

%e 2, -9, 1, 6, 1,

%e 9, -9, -25, 15, 10, 1,

%e 9, 50, -104, -20, 50, 15, 1,

%e -50, 267, -98, -364, 105, 119, 21, 1,

%e -267, 413, 1163, -1610, -539, 574, 238, 28, 1,

%e -413, -2180, 7569, -1511, -6636, 903, 1806, 426, 36, 1,

%e ...

%p egf := k-> (exp(x)-1)^(k-1)/(k-1)!*exp(x-(exp(x)-1)):

%p A341287 := (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):

%p seq(print(seq(A341287(n, k), k=1..n+1)), n=0..9); # _Mélika Tebni_, Apr 20 2022

%Y Cf. A000217, A000587, A048993, A265417, A309775, A335977.

%K sign,tabl

%O 0,8

%A _Petros Hadjicostas_, Feb 08 2021