cp's OEIS Frontend

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.

%I A329943 #24 Jun 23 2024 11:52:00
%S A329943 1,3,1,7,9,1,15,49,27,1,31,225,343,81,1,63,961,3375,2401,243,1,127,
%T A329943 3969,29791,50625,16807,729,1,255,16129,250047,923521,759375,117649,
%U A329943 2187,1,511,65025,2048383,15752961,28629151,11390625,823543,6561,1
%N 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.
%C A329943 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.
%C A329943 From _Manfred Boergens_, Jun 23 2024: (Start)
%C A329943 T(n,k) is the number of k X n binary matrices with no 0 rows.
%C A329943 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.
%C A329943 Swapping n,k gives A092477 (with k<=n).
%C A329943 For nonempty A_j see A218695 (n,k swapped).
%C A329943 For disjoint A_j see A089072 (n,k swapped).
%C A329943 For nonempty and disjoint A_j see A019538 (n,k swapped). (End)
%H A329943 Roy S. Freedman, <a href="https://arxiv.org/abs/1501.01914">Some New Results on Binary Relations</a>, arXiv:1501.01914 [cs.DM], 2015.
%F A329943 T(n,k) = (2^n - 1)^k.
%e A329943 T(n,k) begins, for 1 <= n,k <= 9:
%e A329943     1,     1,       1,         1,           1,             1,               1
%e A329943     3,     9,      27,        81,         243,           729,            2187
%e A329943     7,    49,     343,      2401,       16807,        117649,          823543
%e A329943    15,   225,    3375,     50625,      759375,      11390625,       170859375
%e A329943    31,   961,   29791,    923521,    28629151,     887503681,     27512614111
%e A329943    63,  3969,  250047,  15752961,   992436543,   62523502209,   3938980639167
%e A329943   127, 16129, 2048383, 260144641, 33038369407, 4195872914689, 532875860165503
%p A329943 rt:=(n,k)->(2^n-1)^k:
%t A329943 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 *)
%o A329943 (MuPAD) rt:=(n,k)->(2^n-1)^k:
%Y A329943 Cf. A218695.
%Y A329943 The diagonal T(n,n) is A055601.
%Y A329943 A092477 = T(k,n) is the number of left total relations between A and B.
%Y A329943 A053440 is the number of relations that are both right unique (see A329940) and right total.
%Y A329943 A089072 is the number of functions from A to B: relations between A and B that are both right unique and left total.
%Y A329943 A019538 is the number of surjections between A and B: relations that are right unique, right total, and left total.
%Y A329943 A008279 is the number of injections: relations that are right unique, left total, and left unique.
%Y A329943 A000142 is the number of bijections: relations that are right unique, left total, right total, and left unique.
%K A329943 nonn,tabl,easy
%O A329943 1,2
%A A329943 _Roy S. Freedman_, Nov 24 2019