A254036 Number of Lyndon-Bell strings of length n.

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

Offset

0,4

Comments

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.

Links

Table of n, a(n) for n=0..13.

Index entries for sequences related to Lyndon words

Example

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.

Crossrefs

Cf. A000110.

Sequence in context: A049162 A049176 A049151 * A151039 A151040 A151041

Adjacent sequences: A254033 A254034 A254035 * A254037 A254038 A254039

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 23 2015

Extensions

a(12)-a(13) from Alois P. Heinz, Jan 23 2015

Status

approved