# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a333940
Showing 1-1 of 1

%I A333940 #12 Apr 29 2020 18:19:31
%S A333940 1,1,1,2,1,2,1,3,1,2,2,4,1,2,1,5,1,2,2,4,1,4,2,7,1,2,1,4,1,2,1,7,1,2,
%T A333940 2,4,2,5,2,7,1,2,3,9,2,5,2,12,1,2,1,4,1,2,2,7,1,2,1,4,1,2,1,11,1,2,2,
%U A333940 4,2,5,2,7,1,4,4,11,2,5,2,12,1,2,2,4,1,7
%N A333940 Number of Lyndon factorizations of the k-th composition in standard order.
%C A333940 We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon factorization of a composition c is a multiset of compositions whose Lyndon product is c.
%C A333940 A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, 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.
%C A333940 Also the number of multiset partitions of the Lyndon-word factorization of the n-th composition in standard order.
%F A333940 For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A034691(n).
%e A333940 We have  a(300) = 5, because the 300th composition (3,2,1,3) has the following Lyndon factorizations:
%e A333940   ((3,2,1,3))
%e A333940   ((1,3),(3,2))
%e A333940   ((2),(3,1,3))
%e A333940   ((3),(2,1,3))
%e A333940   ((2),(3),(1,3))
%t A333940 stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A333940 lynprod[]:={};lynprod[{},b_List]:=b;lynprod[a_List,{}]:=a;lynprod[a_List]:=a;
%t A333940 lynprod[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{lynprod[{a},{x,b}],lynprod[{x,a},{b}]}]],{2,1},Prepend[lynprod[{a},{y,b}],x],{1,2},Prepend[lynprod[{x,a},{b}],y]];
%t A333940 lynprod[a_List,b_List,c__List]:=lynprod[a,lynprod[b,c]];
%t A333940 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A333940 dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
%t A333940 Table[Length[Select[dealings[stc[n]],lynprod@@#==stc[n]&]],{n,0,100}]
%Y A333940 The dual version is A333765.
%Y A333940 Binary necklaces are counted by A000031.
%Y A333940 Necklace compositions are counted by A008965.
%Y A333940 Necklaces covering an initial interval are counted by A019536.
%Y A333940 Lyndon compositions are counted by A059966.
%Y A333940 Numbers whose reversed binary expansion is a necklace are A328595.
%Y A333940 Numbers whose prime signature is a necklace are A329138.
%Y A333940 Length of Lyndon factorization of binary expansion is A211100.
%Y A333940 Length of co-Lyndon factorization of binary expansion is A329312.
%Y A333940 Length of co-Lyndon factorization of reversed binary expansion is A329326.
%Y A333940 Length of Lyndon factorization of reversed binary expansion is A329313.
%Y A333940 All of the following pertain to compositions in standard order (A066099):
%Y A333940 - Length is A000120.
%Y A333940 - Necklaces are A065609.
%Y A333940 - Sum is A070939.
%Y A333940 - Runs are counted by A124767.
%Y A333940 - Rotational symmetries are counted by A138904.
%Y A333940 - Strict compositions are A233564.
%Y A333940 - Constant compositions are A272919.
%Y A333940 - Lyndon compositions are A275692.
%Y A333940 - Co-Lyndon compositions are A326774.
%Y A333940 - Aperiodic compositions are A328594.
%Y A333940 - Reversed co-necklaces are A328595.
%Y A333940 - Length of Lyndon factorization is A329312.
%Y A333940 - Rotational period is A333632.
%Y A333940 - Co-necklaces are A333764.
%Y A333940 - Dealing are counted by A333939.
%Y A333940 - Reversed necklaces are A333943.
%Y A333940 - Length of co-Lyndon factorization is A334029.
%Y A333940 - Combinatory separations are A334030.
%Y A333940 Cf. A000740, A001037, A034691, A060223, A269134, A292884, A328596.
%K A333940 nonn
%O A333940 0,4
%A A333940 _Gus Wiseman_, Apr 13 2020

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE