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