A329141 Number of Lyndon compositions of n that are not weakly increasing.

0, 0, 0, 0, 0, 1, 4, 11, 28, 60, 131, 263, 530, 1029, 2009, 3853, 7414, 14152, 27105, 51755, 99069, 189558, 363468, 697302, 1340220, 2578362, 4968001, 9582682, 18508226, 35784670, 69266825, 134207336, 260290846, 505274108, 981691926

Offset: 1

Author

Gus Wiseman, Nov 10 2019

Keywords

• nonn

Comments

A Lyndon composition of n is a finite sequence of positive integers summing to n that is lexicographically strictly less than all of its cyclic rotations.

Examples

			The a(6) = 1 through a(8) = 11 compositions:
  (132)  (142)    (143)
         (1132)   (152)
         (1213)   (1142)
         (11212)  (1214)
                  (1232)
                  (1322)
                  (11132)
                  (11213)
                  (11312)
                  (12122)
                  (111212)
		

Crossrefs

Lyndon compositions are A059966.

Lyndon compositions that are weakly increasing are A167934.

Binary Lyndon words are A001037.

Necklace compositions are A008965.

Cf. A000031, A000740, A178472, A318731, A328596, A329131, A329145.

Programs

Mathematica

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!OrderedQ[#]&&neckQ[#]&&aperQ[#]&]],{n,10}]

Formula

a(n) = A059966(n) - A167934(n).