A329943 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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

LINKS

Table of n, a(n) for n=1..45.

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

FORMULA

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

EXAMPLE

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

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

PROG

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

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.

Sequence in context: A229837 A019639 A306566 * A372908 A011207 A087129

Adjacent sequences: A329940 A329941 A329942 * A329944 A329945 A329946

KEYWORD

nonn,tabl,easy

AUTHOR

Roy S. Freedman, Nov 24 2019

STATUS

approved