Return to Answer

A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words w.r.t. cyclic rotations. Then for enumeration of equivalent classes and Lyndon words with a given weight, we can employ PET as follows.

Let $E_{n,m}$ be the number of equivalence classes of words of length $n$ and weight $m$. Similatly, let $L_{n,m}$ be the number of Lyndon words of length $n$ and weight $m$. Then $$E_{n,m} = \sum_{k\mid \gcd(n,m)} L_{n/k,m/k}$$ and (using Möbius inversion) $$L_{n,m} = \sum_{k\mid \gcd(n,m)} \mu(k)\cdot E_{n/k,m/k}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. By PET, $E_{n,m}$ equals the coefficient of $t^m$ in $$Z_n(t^{d_a}+t^{d_b},t^{2d_a}+t^{2d_b},\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot (t^{kd_a}+t^{kd_b})^{n/k}.$$

It further follows that $L_{n,m}$ equals the coefficient of $t^m$ in $$\sum_{q\mid \gcd(n,m)} \mu(q)\cdot \frac{q}{n}\sum_{k\mid n/q} \varphi(k)\cdot (t^{qkd_a}+t^{qkd_b})^{n/(qk)}$$ $$= \frac{1}{n} \sum_{p\mid n} (t^{pd_a}+t^{pd_b})^{n/p} \sum_{q\mid \gcd(p,m)} \mu(q)\cdot q\cdot \varphi(p/q).$$ (here $p$ stands for $qk$)

UPDATE. From the generating functins above, we can derive explicit formulae (assuming $d_a<d_b$, without loss of generality): $$E_{n,m} = \frac{1}{n}\sum_{k\mid \gcd(n,m)} \varphi(k)\cdot \binom{\frac{n}{k}}{\frac{m-nd_a}{k(d_b-d_a)}}$$ and \begin{split} L_{n,m} &= \frac{1}{n} \sum_{p\mid \gcd(n,m)} \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}} \sum_{q\mid p} \mu(q)\cdot q\cdot \varphi(p/q) \\ &=\frac{1}{n} \sum_{p\mid \gcd(n,m)} \mu(p) \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}}. \end{split}

(where the binomial coefficients are zero whenever the lower index is negative or fractional)

A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words w.r.t. cyclic rotations. Then for enumeration of equivalent classes and Lyndon words with a given weight, we can employ PET as follows.

Let $E_{n,m}$ be the number of equivalence classes of words (both periodic and non-periodic) of length $n$ and weight $m$. Similatly, let $L_{n,m}$ be the number of Lyndon words of length $n$ and weight $m$. Then $$E_{n,m} = \sum_{k\mid \gcd(n,m)} L_{n/k,m/k}$$ and (using Möbius inversion) $$L_{n,m} = \sum_{k\mid \gcd(n,m)} \mu(k)\cdot E_{n/k,m/k}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. By PET, $E_{n,m}$ equals the coefficient of $t^m$ in $$Z_n(t^{d_a}+t^{d_b},t^{2d_a}+t^{2d_b},\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot (t^{kd_a}+t^{kd_b})^{n/k}.$$

It further follows that $L_{n,m}$ equals the coefficient of $t^m$ in $$\sum_{q\mid \gcd(n,m)} \mu(q)\cdot \frac{q}{n}\sum_{k\mid n/q} \varphi(k)\cdot (t^{qkd_a}+t^{qkd_b})^{n/(qk)}$$ $$= \frac{1}{n} \sum_{p\mid n} (t^{pd_a}+t^{pd_b})^{n/p} \sum_{q\mid \gcd(p,m)} \mu(q)\cdot q\cdot \varphi(p/q).$$ (here $p$ stands for $qk$)

UPDATE. From the generating functins above, we can derive explicit formulae (assuming $d_a<d_b$, without loss of generality): $$E_{n,m} = \frac{1}{n}\sum_{k\mid \gcd(n,m)} \varphi(k)\cdot \binom{\frac{n}{k}}{\frac{m-nd_a}{k(d_b-d_a)}}$$ and \begin{split} L_{n,m} &= \frac{1}{n} \sum_{p\mid \gcd(n,m)} \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}} \sum_{q\mid p} \mu(q)\cdot q\cdot \varphi(p/q) \\ &=\frac{1}{n} \sum_{p\mid \gcd(n,m)} \mu(p)\cdot \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}}. \end{split}

(where the binomial coefficients are zero whenever the lower index is negative or fractional)

A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words w.r.t. cyclic rotations. Then for enumeration of and equivalent classes and Lyndon words with a given weight, we can employ PET as follows.

Let $E_{n,m}$ be the number of equivalence classes of words of length $n$ and weight $m$. Similatly, let $L_{n,m}$ be the number of Lyndon words of length $n$ and weight $m$. Then $$E_{n,m} = \sum_{k\mid \gcd(n,m)} L_{n/k,m/k}$$ and (using Möbius inversion) $$L_{n,m} = \sum_{k\mid \gcd(n,m)} \mu(k)\cdot E_{n/k,m/k}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. Then $E_{n,m}$ equals the coefficient of $t^m$ in $$Z_n(t^{d_a}+t^{d_b},t^{2d_a}+t^{2d_b},\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot (t^{kd_a}+t^{kd_b})^{n/k}.$$

It further follows that $L_{n,m}$ equals the coefficient of $t^m$ in $$\sum_{q\mid \gcd(n,m)} \mu(q)\cdot \frac{q}{n}\sum_{k\mid n/q} \varphi(k)\cdot (t^{qkd_a}+t^{qkd_b})^{n/(qk)}$$ $$= \frac{1}{n} \sum_{p\mid n} (t^{pd_a}+t^{pd_b})^{n/p} \sum_{q\mid \gcd(p,m)} \mu(q)\cdot q\cdot \varphi(p/q).$$ (here $p$ stands for $qk$)

UPDATE. From the generating functins above, we can derive explicit formulae (assuming $d_a<d_b$, without loss of generality): $$E_{n,m} = \frac{1}{n}\sum_{k\mid \gcd(n,m)} \varphi(k)\cdot \binom{\frac{n}{k}}{\frac{m-nd_a}{k(d_b-d_a)}}$$ and \begin{split} L_{n,m} &= \frac{1}{n} \sum_{p\mid \gcd(n,m)} \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}} \sum_{q\mid p} \mu(q)\cdot q\cdot \varphi(p/q) \\ &=\frac{1}{n} \sum_{p\mid \gcd(n,m)} \mu(p) \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}}. \end{split}

(where the binomial coefficients ar zero whenever the lower index is negative or fractional)

A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words w.r.t. cyclic rotations. Then for enumeration of equivalent classes and Lyndon words with a given weight, we can employ PET as follows.

Let $E_{n,m}$ be the number of equivalence classes of words of length $n$ and weight $m$. Similatly, let $L_{n,m}$ be the number of Lyndon words of length $n$ and weight $m$. Then $$E_{n,m} = \sum_{k\mid \gcd(n,m)} L_{n/k,m/k}$$ and (using Möbius inversion) $$L_{n,m} = \sum_{k\mid \gcd(n,m)} \mu(k)\cdot E_{n/k,m/k}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. By PET, $E_{n,m}$ equals the coefficient of $t^m$ in $$Z_n(t^{d_a}+t^{d_b},t^{2d_a}+t^{2d_b},\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot (t^{kd_a}+t^{kd_b})^{n/k}.$$

It further follows that $L_{n,m}$ equals the coefficient of $t^m$ in $$\sum_{q\mid \gcd(n,m)} \mu(q)\cdot \frac{q}{n}\sum_{k\mid n/q} \varphi(k)\cdot (t^{qkd_a}+t^{qkd_b})^{n/(qk)}$$ $$= \frac{1}{n} \sum_{p\mid n} (t^{pd_a}+t^{pd_b})^{n/p} \sum_{q\mid \gcd(p,m)} \mu(q)\cdot q\cdot \varphi(p/q).$$ (here $p$ stands for $qk$)

UPDATE. From the generating functins above, we can derive explicit formulae (assuming $d_a<d_b$, without loss of generality): $$E_{n,m} = \frac{1}{n}\sum_{k\mid \gcd(n,m)} \varphi(k)\cdot \binom{\frac{n}{k}}{\frac{m-nd_a}{k(d_b-d_a)}}$$ and \begin{split} L_{n,m} &= \frac{1}{n} \sum_{p\mid \gcd(n,m)} \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}} \sum_{q\mid p} \mu(q)\cdot q\cdot \varphi(p/q) \\ &=\frac{1}{n} \sum_{p\mid \gcd(n,m)} \mu(p) \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}}. \end{split}

(where the binomial coefficients are zero whenever the lower index is negative or fractional)

A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words w.r.t. cyclic rotations. Then for enumeration of and equivalent classes and Lyndon words with a given weight, we can employ PET as follows.

Let $E_{n,m}$ be the number of equivalence classes of words of length $n$ and weight $m$. Similatly, let $L_{n,m}$ be the number of Lyndon words of length $n$ and weight $m$. Then $$E_{n,m} = \sum_{k\mid \gcd(n,m)} L_{n/k,m/k}$$ and (using Möbius inversion) $$L_{n,m} = \sum_{k\mid \gcd(n,m)} \mu(k)\cdot E_{n/k,m/k}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. Then $E_{n,m}$ equals the coefficient of $t^m$ in $$Z_n(t^{d_a}+t^{d_b},t^{2d_a}+t^{2d_b},\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot (t^{kd_a}+t^{kd_b})^{n/k}.$$

It further follows that $L_{n,m}$ equals the coefficient of $t^m$ in $$\sum_{q\mid \gcd(n,m)} \mu(q)\cdot \frac{q}{n}\sum_{k\mid n/q} \varphi(k)\cdot (t^{qkd_a}+t^{qkd_b})^{n/(qk)}$$ $$= \frac{1}{n} \sum_{p\mid n} (t^{pd_a}+t^{pd_b})^{n/p} \sum_{q\mid \gcd(p,m)} \mu(q)\cdot q\cdot \varphi(p/q).$$ (here $p$ stands for $qk$)

A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words w.r.t. cyclic rotations. Then for enumeration of and equivalent classes and Lyndon words with a given weight, we can employ PET as follows.

Let $E_{n,m}$ be the number of equivalence classes of words of length $n$ and weight $m$. Similatly, let $L_{n,m}$ be the number of Lyndon words of length $n$ and weight $m$. Then $$E_{n,m} = \sum_{k\mid \gcd(n,m)} L_{n/k,m/k}$$ and (using Möbius inversion) $$L_{n,m} = \sum_{k\mid \gcd(n,m)} \mu(k)\cdot E_{n/k,m/k}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. Then $E_{n,m}$ equals the coefficient of $t^m$ in $$Z_n(t^{d_a}+t^{d_b},t^{2d_a}+t^{2d_b},\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot (t^{kd_a}+t^{kd_b})^{n/k}.$$

It further follows that $L_{n,m}$ equals the coefficient of $t^m$ in $$\sum_{q\mid \gcd(n,m)} \mu(q)\cdot \frac{q}{n}\sum_{k\mid n/q} \varphi(k)\cdot (t^{qkd_a}+t^{qkd_b})^{n/(qk)}$$ $$= \frac{1}{n} \sum_{p\mid n} (t^{pd_a}+t^{pd_b})^{n/p} \sum_{q\mid \gcd(p,m)} \mu(q)\cdot q\cdot \varphi(p/q).$$ (here $p$ stands for $qk$)

UPDATE. From the generating functins above, we can derive explicit formulae (assuming $d_a<d_b$, without loss of generality): $$E_{n,m} = \frac{1}{n}\sum_{k\mid \gcd(n,m)} \varphi(k)\cdot \binom{\frac{n}{k}}{\frac{m-nd_a}{k(d_b-d_a)}}$$ and \begin{split} L_{n,m} &= \frac{1}{n} \sum_{p\mid \gcd(n,m)} \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}} \sum_{q\mid p} \mu(q)\cdot q\cdot \varphi(p/q) \\ &=\frac{1}{n} \sum_{p\mid \gcd(n,m)} \mu(p) \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}}. \end{split}

(where the binomial coefficients ar zero whenever the lower index is negative or fractional)