A007562 Number of planted trees where non-root, non-leaf nodes an even distance from root are of degree 2.
1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 137, 275, 541, 1098, 2208, 4521, 9240, 19084, 39451, 82113, 171240, 358794, 753460, 1587740, 3353192, 7100909, 15067924, 32044456, 68272854, 145730675, 311575140, 667221030, 1430892924, 3072925944, 6607832422, 14226665499
Offset: 1
Examples
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 + ... From _Joerg Arndt_, Jun 23 2014: (Start) The a(8) = 20 such trees have the following level sequences: 01: [ 0 1 2 3 4 3 2 1 ] 02: [ 0 1 2 3 3 3 2 1 ] 03: [ 0 1 2 3 3 2 2 1 ] 04: [ 0 1 2 3 3 2 1 1 ] 05: [ 0 1 2 3 2 3 2 1 ] 06: [ 0 1 2 3 2 2 2 1 ] 07: [ 0 1 2 3 2 2 1 1 ] 08: [ 0 1 2 3 2 1 2 1 ] 09: [ 0 1 2 3 2 1 1 1 ] 10: [ 0 1 2 2 2 2 2 1 ] 11: [ 0 1 2 2 2 2 1 1 ] 12: [ 0 1 2 2 2 1 2 1 ] 13: [ 0 1 2 2 2 1 1 1 ] 14: [ 0 1 2 2 1 2 2 1 ] 15: [ 0 1 2 2 1 2 1 1 ] 16: [ 0 1 2 2 1 1 1 1 ] 17: [ 0 1 2 1 2 1 2 1 ] 18: [ 0 1 2 1 2 1 1 1 ] 19: [ 0 1 2 1 1 1 1 1 ] 20: [ 0 1 1 1 1 1 1 1 ] Successive levels change by at most 1 and the last level is 1, compare to the example in A000081. (End) From _Gus Wiseman_, Aug 22 2018: (Start) The a(7) = 10 locally non-intersecting trees: (o(o(oo))) (o(oo(o))) (o(oooo)) (oo(o(o))) (oo(ooo)) (o(o)(oo)) (ooo(oo)) (oo(o)(o)) (oooo(o)) (oooooo) (End)
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..1000
- M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
- M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
- N. J. A. Sloane, Transforms
- Index entries for sequences related to rooted trees
Programs
-
Maple
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
-
Mathematica
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 *) purt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Intersection@@#=={}&],{ptn,IntegerPartitions[n-1]}]]; Table[Length[purt[n]],{n,10}] (* Gus Wiseman, Aug 22 2018 *) -
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 */
Formula
Shifts left 2 places under Euler transform.
G.f.: x + x^2 / (Product_{k>0} (1 - x^k)^a(k)). - Michael Somos, Oct 06 2003
a(n) ~ c * d^n / n^(3/2), where d = 2.246066877341161662499621547921... and c = 0.68490297576105466417608032... . - Vaclav Kotesovec, Jun 23 2014
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
Extensions
Better description from Christian G. Bower, May 15 1998
Comments