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

2, 4, 4, 8, 12, 8, 16, 34, 34, 16, 32, 96, 128, 96, 32, 64, 274, 466, 466, 274, 64, 128, 792, 1688, 2100, 1688, 792, 128, 256, 2314, 6154, 9226, 9226, 6154, 2314, 256, 512, 6816, 22688, 40356, 48032, 40356, 22688, 6816, 512, 1024, 20194, 84706, 177466, 245554, 245554, 177466, 84706, 20194, 1024, 2048, 60072, 320168

Offset

1,1

Comments

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

From Petros Hadjicostas, Feb 09 2021: (Start)

From Knopfmacher and Mays (2001): "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), T(n,m) = C(K_{n,m}) = Sum_{i=1..n+1} A341287(n,i)*i^m, where K_{n,m} is the complete bipartite graph with n+m vertices and n*m edges. For values of T(n,m), see the table on p. 10 of the paper.

Huq (2007) reproved the result using different methodology and derived the bivariate e.g.f. of T(n,m). (End)

Links

Jasha Gurevich, Table of n, a(n) for n = 1..300

Chris Brink, Wolfram Kahl, and Gunther Schmidt, Relational Methods in Computer Science, Springer Science & Business Media, 1997, p. 200.

Jasha Gurevich, Full list of formulas for correspondences (binary relations).

Amiqul Huq, Compositions of graphs revisited, Vol. 14 (2007), Article N15.

A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumerations, Integers, Vol. 1 (2001), Article A4. (See p. 10 for the table and p. 8 for a formula.)

J. Riguet, Relations binaires, fermetures, correspondances de Galois, Bulletin de la Société Mathématique de France, Vol. 76 (1948), 114-155.

Wikipedia, Binary relation.

Formula

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

From Petros Hadjicostas, Feb 09 2021: (Start)

T(n,m) = Sum_{i=1..n+1} A341287(n,i)*i^m = Sum_{i=1..m+1} A341287(m,i)*i^n. (See Knopfmacher and Mays (2001) and Huq (2007).)

Bivariate e.g.f.: Sum_{n,m >= 1} T(n,m)*(x^n/n!)*(y^m/m!) = exp((exp(x) - 1)*(exp(y) - 1) + x + y) - exp(x) - exp(y) + 1. (This is a modification of Eq. (7) in Huq (2007), p. 4.) (End)

Example

Array T(n,m) (with rows n >= 1 and columns m >= 1) begins:
    2      4      8      16       32        64        128         256 ...
    4     12     34      96      274       792       2314        6816 ...
    8     34    128     466     1688      6154      22688       84706 ...
   16     96    466    2100     9226     40356     177466      788100 ...
   32    274   1688    9226    48032    245554    1251128     6402586 ...
   64    792   6154   40356   245554   1444212    8380114    48510036 ...
  128   2314  22688  177466  1251128   8380114   54763088   354298186 ...
  256   6816  84706  788100  6402586  48510036  354298186  2540607060 ...
  512  20194 320168 3541066 33044432 281910994 2288754728 18082589146 ...
  ...

Maple

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

Prog

(PARI) T(n, m) = sum(i=1, n, (stirling(m, i-1, 2)*i! + stirling(m, i, 2)*(i+1)! + stirling(m, i+1, 2)*(i+1)!)*stirling(n, i, 2)); \\ Michel Marcus, Dec 10 2015

Crossrefs

Cf. A005056 (1st line or column ?), A014235 (diagonal ?), A341287.

Sequence in context: A319803 A055946 A130124 * A076342 A135268 A245619

Adjacent sequences: A265414 A265415 A265416 * A265418 A265419 A265420

Keyword

nonn,tabl

Author

Jasha Gurevich, Dec 08 2015

Status

approved