OFFSET
1,2
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. T(n,k) is the number of right unique relations and T(k,n) is the number of left unique relations: relation R is left unique if (a1,b) in R and (a2,b) in R implies a1=a2.
LINKS
Roy S. Freedman, Some New Results on Binary Relations, arXiv:1501.01914 [cs.DM], 2015.
FORMULA
T(n,k) = (k+1)^n - 1.
EXAMPLE
T(n,k) begins:
1, 2, 3, 4, 5, 6, 7, 8, ...
3, 8, 15, 24, 35, 48, 63, 80, ...
7, 26, 63, 124, 215, 342, 511, 728, ...
15, 80, 255, 624, 1295, 2400, 4095, 6560, ...
31, 242, 1023, 3124, 7775, 16806, 32767, 59048, ...
63, 728, 4095, 15624, 46655, 117648, 262143, 531440, ...
127, 2186, 16383, 78124, 279935, 823542, 2097151, 4782968, ...
255, 6560, 65535, 390624, 1679615, 5764800, 16777215, 43046720, ...
MAPLE
T:= (n, k)-> (k+1)^n-1:
seq(seq(T(1+d-k, k), k=1..d), d=1..12);
MATHEMATICA
T[n_, k_] := (k + 1)^n - 1; Table[T[n - k + 1, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Amiram Eldar, Nov 25 2019 *)
PROG
(MuPAD) T:=(n, k)->(k+1)^n-1:
CROSSREFS
KEYWORD
AUTHOR
Roy S. Freedman, Nov 24 2019
STATUS
approved