A329655 Square array read by antidiagonals: T(n,k) is the number of relations between set A with n elements and set B with k elements that are both right unique and left unique.

1, 2, 2, 3, 6, 3, 4, 12, 12, 4, 5, 20, 33, 20, 5, 6, 30, 72, 72, 30, 6, 7, 42, 135, 208, 135, 42, 7, 8, 56, 228, 500, 500, 228, 56, 8, 9, 72, 357, 1044, 1545, 1044, 357, 72, 9, 10, 90, 528, 1960, 4050, 4050, 1960, 528, 90, 10, 11, 110, 747, 3392, 9275, 13326, 9275, 3392, 747, 110, 11

Offset: 1

Author

Roy S. Freedman, Nov 18 2019

Keywords

• nonn
• tabl
• easy

Comments

A relation R between set A with n elements and set B with k elements is a subset of the Cartesian product A x B. A relation R is right unique if (a, b1) in R and (a,b2) in R implies b1=b2. A relation R is left unique if (a1,b) in R and (a2,b) in R implies a1=a2.

Examples

			The symmetric array T(n,k) begins:
  1,   2,    3,    4,     5,      6,       7,       8,        9, ...
  2,   6,   12,   20,    30,     42,      56,      72,       90, ...
  3,  12,   33,   72,   135,    228,     357,     528,      747, ...
  4,  20,   72,  208,   500,   1044,    1960,    3392,     5508, ...
  5,  30,  135,  500,  1545,   4050,    9275,   19080,    36045, ...
  6,  42,  228, 1044,  4050,  13326,   37632,   93288,   207774, ...
  7,  56,  357, 1960,  9275,  37632,  130921,  394352,  1047375, ...
  8,  72,  528, 3392, 19080,  93288,  394352, 1441728,  4596552, ...
  9,  90,  747, 5508, 36045, 207774, 1047375, 4596552, 17572113, ...
		

Links

• Roy S. Freedman, Some New Results on Binary Relations, arXiv:1501.01914 [cs.DM], 2015.

Crossrefs

The diagonal T(n,n) is A097662. T(1,k)=A000027; T(2,k)=A002378; T(3,k)=A054602.

Programs

Maple

T:= (n,k)-> value(Sum(binomial(n,j)*binomial(k, j)*j!, j=1..k)):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

Mathematica

T[n_, k_] := Sum[Binomial[n, j] * Binomial[k, j] * j!, {j, 1, k}]; Table[T[n - k + 1, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Amiram Eldar, Nov 25 2019 *)

MuPAD

T:=(n,k)->_plus (binomial(n,j)*binomial(k, j)* j! $ j=1..k):

Formula

T(n,k) = Sum_{j=1..k} binomial(n,j)*binomial(k,j)*j!.

T(n,k) = A088699(n,k)-1.