|
|
A331277
|
|
Array read by antidiagonals: A(n,k) is the number of binary matrices with k distinct columns and any number of nonzero rows with n ones in every column and columns in decreasing lexicographic order.
|
|
5
|
|
|
1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 6, 1, 1, 0, 1, 62, 31, 1, 1, 0, 1, 900, 2649, 160, 1, 1, 0, 1, 16824, 441061, 116360, 841, 1, 1, 0, 1, 384668, 121105865, 231173330, 5364701, 4494, 1, 1, 0, 1, 10398480, 49615422851, 974787170226, 131147294251, 256452714, 24319, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,13
|
|
COMMENTS
|
The condition that the columns be in decreasing order is equivalent to considering nonequivalent matrices with distinct columns up to permutation of columns.
A(n,k) is the number of labeled n-uniform hypergraphs with k edges and no isolated vertices. When n=2 these objects are graphs.
|
|
LINKS
|
|
|
FORMULA
|
A(n, k) = Sum_{j=0..n*k} binomial(binomial(j,n),k) * (Sum_{i=j..n*k} (-1)^(i-j)*binomial(i,j)).
A(n, k) = Sum_{j=0..k} Stirling1(k, j)*A262809(n, j)/k!.
A(n, k) = Sum_{j=0..k} (-1)^(k-j)*binomial(k-1, k-j)*A330942(n, j).
|
|
EXAMPLE
|
Array begins:
====================================================================
n\k | 0 1 2 3 4 5 6
----+---------------------------------------------------------------
0 | 1 1 0 0 0 0 0 ...
1 | 1 1 1 1 1 1 1 ...
2 | 1 1 6 62 900 16824 384668 ...
3 | 1 1 31 2649 441061 121105865 49615422851 ...
4 | 1 1 160 116360 231173330 974787170226 ...
5 | 1 1 841 5364701 131147294251 ...
6 | 1 1 4494 256452714 78649359753286 ...
...
The A(2,2) = 6 matrices are:
[1 0] [1 0] [1 0] [1 1] [1 0] [1 0]
[1 0] [0 1] [0 1] [1 0] [1 1] [0 1]
[0 1] [1 0] [0 1] [0 1] [0 1] [1 1]
[0 1] [0 1] [1 0]
|
|
PROG
|
(PARI) T(n, k)={my(m=n*k); sum(j=0, m, binomial(binomial(j, n), k)*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))}
|
|
CROSSREFS
|
The version with nonnegative integer entries is A331278.
The version with not necessarily distinct columns is A330942.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|