login
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.
1
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,3
COMMENTS
A(n,m) is the number of surjective 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-1)* i! + Stirling2(m, i)* i! ) * Stirling2(n, i).
EXAMPLE
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
MAPLE
sum((Stirling2(m, i-1)*factorial(i)+Stirling2(m, i)*factorial(i))*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!)*stirling(n, i, 2));
CROSSREFS
Sequence in context: A143524 A134249 A188509 * A360965 A336301 A188146
KEYWORD
nonn,tabl
AUTHOR
Jasha Gurevich, Dec 14 2015
STATUS
approved