A341287 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).

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, 15, 1, -50, 267, -98, -364, 105, 119, 21, 1, -267, 413, 1163, -1610, -539, 574, 238, 28, 1, -413, -2180, 7569, -1511, -6636, 903, 1806, 426, 36, 1, 2180, -17731, 17491, 29580, -32570, -12957, 8757, 4500, 705, 45, 1

Offset: 0

Author

Petros Hadjicostas, Feb 08 2021

Keywords

• sign
• tabl

Comments

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

The row sums equal 1.

"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.

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

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.

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.)

Examples

			Triangle T(n,k) with rows n >= 0 and columns 1 <= k <= n+1 begins:
      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,  15,    1,
    -50,   267,  -98,  -364,   105, 119,   21,   1,
   -267,   413, 1163, -1610,  -539, 574,  238,  28,  1,
   -413, -2180, 7569, -1511, -6636, 903, 1806, 426, 36, 1,
   ...
		

Links

• Aminul Huq, Compositions of graphs revisited, The Electronic Journal of Combinatorics, Vol. 14 (2007), Article N15.
• A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumerations, Integers, Vol. 1 (2001), Article A4. (See p. 9 for the table and p. 8 for the recurrence.)

Crossrefs

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

Programs

Maple

egf := k-> (exp(x)-1)^(k-1)/(k-1)!*exp(x-(exp(x)-1)):
A341287 := (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):
seq(print(seq(A341287(n, k), k=1..n+1)), n=0..9); # Mélika Tebni, Apr 20 2022

Formula

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

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

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

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

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

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).

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).)

From Mélika Tebni, Apr 20 2022: (Start)

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

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