OFFSET
0,5
COMMENTS
A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with rows in decreasing order and at most n ones in every column.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..209
FORMULA
Lim_{n->oo} A(n,k) = 2^k.
EXAMPLE
Array begins:
==================================================================
n\k | 0 1 2 3 4 5 6 7
----+-------------------------------------------------------------
0 | 1 1 1 1 1 1 1 1 ...
1 | 1 2 5 15 52 203 877 4140 ...
2 | 1 2 8 59 652 9736 186478 4421018 ...
3 | 1 2 8 109 3623 200522 16514461 1912959395 ...
4 | 1 2 8 128 11087 2232875 775098224 428188962261 ...
5 | 1 2 8 128 21380 15312665 22165394234 57353442460140 ...
6 | 1 2 8 128 29228 70197998 422059040480 5051078354829005 ...
7 | 1 2 8 128 32297 227731312 5686426671375 ...
...
The T(1,2) = 5 set systems are:
{},
{{1,2}},
{{1,2}, {2}},
{{1},{1,2}},
{{1}, {2}}.
PROG
(PARI)
WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); (vecsum(WeighT(v)) + 1)^k/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, 1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)}
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Jan 04 2020
STATUS
approved