|
| |
|
|
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.
|
|
4
|
|
|
|
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.
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
|
|
|
|
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
|
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
