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.

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

Offset: 0

Author

Andrew Howroyd, Jan 13 2020

Keywords

• nonn
• tabl

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.

Examples

			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]
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325

Crossrefs

Rows n=1..3 are A000012, A121251, A136245.

Columns k=0..3 are A000012, A000012, A047665, A137219.

The version with nonnegative integer entries is A331278.

The version with not necessarily distinct columns is A330942.

Cf. A262809 (unrestricted version), A331315, A331639.

Programs

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)))}

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

A331639(n) = Sum_{d|n} A(n/d, d).