login
Number of multiset partitions of a multiset whose multiplicities are the parts of the n-th composition in standard order.
4

%I #6 Apr 16 2020 18:48:48

%S 1,1,2,2,3,4,4,5,5,7,9,11,7,11,11,15,7,12,16,21,16,26,26,36,12,21,26,

%T 36,21,36,36,52,11,19,29,38,31,52,52,74,29,52,66,92,52,92,92,135,19,

%U 38,52,74,52,92,92,135,38,74,92,135,74,135,135,203,15,30,47

%N Number of multiset partitions of a multiset whose multiplicities are the parts of the n-th composition in standard order.

%C A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

%F a(n) = A001055(A057335(n)).

%e The a(1) = 1 through a(11) = 11 multiset partitions:

%e {1} {11} {12} {111} {112} {122} {123}

%e {1}{1} {1}{2} {1}{11} {1}{12} {1}{22} {1}{23}

%e {1}{1}{1} {2}{11} {2}{12} {2}{13}

%e {1}{1}{2} {1}{2}{2} {3}{12}

%e {1}{2}{3}

%e {1111} {1112} {1122} {1123}

%e {1}{111} {1}{112} {1}{122} {1}{123}

%e {11}{11} {11}{12} {11}{22} {11}{23}

%e {1}{1}{11} {2}{111} {12}{12} {12}{13}

%e {1}{1}{1}{1} {1}{1}{12} {2}{112} {2}{113}

%e {1}{2}{11} {1}{1}{22} {3}{112}

%e {1}{1}{1}{2} {1}{2}{12} {1}{1}{23}

%e {2}{2}{11} {1}{2}{13}

%e {1}{1}{2}{2} {1}{3}{12}

%e {2}{3}{11}

%e {1}{1}{2}{3}

%t stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t ptnToNorm[y_]:=Join@@Table[ConstantArray[i,y[[i]]],{i,Length[y]}];

%t facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];

%t Table[Length[facs[Times@@Prime/@ptnToNorm[stc[n]]]],{n,0,30}]

%Y The described multiset has A000120 distinct parts.

%Y The sum of the described multiset is A029931.

%Y Multisets of compositions are A034691.

%Y The described multiset is a row of A095684.

%Y Combinatory separations of normal multisets are A269134.

%Y The product of the described multiset is A284001.

%Y The version for prime indices is A318284.

%Y The version counting combinatory separations is A334030.

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

%Y - Length is A000120.

%Y - Sum is A070939.

%Y - Strict compositions are A233564.

%Y - Constant compositions are A272919.

%Y - Length of Lyndon factorization is A329312.

%Y - Dealings are counted by A333939.

%Y - Distinct parts are counted by A334028.

%Y - Length of co-Lyndon factorization is A334029.

%Y Cf. A057335, A065609, A275692, A292884, A318560, A318563, A326774, A333764, A333765, A333940.

%K nonn

%O 0,3

%A _Gus Wiseman_, Apr 16 2020