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

Author

Gus Wiseman, Sep 05 2018

Keywords

• nonn

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.

Examples

			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))
		

Links

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

Crossrefs

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

Programs

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}]

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

Extensions

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

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