|
%I #65 Feb 10 2021 08:25:25
%S 2,4,4,8,12,8,16,34,34,16,32,96,128,96,32,64,274,466,466,274,64,128,
%T 792,1688,2100,1688,792,128,256,2314,6154,9226,9226,6154,2314,256,512,
%U 6816,22688,40356,48032,40356,22688,6816,512,1024,20194,84706,177466,245554,245554,177466,84706,20194,1024,2048,60072,320168
%N 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.
%C T(n,m) is the number of difunctional (regular) binary relations between an n-element set and an m-element set.
%C From _Petros Hadjicostas_, Feb 09 2021: (Start)
%C 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."
%C 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.
%C Huq (2007) reproved the result using different methodology and derived the bivariate e.g.f. of T(n,m). (End)
%H Jasha Gurevich, <a href="/A265417/b265417.txt">Table of n, a(n) for n = 1..300</a>
%H Chris Brink, Wolfram Kahl, and Gunther Schmidt, <a href="http://dx.doi.org/10.1007/978-3-7091-6510-2">Relational Methods in Computer Science</a>, Springer Science & Business Media, 1997, p. 200.
%H Jasha Gurevich, <a href="/A265417/a265417_2.pdf">Full list of formulas for correspondences (binary relations)</a>.
%H Amiqul Huq, <a href="https://doi.org/10.37236/1016">Compositions of graphs revisited</a>, 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. 10 for the table and p. 8 for a formula.)
%H J. Riguet, <a href="http://www.numdam.org/item?id=BSMF_1948__76__114_0">Relations binaires, fermetures, correspondances de Galois</a>, Bulletin de la Société Mathématique de France, Vol. 76 (1948), 114-155.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_relation#Difunctional"> Binary relation</a>.
%F 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).
%F From _Petros Hadjicostas_, Feb 09 2021: (Start)
%F 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).)
%F 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)
%e Array T(n,m) (with rows n >= 1 and columns m >= 1) begins:
%e 2 4 8 16 32 64 128 256 ...
%e 4 12 34 96 274 792 2314 6816 ...
%e 8 34 128 466 1688 6154 22688 84706 ...
%e 16 96 466 2100 9226 40356 177466 788100 ...
%e 32 274 1688 9226 48032 245554 1251128 6402586 ...
%e 64 792 6154 40356 245554 1444212 8380114 48510036 ...
%e 128 2314 22688 177466 1251128 8380114 54763088 354298186 ...
%e 256 6816 84706 788100 6402586 48510036 354298186 2540607060 ...
%e 512 20194 320168 3541066 33044432 281910994 2288754728 18082589146 ...
%e ...
%p 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)
%o (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
%Y Cf. A005056 (1st line or column ?), A014235 (diagonal ?), A341287.
%K nonn,tabl
%O 1,1
%A _Jasha Gurevich_, Dec 08 2015
|
