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,5

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

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.

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)

Example

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

Prog

(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]<h & cM=concat(cM~, matrix(s[2], h-s[1]))~;
s[2]<k & cM=concat(cM, matrix(max(h, s[1]), k-s[2])); cM[h, k]= */
(PARI) A(m, n) = sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n ) \\ Andrew Howroyd, Mar 29 2023

Crossrefs

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

Main diagonal is A048291.

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

Sequence in context: A056752 A053714 A168290 * A179837 A238743 A168517

Adjacent sequences: A218692 A218693 A218694 * A218696 A218697 A218698

Keyword

nonn,tabl

Author

M. F. Hasler, Nov 04 2012

Status

approved