A265417 -id:A265417 - cp's OEIS frontend

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

Petros Hadjicostas, Feb 08 2021

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

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

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

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

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

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)

A265706 Rectangular array A read by upward antidiagonals: A(n,m) is the number of total difunctional (regular) binary relations between an n-element set and an m-element set.

Original entry on oeis.org

1, 3, 1, 7, 5, 1, 15, 19, 9, 1, 31, 65, 49, 17, 1, 63, 211, 225, 127, 33, 1, 127, 665, 961, 749, 337, 65, 1, 255, 2059, 3969, 3991, 2505, 919, 129, 1, 511, 6305, 16129, 20237, 16201, 8525, 2569, 257, 1, 1023, 19171, 65025, 100087, 97713, 65911

Offset: 1

Jasha Gurevich, Dec 14 2015

A(n,m) is the number of total difunctional (regular) binary relations between an n-element set and an m-element set.

			Array A begins
1   3     7     15      31       63       127        255         511
1   5    19     65     211      665      2059       6305       19171
1   9    49    225     961     3969     16129      65025      261121
1  17   127    749    3991    20237    100087     489149     2379511
1  33   337   2505   16201    97713    568177    3242265    18341401
1  65   919   8525   65911   464645   3115519   20322605   130656871
1 129  2569  29625  271561  2214009  16911049  124422105   896158921
1 257  7327 105149 1137991 10657997  91989367  756570029  6046077511
1 513 21217 380745 4857001 52034913 504717697 4611314745 40608430681

Jasha Gurevich, Table of n, a(n) for n = 1..300
Chris Brink, Wolfram Kahl, Gunther Schmidt, Relational Methods in Computer Science, Springer Science & Business Media, 1997, p. 200.
J. Riguet, Relations binaires, fermetures, correspondances de Galois, Bulletin de la Société Mathématique de France (1948) Volume: 76, pp. 114-155.
Wikipedia, Binary relation

Cf. A265417.

sum((Stirling2(m, i)*factorial(i)+Stirling2(m, i+1)*factorial(i+1))*Stirling2(n, i), i = 1 .. n);

Table[Sum[(StirlingS2[m, i] i! + StirlingS2[m, i + 1] (i + 1)!) StirlingS2[n - m + 1, i], {i, n - m + 1}], {n, 10}, {m, n, 1, -1}] // Flatten (* Michael De Vlieger, Dec 14 2015 *)

T(n, m) = sum(i=1, n, ( stirling(m, i, 2)*i! + stirling(m, i+1, 2)*(i+1)!)*stirling(n, i, 2));

T(n, m) = Sum_{i=1..n} (Stirling2(m, i)* i! + Stirling2(m, i+1)*(i+1)!) *Stirling2(n, i).

A265707 Rectangular array A read by upward antidiagonals: A(n,m) is the number of surjective difunctional (regular) binary relations between an n-element set and an m-element set.

Original entry on oeis.org

1, 1, 3, 1, 5, 7, 1, 9, 19, 15, 1, 17, 49, 65, 31, 1, 33, 127, 225, 211, 63, 1, 65, 337, 749, 961, 665, 127, 1, 129, 919, 2505, 3991, 3969, 2059, 255, 1, 257, 2569, 8525, 16201, 20237, 16129, 6305, 511, 1, 513, 7327, 29625, 65911, 97713

Offset: 1

Jasha Gurevich, Dec 14 2015

A(n,m) is the number of surjective difunctional (regular) binary relations between an n-element set and an m-element set.

			Array A begins
    1     1      1       1        1         1         1          1           1
    3     5      9      17       33        65       129        257         513
    7    19     49     127      337       919      2569       7327       21217
   15    65    225     749     2505      8525     29625     105149      380745
   31   211    961    3991    16201     65911    271561    1137991     4857001
   63   665   3969   20237    97713    464645   2214009   10657997    52034913
  127  2059  16129  100087   568177   3115519  16911049   91989367   504717697
  255  6305  65025  489149  3242265  20322605 124422105  756570029  4611314745
  511 19171 261121 2379511 18341401 130656871 896158921 6046077511 40608430681

Jasha Gurevich, Table of n, a(n) for n = 1..300
Chris Brink, Wolfram Kahl, Gunther Schmidt, Relational Methods in Computer Science, Springer Science & Business Media, 1997, p. 200.
J. Riguet, Relations binaires, fermetures, correspondances de Galois, Bulletin de la Société Mathématique de France (1948) Volume: 76, pp. 114-155.
Wikipedia, Binary relation

Cf. A265417, A265706.

sum((Stirling2(m, i-1)*factorial(i)+Stirling2(m,i)*factorial(i))*Stirling2(n, i), i = 1 .. n);

T(n, m) = sum(i=1, n, (stirling(m, i-1, 2)*i! + stirling(m, i, 2)*i!)*stirling(n, i, 2));

T(n, m) = Sum_{i=1..n} (Stirling2(m, i-1)* i! + Stirling2(m, i)* i! ) * Stirling2(n, i).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A265706 Rectangular array A read by upward antidiagonals: A(n,m) is the number of total difunctional (regular) binary relations between an n-element set and an m-element set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A265707 Rectangular array A read by upward antidiagonals: A(n,m) is the number of surjective difunctional (regular) binary relations between an n-element set and an m-element set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A265706 Rectangular array A read by upward antidiagonals: A(n,m) is the number of total difunctional (regular) binary relations between an n-element set and an m-element set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A265707 Rectangular array A read by upward antidiagonals: A(n,m) is the number of surjective difunctional (regular) binary relations between an n-element set and an m-element set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

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