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.

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

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

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: A185877 A135858 A193845 * A098966 A021763 A261693

Adjacent sequences: A265703 A265704 A265705 * A265707 A265708 A265709

Keyword

nonn,tabl

Author

Jasha Gurevich, Dec 14 2015

Status

approved