|
|
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.
|
|
8
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|