A317852 Number of plane trees with n nodes where the sequence of branches directly under any given node is aperiodic, meaning its cyclic permutations are all different.

1, 1, 1, 3, 8, 26, 76, 247, 783, 2565, 8447, 28256, 95168, 323720, 1108415, 3821144, 13246307, 46158480, 161574043, 567925140, 2003653016, 7092953340, 25186731980, 89690452750, 320221033370, 1146028762599, 4110596336036, 14774346783745, 53203889807764, 191934931634880

Offset

1,4

Comments

Also the number of plane trees with n nodes where the sequence of branches directly under any given node has relatively prime run-lengths.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Example

The a(5) = 8 locally aperiodic plane trees:
  ((((o)))),
  (((o)o)), ((o(o))), (((o))o), (o((o))),
  ((o)oo), (o(o)o), (oo(o)).
The a(6) = 26 locally aperiodic plane trees:
  (((((o)))))  ((((o)o)))  (((o)oo))  ((o)ooo)
               (((o(o))))  ((o(o)o))  (o(o)oo)
               ((((o))o))  ((oo(o)))  (oo(o)o)
               ((o((o))))  (((o)o)o)  (ooo(o))
               ((((o)))o)  ((o(o))o)
               (o(((o))))  (o((o)o))
               (((o))(o))  (o(o(o)))
               ((o)((o)))  (((o))oo)
                           (o((o))o)
                           (oo((o)))
                           ((o)(o)o)
                           ((o)o(o))
                           (o(o)(o))

Mathematica

aperQ[q_]:=Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
aperplane[n_]:=If[n==1, {{}}, Join@@Table[Select[Tuples[aperplane/@c], aperQ], {c, Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[aperplane[n]], {n, 10}]

Prog

(PARI)
Tfm(p, n)={sum(d=1, n, moebius(d)*(subst(1/(1+O(x*x^(n\d))-p), x, x^d)-1))}
seq(n)={my(p=O(1)); for(i=1, n, p=1+Tfm(x*p, i)); Vec(p)} \\ Andrew Howroyd, Feb 08 2020

Crossrefs

Cf. A000108, A000837, A007853, A032171, A032200, A254040, A301700, A303386, A303431, A304173, A304175, A317708, A317852.

Sequence in context: A281972 A355869 A343553 * A306485 A148801 A131910

Adjacent sequences: A317849 A317850 A317851 * A317853 A317854 A317855

Keyword

nonn

Author

Gus Wiseman, Sep 05 2018

Extensions

a(16)-a(17) from Robert Price, Sep 15 2018

Terms a(18) and beyond from Andrew Howroyd, Feb 08 2020

Status

approved