A329940 Square array read by antidiagonals upwards: T(n,k) is the number of right unique relations between set A with n elements and set B with k elements.

1, 3, 2, 7, 8, 3, 15, 26, 15, 4, 31, 80, 63, 24, 5, 63, 242, 255, 124, 35, 6, 127, 728, 1023, 624, 215, 48, 7, 255, 2186, 4095, 3124, 1295, 342, 63, 8, 511, 6560, 16383, 15624, 7775, 2400, 511, 80, 9, 1023, 19682, 65535, 78124, 46655, 16806, 4095, 728, 99, 10

Offset: 1

Author

Roy S. Freedman, Nov 24 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. 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.

Examples

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

Links

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

Crossrefs

Cf. A037205 (main diagonal).

Cf. A003992, A004248, A009998, A009999, A051128, A051129, A095884.

Programs

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

MuPAD

T:=(n,k)->(k+1)^n-1:

Formula

T(n,k) = (k+1)^n - 1.