cp's OEIS Frontend

A269134 Number of combinatory separations of normal multisets of weight n.

%I A269134 #21 Mar 22 2025 11:40:44
%S A269134 1,4,14,57,223,948,3940,16994,72964,317959,1385592,6085763,26738139,
%T A269134 117939291,520553999,2301781692,10181786176,45074744448,199558036891,
%U A269134 883670342156,3912320450786
%N A269134 Number of combinatory separations of normal multisets of weight n.
%C A269134 A multiset is normal if it spans an initial interval of positive integers. The type of a multiset of integers is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of 335556 is 112223.
%C A269134 If and only if there exists a multiset partition p whose multiset union has type h and where g = {g_1,...,g_n} is the multiset of types of the blocks of p, there exists a *combinatory separation* which is regarded as a multi-arrow p:h<=g. For example 1122<={12,11} is *not* a combinatory separation because one cannot partition a multiset of type 1122 into two blocks where one block has two distinct elements and the other block has two equal elements. Normal multisets N and combinatory separations S comprise a multi-order (N,S). The value of a(n) is the total number of *distinct* combinatory separations h<=g where h has weight n.
%C A269134 The term "combinatory separation" is inspired by MacMahon's inscrutable "Combinatory Analysis" (1915) which states: "A partition of any number is "separated" into "separates" by writing down a set [sic] of partitions, each partition in its own brackets, from left to right so that when all of the parts of these partitions are assembled in a single bracket, the partition separated is reproduced."
%H A269134 Martin Fuller, <a href="/A269134/a269134.cpp.txt">C++ program</a>
%H A269134 Gus Wiseman, <a href="https://docs.google.com/document/d/1m0s6DGTBkDW9gvMuFmJHvy6oLGRAbQ7okAZcOPZawp0/pub">Comcategories and Multiorders</a> <a href="http://www.nafindix.com/math/academic/ComcategoriesandMultiordersv7.pdf">(pdf version)</a>
%e A269134 For a(3) the 14 distinct combinatory separations grouped according to head are: 111<={111}, 111<={1,11}, 111<={1,1,1}; 112<={112}, 112<={1,11}, 112<={1,12}, 112<={1,1,1}; 122<={122}, 122<={1,11}, 122<={1,12}, 122<={1,1,1}; 123<={123}, 123<={1,12}, 123<={1,1,1}.
%e A269134 Note that in this enumeration the two multiset partitions {{1},{2,3}}:123<={1,12} and {{1,2},{3}}:123<={1,12} do not represent distinct multi-arrows and consequently are counted only once, whereas the two multiset partitions {{1},{1,2}}:112<={1,12} and {{1,2},{2}}:122<={1,12} are counted separately even though they have the same multiset of block-types.
%t A269134 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A269134 mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
%t A269134 allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t A269134 normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
%t A269134 Table[Length[Union@@Table[{m,Sort[normize/@#]}&/@mps[m],{m,allnorm[n]}]],{n,7}] (* _Gus Wiseman_, Aug 29 2018 *)
%Y A269134 Cf. A255906 (multiset partitions of normal multisets of weight n), A096443 (multiset partitions of multiset class representatives), A007716 (non-isomorphic multiset partitions of weight n).
%Y A269134 Cf. A034691, A318396, A318559, A318560, A318562, A318563, A318567.
%K A269134 nonn,more
%O A269134 1,2
%A A269134 _Gus Wiseman_, Feb 20 2016
%E A269134 a(9) from _Gus Wiseman_, Aug 29 2018
%E A269134 a(10) from _Robert Price_, Sep 14 2018
%E A269134 a(11)-a(21) from _Martin Fuller_, Mar 22 2025