Jasha Gurevich - cp's OEIS frontend

User: Jasha Gurevich

Jasha Gurevich has authored 3 sequences.

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, 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

Jasha Gurevich, Dec 14 2015

A(n,m) is the number of surjective difunctional (regular) binary relations between an n-element set and an m-element set.

			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

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

Cf. A265417, A265706.

sum((Stirling2(m, i-1)*factorial(i)+Stirling2(m,i)*factorial(i))*Stirling2(n, i), i = 1 .. n);

T(n, m) = sum(i=1, n, (stirling(m, i-1, 2)*i! + stirling(m, i, 2)*i!)*stirling(n, i, 2));

T(n, m) = Sum_{i=1..n} (Stirling2(m, i-1)* i! + Stirling2(m, i)* i! ) * Stirling2(n, i).

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.

Original entry on oeis.org

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

Jasha Gurevich, Dec 14 2015

A(n,m) is the number of total difunctional (regular) binary relations between an n-element set and an m-element set.

			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

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

Cf. A265417.

sum((Stirling2(m, i)*factorial(i)+Stirling2(m, i+1)*factorial(i+1))*Stirling2(n, i), i = 1 .. n);

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 *)

T(n, m) = sum(i=1, n, ( stirling(m, i, 2)*i! + stirling(m, i+1, 2)*(i+1)!)*stirling(n, i, 2));

T(n, m) = Sum_{i=1..n} (Stirling2(m, i)* i! + Stirling2(m, i+1)*(i+1)!) *Stirling2(n, i).

A265417 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.

Original entry on oeis.org

2, 4, 4, 8, 12, 8, 16, 34, 34, 16, 32, 96, 128, 96, 32, 64, 274, 466, 466, 274, 64, 128, 792, 1688, 2100, 1688, 792, 128, 256, 2314, 6154, 9226, 9226, 6154, 2314, 256, 512, 6816, 22688, 40356, 48032, 40356, 22688, 6816, 512, 1024, 20194, 84706, 177466, 245554, 245554, 177466, 84706, 20194, 1024, 2048, 60072, 320168

Offset: 1

Jasha Gurevich, Dec 08 2015

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)

			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 ...
  ...

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.

Cf. A005056 (1st line or column ?), A014235 (diagonal ?), A341287.

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)

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

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)

cp's OEIS Frontend

User: Jasha Gurevich

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A265417 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula