login
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.
2
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,2
COMMENTS
A(n,m) is the number of total difunctional (regular) binary relations between an n-element set and an m-element set.
LINKS
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
FORMULA
T(n, m) = Sum_{i=1..n} (Stirling2(m, i)* i! + Stirling2(m, i+1)*(i+1)!) *Stirling2(n, i).
EXAMPLE
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
MAPLE
sum((Stirling2(m, i)*factorial(i)+Stirling2(m, i+1)*factorial(i+1))*Stirling2(n, i), i = 1 .. n);
MATHEMATICA
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 *)
PROG
(PARI) T(n, m) = sum(i=1, n, ( stirling(m, i, 2)*i! + stirling(m, i+1, 2)*(i+1)!)*stirling(n, i, 2));
CROSSREFS
Cf. A265417.
Sequence in context: A135858 A193845 A372938 * A098966 A021763 A261693
KEYWORD
nonn,tabl
AUTHOR
Jasha Gurevich, Dec 14 2015
STATUS
approved