A254036 Number of Lyndon-Bell strings of length n.

1, 1, 1, 3, 9, 33, 128, 564, 2681, 13845, 76661, 453025, 2839969, 18805657, 131020298, 957267541, 7313308052, 58274257913, 483216851547, 4161351882552, 37150641551094, 343261561413610, 3277653005298471, 32298890876004413, 328061896605786860, 3430576696925207946

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

Tim Peters, Table of n, a(n) for n = 0..33 (terms 0..29 from Martin Fuller).

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

Author

Jeffrey Shallit, Jan 23 2015

Extensions

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

a(12)-a(13) corrected and a(14)-a(19) added by Joerg Arndt, Apr 19 2025

a(20)-a(25) from Martin Fuller, Apr 22 2025

Status

approved