OFFSET
1,4
COMMENTS
Also the number of locally Lyndon plane trees with n nodes, where a plane tree is locally Lyndon if the sequence of branches directly under any given node is a Lyndon word. - Gus Wiseman, Sep 05 2018
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
Wikipedia, Lyndon word
FORMULA
Shifts left under "CHK" (necklace, identity, unlabeled) transform.
From Petros Hadjicostas, Dec 03 2017: (Start)
a(n+1) = (1/n)*Sum_{d|n} mu(n/d)*c(d), where c(n) = n*a(n) + Sum_{s=1..n-1} c(s)*a(n-s) with a(1) = c(1) = 1.
G.f.: If A(x) = Sum_{n>=1} a(n)*x^n, then Sum_{n>=1} a(n+1)*x^n = -Sum_{n>=1} (mu(n)/n)*log(1-A(x^n)).
The g.f. of the auxiliary sequence (c(n): n>=1) is C(x) = Sum_{n>=1} c(n)*x^n = x*(dA(x)/dx)/(1-A(x)) = x + 3*x^2 + 7*x^3 + 19*x^4 + 51*x^5 + 147*x^6 + 414*x^7 + 1203*x^8 + ...
(End)
EXAMPLE
From Gus Wiseman, Sep 05 2018: (Start)
The a(6) = 10 locally Lyndon plane trees:
(((((o)))))
(((o(o))))
((o((o))))
(o(((o))))
((o)((o)))
((oo(o)))
(o(o(o)))
(oo((o)))
(o(o)(o))
(ooo(o))
(End)
MATHEMATICA
T[n_, k_] := Module[{A}, A[_, _] = 0; If[k < 1 || k > n, 0, For[j = 1, j <= n, j++, A[x_, y_] = x*y - x*Sum[MoebiusMu[i]/i * Log[1 - A [x^i, y^i]] + O[x]^j // Normal , {i, 1, j}]]; Coefficient[Coefficient[A[x, y], x, n], y, k]]];
a[n_] := a[n] = Sum[T[n, k], {k, 1, n}];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 28}] (* Jean-François Alcover, Jun 30 2017, using Michael Somos' code for A055363 *)
LyndonQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And]&&Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
lynplane[n_]:=If[n==1, {{}}, Join@@Table[Select[Tuples[lynplane/@c], LyndonQ], {c, Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[lynplane[n]], {n, 10}] (* Gus Wiseman, Sep 05 2018 *)
PROG
(PARI)
CHK(p, n)={sum(d=1, n, moebius(d)/d*log(subst(1/(1+O(x*x^(n\d))-p), x, x^d)))}
seq(n)={my(p=O(1)); for(i=1, n, p=1+CHK(x*p, i)); Vec(p)} \\ Andrew Howroyd, Jun 20 2018
CROSSREFS
KEYWORD
nonn,eigen
AUTHOR
STATUS
approved