A116539 Number of zero-one matrices with n ones and no zero rows or columns and with distinct rows, up to permutation of rows.

1, 1, 2, 7, 28, 134, 729, 4408, 29256, 210710, 1633107, 13528646, 119117240, 1109528752, 10889570768, 112226155225, 1210829041710, 13640416024410, 160069458445202, 1952602490538038, 24712910192430620, 323964329622503527, 4391974577299578248, 61488854148194151940

Offset

0,3

Comments

Also the number of labeled hypergraphs spanning an initial interval of positive integers with edge-sizes summing to n. - Gus Wiseman, Dec 18 2018

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

P. J. Cameron, T. Prellberg and D. Stark, Asymptotics for incidence matrix classes , arXiv:math/0510155 [math.CO], 2005-2006.

M. Klazar, Extremal problems for ordered hypergraphs, arXiv:math/0305048 [math.CO], 2003.

Example

From Gus Wiseman, Dec 18 2018: (Start)
The a(3) = 7 edge-sets:
    {{1,2,3}}
   {{1},{1,2}}
   {{2},{1,2}}
   {{1},{2,3}}
   {{2},{1,3}}
   {{3},{1,2}}
  {{1},{2},{3}}
Inequivalent representatives of the a(4) = 28 0-1 matrices:
  [1111]
.
  [100][1000][010][0100][001][0010][0001][110][110][1100][101][1010][1001]
  [111][0111][111][1011][111][1101][1110][101][011][0011][011][0101][0110]
.
  [10][100][100][1000][100][100][1000][1000][010][010][0100][0100][0010]
  [01][010][010][0100][001][001][0010][0001][001][001][0010][0001][0001]
  [11][101][011][0011][110][011][0101][0110][110][101][1001][1010][1100]
.
  [1000]
  [0100]
  [0010]
  [0001]
(End)

Maple

b:= proc(n, i, k) b(n, i, k):=`if`(n=0, 1, `if`(i<1, 0, add(b(n-i*j,
      min(n-i*j, i-1), k)*binomial(binomial(k, i), j), j=0..n/i)))
    end:
a:= n-> add(add(b(n$2, i)*(-1)^(k-i)*binomial(k, i), i=0..k), k=0..n):
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 13 2019

Mathematica

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, Min[n - i*j, i - 1], k]*Binomial[Binomial[k, i], j], {j, 0, n/i}]]];
a[n_] := Sum[Sum[b[n, n, i]*(-1)^(k-i)*Binomial[k, i], {i, 0, k}], {k, 0, n}];
a /@ Range[0, 23] (* Jean-François Alcover, Feb 25 2020, after Alois P. Heinz *)

Crossrefs

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

Cf. A049311, A058891, A101370, A255906, A283877, A306021, A319190.

Row sums of A326914 and of A326962.

Sequence in context: A052319 A127783 A297195 * A266467 A370509 A141318

Adjacent sequences: A116536 A116537 A116538 * A116540 A116541 A116542

Keyword

nonn

Author

Vladeta Jovovic, Mar 27 2006

Extensions

a(0)=1 prepended and more terms added by Alois P. Heinz, Sep 13 2019

Status

approved