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

Author

Vladeta Jovovic, Mar 27 2006

Keywords

• nonn

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

Examples

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

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

Crossrefs

Cf. A049311, A101370.

Row sums of A327117.

Programs

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

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

Extensions

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