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

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

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

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

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.

Sequence in context: A166141 A087253 A197686 * A369458 A257936 A348039

Adjacent sequences: A331274 A331275 A331276 * A331278 A331279 A331280

Keyword

nonn,tabl

Author

Andrew Howroyd, Jan 13 2020

Status

approved