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

1, 1, 3, 10, 41, 192, 1025, 6087, 39754, 282241, 2159916, 17691161, 154192692, 1423127819, 13851559475, 141670442163, 1517880400352, 16989834719706, 198191448685735, 2404300796114642, 30273340418567819, 394948562421362392, 5330161943597341380, 74307324695105372519

Offset

0,3

Comments

Also number of normal set multipartitions of weight n. These are defined as multisets of sets that together partition a normal multiset of weight n, where a multiset is normal if it spans an initial interval of positive integers. Set multipartitions are involved in the expansion of elementary symmetric functions in terms of augmented monomial symmetric functions. - Gus Wiseman, Oct 22 2015

Links

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

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.

Gus Wiseman, Four symmetric function identities

Example

The a(3) = 10 normal set multipartitions are: {1,1,1}, {1,12}, {1,1,2}, {2,12}, {1,2,2}, {123}, {1,23}, {2,13}, {3,12}, {1,2,3}.

Maple

b:= proc(n, i, k) option remember; `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-1, 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..24);  # Alois P. Heinz, Sep 13 2019

Mathematica

MSOSA[s_List] :=
  MSOSA[s] = If[Length[s] === 0, {{}}, Module[{sbs, fms},
     sbs = Rest[Subsets[Union[s]]];
     fms =
      Function[r,
        Append[#, r] & /@
         MSOSA[Fold[DeleteCases[#1, #2, {1}, 1] &, s, r]]] /@ sbs;
     Select[Join @@ fms, OrderedQ]
     ]];
mmallnorm[n_Integer] :=
  Function[s, Array[Count[s, y_ /; y <= #] + 1 &, n]] /@
   Subsets[Range[n - 1] + 1];
Array[Plus @@ Length /@ MSOSA /@ mmallnorm[#] &, 9]
(* Gus Wiseman, Oct 22 2015 *)

Prog

(PARI)
R(n, k)={Vec(-1 + 1/prod(j=1, k, (1 - x^j + O(x*x^n))^binomial(k, j) ))}
seq(n) = {concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Sep 23 2023

Crossrefs

Cf. A049311, A101370.

Row sums of A327117.

Sequence in context: A140046 A260772 A325059 * A236407 A000248 A245504

Adjacent sequences: A116537 A116538 A116539 * A116541 A116542 A116543

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