A254036 - OEIS

%I #13 Jan 23 2015 22:40:02

%S 1,1,1,3,9,33,128,564,2681,13845,76661,453025,2839968,18805590

%N Number of Lyndon-Bell strings of length n.

%C a(n) is the number of length-n "growth-restricted" strings over the alphabet {0,1,...,n-1} that are also Lyndon words. A string is "growth restricted" if every letter is at most one more than the maximum of all preceding letters, and is enumerated by the Bell numbers (A000110). A string is "Lyndon" if it is lexicographically smaller than all its cyclic shifts.

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

%e For n = 3 we have a(3) = 3, since the 5 growth-restricted strings of length 3 are 000, 001, 010, 011, 012, and 000 and 010 are not Lyndon.

%Y Cf. A000110.

%K nonn,more

%O 0,4

%A _Jeffrey Shallit_, Jan 23 2015

%E a(12)-a(13) from _Alois P. Heinz_, Jan 23 2015