|
%I #30 Jul 19 2024 11:32:47
%S 1,1,1,1,7,1,1,25,25,1,1,79,265,79,1,1,241,2161,2161,241,1,1,727,
%T 16081,41503,16081,727,1,1,2185,115465,693601,693601,115465,2185,1,1,
%U 6559,816985,10924399,24997921,10924399,816985,6559,1
%N Square array A(h,k) = (2^h-1)*A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)*2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.
%C This symmetric table is defined in the Kreweras papers, used also in A223911. Its upper or lower triangular part equals A183109, which might provide a simpler formula.
%C Number of h X k binary matrices with no zero rows or columns. - _Andrew Howroyd_, Mar 29 2023
%C A(h,k) is the number of coverings of [h] by tuples (A_1,...,A_k) in P([h])^k with nonempty A_j, with P(.) denoting the power set. For the disjoint case see A019538. For tuples with "nonempty" omitted see A092477 and A329943 (amendment by _Manfred Boergens_, Jun 24 2024). - _Manfred Boergens_, May 26 2024
%H Andrew Howroyd, <a href="/A218695/b218695.txt">Table of n, a(n) for n = 1..1275</a> (first 50 antidiagonals)
%H G. Kreweras, <a href="http://www.numdam.org/item/?id=MSH_1969__26__5_0">Dénombrements systématiques de relations binaires externes</a>, Math. Sci. Humaines 26 (1969) 5-15.
%H G. Kreweras, <a href="http://dx.doi.org/10.1016/0012-365X(85)90137-2">Dénombrement des ordres étagés</a>, Discrete Math., 53 (1985), 147-149.
%F From _Andrew Howroyd_, Mar 29 2023: (Start)
%F A(h, k) = Sum_{i=0..h} (-1)^(h-i) * binomial(h, i) * (2^i-1)^k.
%F A052332(n) = Sum_{i=1..n-1} binomial(n,i)*A(i, n-i) for n > 0. (End)
%e Array A(h,k) begins:
%e =====================================================
%e h\k | 1 2 3 4 5 6 ...
%e ----+------------------------------------------------
%e 1 | 1 1 1 1 1 1 ...
%e 2 | 1 7 25 79 241 727 ...
%e 3 | 1 25 265 2161 16081 115465 ...
%e 4 | 1 79 2161 41503 693601 10924399 ...
%e 5 | 1 241 16081 693601 24997921 831719761 ...
%e 6 | 1 727 115465 10924399 831719761 57366997447 ...
%e ...
%o (PARI) c(h,k)={(h<2 || k<2) & return(1); sum(i=1,h-1,binomial(h,h-i)*2^i*c(i,k-1))+(2^h-1)*c(h,k-1)}
%o /* For better performance when h and k are large, insert the following memoization code before "sum(...)": cM=='cM & cM=matrix(h,k); my(s=matsize(cM));
%o s[1] >= h & s[2] >= k & cM[h,k] & return(cM[h,k]);
%o s[1]<h & cM=concat(cM~,matrix(s[2],h-s[1]))~;
%o s[2]<k & cM=concat(cM,matrix(max(h,s[1]),k-s[2])); cM[h,k]= */
%o (PARI) A(m, n) = sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n ) \\ _Andrew Howroyd_, Mar 29 2023
%Y Columns 1..3 are A000012, A058481, A058482.
%Y Main diagonal is A048291.
%Y Cf. A019538, A056152 (unlabeled case), A052332, A092477, A183109, A223911, A329943.
%K nonn,tabl
%O 1,5
%A _M. F. Hasler_, Nov 04 2012
|
