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

%I #29 Sep 23 2023 13:46:49

%S 1,1,3,10,41,192,1025,6087,39754,282241,2159916,17691161,154192692,

%T 1423127819,13851559475,141670442163,1517880400352,16989834719706,

%U 198191448685735,2404300796114642,30273340418567819,394948562421362392,5330161943597341380,74307324695105372519

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

%C 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

%H Alois P. Heinz, <a href="/A116540/b116540.txt">Table of n, a(n) for n = 0..230</a>

%H P. J. Cameron, T. Prellberg and D. Stark, <a href="http://arxiv.org/abs/math/0510155">Asymptotics for incidence matrix classes</a>, arXiv:math/0510155 [math.CO], 2005-2006.

%H M. Klazar, <a href="http://arXiv.org/abs/math.CO/0305048">Extremal problems for ordered hypergraphs</a>, arXiv:math/0305048 [math.CO], 2003.

%H Gus Wiseman, <a href="https://plus.google.com/114451380451684885774/posts/ix4rbCCY9Dj">Four symmetric function identities</a>

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

%p b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(b(n-i*j,

%p min(n-i*j, i-1), k)*binomial(binomial(k, i)+j-1, j), j=0..n/i)))

%p end:

%p a:= n-> add(add(b(n$2, i)*(-1)^(k-i)*binomial(k, i), i=0..k), k=0..n):

%p seq(a(n), n=0..24); # _Alois P. Heinz_, Sep 13 2019

%t MSOSA[s_List] :=

%t MSOSA[s] = If[Length[s] === 0, {{}}, Module[{sbs, fms},

%t sbs = Rest[Subsets[Union[s]]];

%t fms =

%t Function[r,

%t Append[#, r] & /@

%t MSOSA[Fold[DeleteCases[#1, #2, {1}, 1] &, s, r]]] /@ sbs;

%t Select[Join @@ fms, OrderedQ]

%t ]];

%t mmallnorm[n_Integer] :=

%t Function[s, Array[Count[s, y_ /; y <= #] + 1 &, n]] /@

%t Subsets[Range[n - 1] + 1];

%t Array[Plus @@ Length /@ MSOSA /@ mmallnorm[#] &, 9]

%t (* _Gus Wiseman_, Oct 22 2015 *)

%o (PARI)

%o R(n, k)={Vec(-1 + 1/prod(j=1, k, (1 - x^j + O(x*x^n))^binomial(k, j) ))}

%o 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

%Y Cf. A049311, A101370.

%Y Row sums of A327117.

%K nonn

%O 0,3

%A _Vladeta Jovovic_, Mar 27 2006

%E a(0)=1 prepended and more terms added by _Alois P. Heinz_, Sep 13 2019