login
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

%I #26 Nov 25 2019 16:20:21

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

%T 42,7,8,56,228,500,500,228,56,8,9,72,357,1044,1545,1044,357,72,9,10,

%U 90,528,1960,4050,4050,1960,528,90,10,11,110,747,3392,9275,13326,9275,3392,747,110,11

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

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

%H Roy S. Freedman, <a href="https://arxiv.org/abs/1501.01914">Some New Results on Binary Relations</a>, arXiv:1501.01914 [cs.DM], 2015.

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

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

%e The symmetric array T(n,k) begins:

%e 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

%e 2, 6, 12, 20, 30, 42, 56, 72, 90, ...

%e 3, 12, 33, 72, 135, 228, 357, 528, 747, ...

%e 4, 20, 72, 208, 500, 1044, 1960, 3392, 5508, ...

%e 5, 30, 135, 500, 1545, 4050, 9275, 19080, 36045, ...

%e 6, 42, 228, 1044, 4050, 13326, 37632, 93288, 207774, ...

%e 7, 56, 357, 1960, 9275, 37632, 130921, 394352, 1047375, ...

%e 8, 72, 528, 3392, 19080, 93288, 394352, 1441728, 4596552, ...

%e 9, 90, 747, 5508, 36045, 207774, 1047375, 4596552, 17572113, ...

%p T:= (n,k)-> value(Sum(binomial(n,j)*binomial(k, j)*j!, j=1..k)):

%p seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

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

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

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

%K nonn,tabl,easy

%O 1,2

%A _Roy S. Freedman_, Nov 18 2019