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

1, 3, 1, 7, 9, 1, 15, 49, 27, 1, 31, 225, 343, 81, 1, 63, 961, 3375, 2401, 243, 1, 127, 3969, 29791, 50625, 16807, 729, 1, 255, 16129, 250047, 923521, 759375, 117649, 2187, 1, 511, 65025, 2048383, 15752961, 28629151, 11390625, 823543, 6561, 1

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 total if for each b in B there exists an a in A such that (a,b) in R. T(n,k) is the number of right total relations and T(k,n) is the number of left total relations: relation R is left total if for each a in A there exists a b in B such that (a,b) in R.

From Manfred Boergens, Jun 23 2024: (Start)

T(n,k) is the number of k X n binary matrices with no 0 rows.

T(n,k) is the number of coverings of [k] by tuples (A_1,...,A_n) in P([k])^n, with P(.) denoting the power set.

Swapping n,k gives A092477 (with k<=n).

For nonempty A_j see A218695 (n,k swapped).

For disjoint A_j see A089072 (n,k swapped).

For nonempty and disjoint A_j see A019538 (n,k swapped). (End)

Examples

			T(n,k) begins, for 1 <= n,k <= 9:
    1,     1,       1,         1,           1,             1,               1
    3,     9,      27,        81,         243,           729,            2187
    7,    49,     343,      2401,       16807,        117649,          823543
   15,   225,    3375,     50625,      759375,      11390625,       170859375
   31,   961,   29791,    923521,    28629151,     887503681,     27512614111
   63,  3969,  250047,  15752961,   992436543,   62523502209,   3938980639167
  127, 16129, 2048383, 260144641, 33038369407, 4195872914689, 532875860165503
		

Links

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

Crossrefs

Cf. A218695.

The diagonal T(n,n) is A055601.

A092477 = T(k,n) is the number of left total relations between A and B.

A053440 is the number of relations that are both right unique (see A329940) and right total.

A089072 is the number of functions from A to B: relations between A and B that are both right unique and left total.

A019538 is the number of surjections between A and B: relations that are right unique, right total, and left total.

A008279 is the number of injections: relations that are right unique, left total, and left unique.

A000142 is the number of bijections: relations that are right unique, left total, right total, and left unique.

Programs

Maple

rt:=(n,k)->(2^n-1)^k:

Mathematica

T[n_, k_] := (2^n - 1)^k; Table[T[n - k + 1, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Amiram Eldar, Nov 25 2019 *)

MuPAD

rt:=(n,k)->(2^n-1)^k:

Formula

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