cp's OEIS Frontend

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.

%I A318396 #13 Oct 31 2019 21:13:08
%S A318396 1,1,3,6,15,28,64,116,238,430,818,1426,2618,4439,7775,12993,22025,
%T A318396 35946,59507,95319,154073,243226,385192,598531,933096,1429794,2193699,
%U A318396 3322171,5027995,7524245,11253557,16661211,24637859,36130242,52879638,76830503,111422013,160505622
%N 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.
%C A318396 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.
%C A318396 From _Andrew Howroyd_, Oct 31 2019: (Start)
%C A318396 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.
%C A318396 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)
%H A318396 Andrew Howroyd, <a href="/A318396/b318396.txt">Table of n, a(n) for n = 0..100</a>
%H A318396 Manfred Krause, <a href="https://doi.org/10.2307%2F2975191">A simple proof of the Gale-Ryser theorem</a>, American Mathematical Monthly, 1996.
%H A318396 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Ryser_theorem">Gale-Ryser theorem</a>
%e A318396 The a(4) = 15 pairs of integer partitions:
%e A318396      4, 1111
%e A318396     22, 22
%e A318396     22, 211
%e A318396     22, 1111
%e A318396     31, 211
%e A318396     31, 1111
%e A318396    211, 22
%e A318396    211, 31
%e A318396    211, 211
%e A318396    211, 1111
%e A318396   1111, 4
%e A318396   1111, 22
%e A318396   1111, 31
%e A318396   1111, 211
%e A318396   1111, 1111
%e A318396 The a(4) = 15 combinatory separations:
%e A318396   1111<={1,1,1,1}
%e A318396   1112<={1,1,12}
%e A318396   1112<={1,1,1,1}
%e A318396   1122<={12,12}
%e A318396   1122<={1,1,12}
%e A318396   1122<={1,1,1,1}
%e A318396   1123<={1,123}
%e A318396   1123<={12,12}
%e A318396   1123<={1,1,12}
%e A318396   1123<={1,1,1,1}
%e A318396   1234<={1234}
%e A318396   1234<={1,123}
%e A318396   1234<={12,12}
%e A318396   1234<={1,1,12}
%e A318396   1234<={1,1,1,1}
%t A318396 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A318396 mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
%t A318396 strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
%t A318396 normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
%t A318396 Table[Length[Select[Union@@Table[{m,Sort[normize/@#]}&/@mps[m],{m,strnorm[n]}],And@@UnsameQ@@@#[[2]]&]],{n,6}]
%o A318396 (PARI)
%o A318396 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)
%o A318396 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
%o A318396 (PARI) \\ faster version.
%o A318396 a(n)={local(Cache=Map());
%o A318396   my(recurse(b, c, s, t)=my(hk=Vecsmall([b, c, s, t]), z);
%o A318396      if(!mapisdefined(Cache, hk, &z),
%o A318396        z = if(s, sum(i=1, min(s, b), sum(j=1, min(t-s+i, c), self()(i, j, s-i, t-j))),
%o A318396            if(t, sum(j=1, min(t, c), self()(b, j, s, t-j)), 1));
%o A318396        mapput(Cache, hk, z)); z);
%o A318396   recurse(n, n, n, n)
%o A318396 } \\ _Andrew Howroyd_, Oct 31 2019
%Y A318396 Cf. A000041, A000110, A001247, A007716, A008277, A029894, A049311, A059849, A116540, A181939, A265947, A269134, A318393, A318394, A327913.
%K A318396 nonn
%O A318396 0,3
%A A318396 _Gus Wiseman_, Aug 25 2018
%E A318396 Terms a(9) and beyond from _Andrew Howroyd_, Oct 31 2019