A330942 Array read by antidiagonals: A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with n ones in every column and columns in nonincreasing lexicographic order.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 7, 1, 1, 1, 8, 75, 32, 1, 1, 1, 16, 1105, 2712, 161, 1, 1, 1, 32, 20821, 449102, 116681, 842, 1, 1, 1, 64, 478439, 122886128, 231522891, 5366384, 4495, 1, 1, 1, 128, 12977815, 50225389432, 975712562347, 131163390878, 256461703, 24320, 1, 1

Offset: 0

Author

Andrew Howroyd, Jan 13 2020

Keywords

• nonn
• tabl

Comments

The condition that the columns be in nonincreasing order is equivalent to considering nonequivalent matrices up to permutation of columns.

A(n,k) is the number of labeled n-uniform hypergraphs with multiple edges allowed and with k edges and no isolated vertices. When n=2 these objects are multigraphs.

Examples

			Array begins:
============================================================
n\k | 0 1    2         3              4                5
----+-------------------------------------------------------
  0 | 1 1    1         1              1                1 ...
  1 | 1 1    2         4              8               16 ...
  2 | 1 1    7        75           1105            20821 ...
  3 | 1 1   32      2712         449102        122886128 ...
  4 | 1 1  161    116681      231522891     975712562347 ...
  5 | 1 1  842   5366384   131163390878 8756434117294432 ...
  6 | 1 1 4495 256461703 78650129124911 ...
  ...
The A(2,2) = 7 matrices are:
   [1 0]  [1 0]  [1 0]  [1 1]  [1 0]  [1 0]  [1 1]
   [1 0]  [0 1]  [0 1]  [1 0]  [1 1]  [0 1]  [1 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, A121316, A136246.

Columns k=0..3 are A000012, A000012, A226994, A137220.

The version with nonnegative integer entries is A331315.

Other variations considering distinct rows and columns and equivalence under different combinations of permutations of rows and columns are:

All solutions: A262809 (all), A331567 (distinct rows).

Up to row permutation: A188392, A188445, A331126, A331039.

Up to column permutation: this sequence, A331571, A331277, A331569.

Nonisomorphic: A331461, A331510, A331508, A331509.

Cf. A331638.

Programs

Mathematica

T[n_, k_] := With[{m = n k}, Sum[Binomial[Binomial[j, n] + k - 1, k] Sum[ (-1)^(i - j) Binomial[i, j], {i, j, m}], {j, 0, m}]];
Table[T[n - k, k], {n, 0, 9}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Apr 10 2020, from PARI *)

PARI

T(n, k)={my(m=n*k); sum(j=0, m, binomial(binomial(j, n)+k-1, 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-1, k) * (Sum_{i=j..n*k} (-1)^(i-j)*binomial(i,j)).

A(n, k) = Sum_{j=0..k} abs(Stirling1(k, j))*A262809(n, j)/k!.

A(n, k) = Sum_{j=0..k} binomial(k-1, k-j)*A331277(n, j).

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