login
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.
4

%I #50 Feb 08 2020 20:41:49

%S 1,1,1,3,8,26,76,247,783,2565,8447,28256,95168,323720,1108415,3821144,

%T 13246307,46158480,161574043,567925140,2003653016,7092953340,

%U 25186731980,89690452750,320221033370,1146028762599,4110596336036,14774346783745,53203889807764,191934931634880

%N 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.

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

%H Andrew Howroyd, <a href="/A317852/b317852.txt">Table of n, a(n) for n = 1..200</a>

%e The a(5) = 8 locally aperiodic plane trees:

%e ((((o)))),

%e (((o)o)), ((o(o))), (((o))o), (o((o))),

%e ((o)oo), (o(o)o), (oo(o)).

%e The a(6) = 26 locally aperiodic plane trees:

%e (((((o))))) ((((o)o))) (((o)oo)) ((o)ooo)

%e (((o(o)))) ((o(o)o)) (o(o)oo)

%e ((((o))o)) ((oo(o))) (oo(o)o)

%e ((o((o)))) (((o)o)o) (ooo(o))

%e ((((o)))o) ((o(o))o)

%e (o(((o)))) (o((o)o))

%e (((o))(o)) (o(o(o)))

%e ((o)((o))) (((o))oo)

%e (o((o))o)

%e (oo((o)))

%e ((o)(o)o)

%e ((o)o(o))

%e (o(o)(o))

%t aperQ[q_]:=Array[RotateRight[q,#]&,Length[q],1,UnsameQ];

%t aperplane[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[aperplane/@c],aperQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];

%t Table[Length[aperplane[n]],{n,10}]

%o (PARI)

%o Tfm(p, n)={sum(d=1, n, moebius(d)*(subst(1/(1+O(x*x^(n\d))-p), x, x^d)-1))}

%o seq(n)={my(p=O(1)); for(i=1, n, p=1+Tfm(x*p, i)); Vec(p)} \\ _Andrew Howroyd_, Feb 08 2020

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

%K nonn

%O 1,4

%A _Gus Wiseman_, Sep 05 2018

%E a(16)-a(17) from _Robert Price_, Sep 15 2018

%E Terms a(18) and beyond from _Andrew Howroyd_, Feb 08 2020