A218695 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.

1, 1, 1, 1, 7, 1, 1, 25, 25, 1, 1, 79, 265, 79, 1, 1, 241, 2161, 2161, 241, 1, 1, 727, 16081, 41503, 16081, 727, 1, 1, 2185, 115465, 693601, 693601, 115465, 2185, 1, 1, 6559, 816985, 10924399, 24997921, 10924399, 816985, 6559, 1

Offset: 1

Author

M. F. Hasler, Nov 04 2012

Keywords

• nonn
• tabl

Comments

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.

Number of h X k binary matrices with no zero rows or columns. - Andrew Howroyd, Mar 29 2023

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

Examples

			Array A(h,k) begins:
=====================================================
h\k | 1   2      3        4         5           6 ...
----+------------------------------------------------
  1 | 1   1      1        1         1           1 ...
  2 | 1   7     25       79       241         727 ...
  3 | 1  25    265     2161     16081      115465 ...
  4 | 1  79   2161    41503    693601    10924399 ...
  5 | 1 241  16081   693601  24997921   831719761 ...
  6 | 1 727 115465 10924399 831719761 57366997447 ...
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
• G. Kreweras, Dénombrements systématiques de relations binaires externes, Math. Sci. Humaines 26 (1969) 5-15.
• G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.

Crossrefs

Columns 1..3 are A000012, A058481, A058482.

Main diagonal is A048291.

Cf. A019538, A056152 (unlabeled case), A052332, A092477, A183109, A223911, A329943.

Programs

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)}
/* 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));
s[1] >= h & s[2] >= k & cM[h,k] & return(cM[h,k]);
s[1]
				

PARI

A(m, n) = sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n ) \\ Andrew Howroyd, Mar 29 2023

Formula

From Andrew Howroyd, Mar 29 2023: (Start)

A(h, k) = Sum_{i=0..h} (-1)^(h-i) * binomial(h, i) * (2^i-1)^k.

A052332(n) = Sum_{i=1..n-1} binomial(n,i)*A(i, n-i) for n > 0. (End)