A318396 Number of pairs of integer partitions (y, v) of n such that there exists a pair of set partitions of {1,...,n} with meet {{1},...,{n}}, the first having block sizes y and the second v.

1, 1, 3, 6, 15, 28, 64, 116, 238, 430, 818, 1426, 2618, 4439, 7775, 12993, 22025, 35946, 59507, 95319, 154073, 243226, 385192, 598531, 933096, 1429794, 2193699, 3322171, 5027995, 7524245, 11253557, 16661211, 24637859, 36130242, 52879638, 76830503, 111422013, 160505622

Offset: 0

Author

Gus Wiseman, Aug 25 2018

Keywords

• nonn

Comments

A multiset is normal if it spans an initial interval of positive integers, and strongly normal if in addition it has weakly decreasing multiplicities. a(n) is also the number of combinatory separations (see A269134 for definition) of strongly normal multisets of size n into normal sets.

From Andrew Howroyd, Oct 31 2019: (Start)

Also, the number of distinct unordered row and column sums of binary matrices without empty columns or rows and with a total of n ones. Only matrices in which both row and columns sums are weakly increasing need to be considered.

By the Gale-Ryser theorem this is equivalent to the number of pairs of integer partitions (y,v) of n with y dominating v. (End)

Examples

			The a(4) = 15 pairs of integer partitions:
     4, 1111
    22, 22
    22, 211
    22, 1111
    31, 211
    31, 1111
   211, 22
   211, 31
   211, 211
   211, 1111
  1111, 4
  1111, 22
  1111, 31
  1111, 211
  1111, 1111
The a(4) = 15 combinatory separations:
  1111<={1,1,1,1}
  1112<={1,1,12}
  1112<={1,1,1,1}
  1122<={12,12}
  1122<={1,1,12}
  1122<={1,1,1,1}
  1123<={1,123}
  1123<={12,12}
  1123<={1,1,12}
  1123<={1,1,1,1}
  1234<={1234}
  1234<={1,123}
  1234<={12,12}
  1234<={1,1,12}
  1234<={1,1,1,1}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..100
• Manfred Krause, A simple proof of the Gale-Ryser theorem, American Mathematical Monthly, 1996.
• Wikipedia, Gale-Ryser theorem

Crossrefs

Cf. A000041, A000110, A001247, A007716, A008277, A029894, A049311, A059849, A116540, A181939, A265947, A269134, A318393, A318394, A327913.

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
Table[Length[Select[Union@@Table[{m,Sort[normize/@#]}&/@mps[m],{m,strnorm[n]}],And@@UnsameQ@@@#[[2]]&]],{n,6}]

PARI

IsDom(p,q)=if(#q<#p, 0, my(s=0,t=0); for(i=0, #p-1, s+=p[#p-i]; t+=q[#q-i]; if(t>s, return(0))); 1)
a(n)={if(n<1, n==0, my(s=0); forpart(p=n, forpart(q=n, s+=IsDom(p,q), [1, p[#p]], [#p, n])); s)} \\ Andrew Howroyd, Oct 31 2019

PARI

\\ faster version.
a(n)={local(Cache=Map());
  my(recurse(b, c, s, t)=my(hk=Vecsmall([b, c, s, t]), z);
     if(!mapisdefined(Cache, hk, &z),
       z = if(s, sum(i=1, min(s, b), sum(j=1, min(t-s+i, c), self()(i, j, s-i, t-j))),
           if(t, sum(j=1, min(t, c), self()(b, j, s, t-j)), 1));
       mapput(Cache, hk, z)); z);
  recurse(n, n, n, n)
} \\ Andrew Howroyd, Oct 31 2019

Extensions

Terms a(9) and beyond from Andrew Howroyd, Oct 31 2019