A218695 - OEIS

%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