A349001 The number of Lyndon words of size n from an alphabet of 5 letters and 1st and 2nd letter of the alphabet with equal frequency in the words.

1, 3, 4, 14, 46, 174, 656, 2640, 10790, 45340, 193600, 839820, 3686424, 16353924, 73187456, 330052646, 1498335650, 6841899606, 31404443032, 144814450188, 670552118244, 3116578216310, 14534401932712, 67992210407514, 318969964124256, 1500268062754830

Offset

0,2

Comments

Counts a subset of the Lyndon words in A001692. Here there is no requirement of how often the 3rd to 5th letter of the alphabet are in the admitted word, only on the frequency of the 1st and 2nd letter of the alphabet.

Let T(n,k,M) be the number of words of length n drawn from an alphabet of size M where the first k letters of the alphabet appear with the same frequency f in each word. Then T(n,k,M) = Sum_{f=0..floor(n/k)) (M-k)^(n-f*k) * Product_{i=0..k-1} binomial(n-i*f,f) and T(n,2,5) = A026375(n), T(n,3,6) = A294035(n), T(n,2,6)= A081671(n). Removing the words with cycles by the inclusion-exclusion principle by a Mobius Transform gives words of length n of that type without cycles and division through n the Lyndon words of that type. - R. J. Mathar, Nov 07 2021

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Index entries for sequences related to Lyndon words

Formula

n*a(n) = Sum_{d|n} mu(d)*A026375(n/d) where mu = A008683.

Example

Examples for the alphabet {0,1,2,3,4}:
a(0)=1 counts (), the empty word.
a(3)=14 counts (021) (031) (041) (012) (013) (223) (233) (243) (014) (224) (234) (334) (244) (344), words of length 3 where the letters 0 and the 1 occur both either not or once.
a(4)=46 counts (0011) (0221) (0321) (0421) (0231) (0331) (0431) (0241) (0341) (0441) (0212) (0312) (0412) (0122) (0132) (0142) (0213) (0313) (0413) (0123) (2223) (0133) (2233) (2333) (2433) (0143) (2243) (2343) (2443) (0214) (0314) (0414) (0124) (2224) (2324) (0134) (2234) (2334) (3334) (2434) (0144) (2244) (2344) (3344) (2444) (3444).

Prog

(PARI) a(n) = if(n>0, sumdiv(n, d, moebius(n/d)*sum(k=0, d, binomial(d, k)*binomial(2*k, k)))/n, n==0) \\ Andrew Howroyd, Jan 14 2023

Crossrefs

Cf. A022553 (alphabet of 2 letters), A290277 (of 3 letters), A060165 (of 4 letters), A026375.

Sequence in context: A081714 A117718 A268700 * A176857 A356463 A248152

Adjacent sequences: A348998 A348999 A349000 * A349002 A349003 A349004

Keyword

nonn

Author

R. J. Mathar, Nov 05 2021

Extensions

Terms a(16) and beyond from Andrew Howroyd, Jan 14 2023

Status

approved