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
KEYWORD
nonn,tabl
AUTHOR
Jasha Gurevich, Dec 08 2015
STATUS
approved