|
|
A007562
|
|
Number of planted trees where non-root, non-leaf nodes an even distance from root are of degree 2.
(Formerly M0773)
|
|
32
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
There is no planted tree on one node by definition.
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
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
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]
|
|
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
|
|
EXAMPLE
|
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 + ...
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)
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)
|
|
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 *)
|
|
PROG
|
(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 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,eigen
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|