cp's OEIS Frontend

A007562 Number of planted trees where non-root, non-leaf nodes an even distance from root are of degree 2.

%I A007562 M0773 #58 Jun 11 2021 18:25:47
%S A007562 1,1,1,2,3,6,10,20,36,72,137,275,541,1098,2208,4521,9240,19084,39451,
%T A007562 82113,171240,358794,753460,1587740,3353192,7100909,15067924,32044456,
%U A007562 68272854,145730675,311575140,667221030,1430892924,3072925944,6607832422,14226665499
%N A007562 Number of planted trees where non-root, non-leaf nodes an even distance from root are of degree 2.
%C A007562 There is no planted tree on one node by definition.
%C A007562 Column k=2 of A144018. - _Alois P. Heinz_, Oct 17 2012
%C A007562 It appears that a(n) is also the number of locally non-intersecting unlabeled rooted trees with n nodes, where a tree is locally non-intersecting if the branches directly under of any non-leaf node have empty intersection. - _Gus Wiseman_, Aug 22 2018
%D A007562 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007562 Alois P. Heinz, <a href="/A007562/b007562.txt">Table of n, a(n) for n = 1..1000</a>
%H A007562 M. Bernstein and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0205301">Some canonical sequences of integers</a>, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
%H A007562 M. Bernstein and N. J. A. Sloane, <a href="/A003633/a003633_1.pdf">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
%H A007562 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A007562 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A007562 Shifts left 2 places under Euler transform.
%F A007562 G.f.: x + x^2 / (Product_{k>0} (1 - x^k)^a(k)). - _Michael Somos_, Oct 06 2003
%F A007562 a(n) ~ c * d^n / n^(3/2), where d = 2.246066877341161662499621547921... and  c = 0.68490297576105466417608032... . - _Vaclav Kotesovec_, Jun 23 2014
%F A007562 G.f. A(x) satisfies: A(x) = x + x^2 * exp(A(x) + A(x^2)/2 + A(x^3)/3 + A(x^4)/4 + ...). - _Ilya Gutkovskiy_, Jun 11 2021
%e A007562 G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 10*x^7 + 20*x^8 + 36*x^9 + ...
%e A007562 From _Joerg Arndt_, Jun 23 2014: (Start)
%e A007562 The a(8) = 20 such trees have the following level sequences:
%e A007562 01:  [ 0 1 2 3 4 3 2 1 ]
%e A007562 02:  [ 0 1 2 3 3 3 2 1 ]
%e A007562 03:  [ 0 1 2 3 3 2 2 1 ]
%e A007562 04:  [ 0 1 2 3 3 2 1 1 ]
%e A007562 05:  [ 0 1 2 3 2 3 2 1 ]
%e A007562 06:  [ 0 1 2 3 2 2 2 1 ]
%e A007562 07:  [ 0 1 2 3 2 2 1 1 ]
%e A007562 08:  [ 0 1 2 3 2 1 2 1 ]
%e A007562 09:  [ 0 1 2 3 2 1 1 1 ]
%e A007562 10:  [ 0 1 2 2 2 2 2 1 ]
%e A007562 11:  [ 0 1 2 2 2 2 1 1 ]
%e A007562 12:  [ 0 1 2 2 2 1 2 1 ]
%e A007562 13:  [ 0 1 2 2 2 1 1 1 ]
%e A007562 14:  [ 0 1 2 2 1 2 2 1 ]
%e A007562 15:  [ 0 1 2 2 1 2 1 1 ]
%e A007562 16:  [ 0 1 2 2 1 1 1 1 ]
%e A007562 17:  [ 0 1 2 1 2 1 2 1 ]
%e A007562 18:  [ 0 1 2 1 2 1 1 1 ]
%e A007562 19:  [ 0 1 2 1 1 1 1 1 ]
%e A007562 20:  [ 0 1 1 1 1 1 1 1 ]
%e A007562 Successive levels change by at most 1 and the last level is 1, compare to the example in A000081.
%e A007562 (End)
%e A007562 From _Gus Wiseman_, Aug 22 2018: (Start)
%e A007562 The a(7) = 10 locally non-intersecting trees:
%e A007562   (o(o(oo)))
%e A007562   (o(oo(o)))
%e A007562   (o(oooo))
%e A007562   (oo(o(o)))
%e A007562   (oo(ooo))
%e A007562   (o(o)(oo))
%e A007562   (ooo(oo))
%e A007562   (oo(o)(o))
%e A007562   (oooo(o))
%e A007562   (oooooo)
%e A007562 (End)
%p A007562 with(numtheory): etr:= proc(p) local b; b:= proc(n) option remember; if n=0 then 1 else (add(d*p(d), d=divisors(n)) +add(add(d*p(d), d= divisors(j)) *b(n-j), j=1..n-1))/n fi end end: b:= etr(a): a:= n-> `if`(n<=1, n, b(n-2)): seq(a(n), n=1..40);  # _Alois P. Heinz_, Sep 06 2008
%t A007562 etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, (Sum[ Sum[ d*p[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}] + Sum[ d*p[d], {d, Divisors[n]}])/n]; b]; b = etr[a]; a[n_] := If[n <= 1, n, b[n-2]]; Table[a[n], {n, 1, 36}] (* _Jean-François Alcover_, Aug 01 2013, after _Alois P. Heinz_ *)
%t A007562 purt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Intersection@@#=={}&],{ptn,IntegerPartitions[n-1]}]];
%t A007562 Table[Length[purt[n]],{n,10}] (* _Gus Wiseman_, Aug 22 2018 *)
%o A007562 (PARI) {a(n) = local(A); if( n<2, n>0, A = x / (1 - x) + O(x^n); for(k=2, n-2, A /= (1 - x^k + O(x^n))^polcoeff(A, k-1)); polcoeff(A, n-1))}; /* _Michael Somos_, Oct 06 2003 */
%Y A007562 Cf. A000081, A000837, A004111, A007560, A144018, A289509, A316470, A316473, A316475.
%K A007562 nonn,nice,eigen
%O A007562 1,4
%A A007562 _N. J. A. Sloane_
%E A007562 Better description from _Christian G. Bower_, May 15 1998