login
Number of Lyndon words (aperiodic necklaces) with n beads of n colors.
6

%I #26 May 20 2019 02:45:53

%S 1,1,8,60,624,7735,117648,2096640,43046640,999989991,25937424600,

%T 743008120140,23298085122480,793714765724595,29192926025339776,

%U 1152921504338411520,48661191875666868480,2185911559727674682148,104127350297911241532840,5242879999999487999992020

%N Number of Lyndon words (aperiodic necklaces) with n beads of n colors.

%H Alois P. Heinz, <a href="/A075147/b075147.txt">Table of n, a(n) for n = 1..350</a>

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

%F a(n) = (1/n) * Sum_{d|n} mu(n/d)*n^d.

%F Asymptotic to n^(n-1) = A000169(n).

%F a(n) is the n-th term of the inverse Euler transform of j-> n^j. - _Alois P. Heinz_, Jun 23 2018

%F a(n) = [x^n] Sum_{k>=1} mu(k)*log(1/(1 - n*x^k))/k. - _Ilya Gutkovskiy_, May 20 2019

%p with(numtheory):

%p a:= n-> add(n^d *mobius(n/d), d=divisors(n))/n:

%p seq(a(n), n=1..25); # _Alois P. Heinz_, Dec 21 2014

%t Table[Total@Map[ MoebiusMu[#1] n^(n/#1 - 1) &, Divisors[n]], {n, 20}] (* _Olivier GĂ©rard_, Aug 05 2016 *)

%Y Main diagonal of A074650 and A143325.

%Y Cf. A008683, A306173.

%K nonn

%O 1,3

%A _Christian G. Bower_, Sep 04 2002