A334030 Number of combinatory separations of a multiset whose multiplicities are the parts of the n-th composition in standard order.

1, 1, 2, 2, 3, 4, 4, 3, 5, 7, 8, 8, 7, 9, 8, 5, 7, 12, 15, 14, 15, 17, 18, 13, 12, 17, 17, 16, 14, 16, 13, 7, 11, 19, 27, 26, 27, 37, 37, 25, 27, 37, 33, 34, 37, 40, 36, 22, 19, 32, 37, 33, 37, 38, 40, 28, 26, 33, 34, 30, 25, 28, 22, 11, 15, 30, 44, 42, 51, 68

Offset: 0

Author

Gus Wiseman, Apr 16 2020

Keywords

• nonn

Comments

A multiset is normal if it covers 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 (3,3,5,5,5,6) is (1,1,2,2,2,3).

A pair h<={g_1,...,g_k} is a combinatory separation iff there exists a multiset partition of h whose multiset of block-types is {g_1,...,g_k}. For example, the (headless) combinatory separations of the multiset (1122) are (1122), (1)(112), (1)(122), (11)(11), (12)(12), (1)(1)(11), (1)(1)(12), (1)(1)(1)(1). This list excludes (12)(11), because one cannot partition (1122) into two blocks where one block has two distinct elements and the other has two equal elements.

Examples

			The combinatory separations for n = 1, 3, 5, 9, 10, 13 (heads not shown):
  (1)  (12)    (112)      (1112)        (1122)        (1223)
       (1)(1)  (1)(11)    (1)(111)      (11)(11)      (1)(112)
               (1)(12)    (1)(112)      (1)(112)      (11)(12)
               (1)(1)(1)  (11)(12)      (1)(122)      (1)(122)
                          (1)(1)(11)    (12)(12)      (1)(123)
                          (1)(1)(12)    (1)(1)(11)    (12)(12)
                          (1)(1)(1)(1)  (1)(1)(12)    (1)(1)(11)
                                        (1)(1)(1)(1)  (1)(1)(12)
                                                      (1)(1)(1)(1)
		

Crossrefs

Multisets of compositions are A034691.

The described multiset is a row of A095684.

Combinatory separations of normal multisets are A269134.

Shuffles of compositions are counted by A292884.

Combinatory separations of prime indices are A318559.

The version for prime indices is A318560.

Combinatory separations of strongly normal multisets are A318563.

Multiset partitions of the described multiset are A333942.

All of the following pertain to compositions in standard order (A066099):

- Length is A000120.

- Sum is A070939.

- Strict compositions are A233564.

- Constant compositions are A272919.

- Length of Lyndon factorization is A329312.

- Dealings are counted by A333939.

Cf. A065609, A275692, A318284, A326774, A333764, A333765, A333940.

Programs

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
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]]]];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
ptnToNorm[y_]:=Join@@Table[ConstantArray[i,y[[i]]],{i,Length[y]}];
Table[Length[Union[Table[Sort[normize/@m],{m,mps[ptnToNorm[stc[n]]]}]]],{n,0,100}]