|
|
A005201
|
|
Total number of fixed points in trees with n nodes.
(Formerly M3803)
|
|
4
|
|
|
1, 0, 1, 1, 5, 10, 31, 72, 201, 509, 1374, 3587, 9647, 25686, 69348, 187052, 508480, 1384959, 3791466, 10407842, 28677319, 79231664, 219557624, 609922977, 1698526750, 4740469708, 13258136509, 37151664771, 104294992317, 293279485007
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f. satisfies A(x) = T(x)*(1-F(x^2))-F(x^2), where T(x) = x + x^2 + 2*x^3 + ... is g.f. for A000081, F(x) = x + 2*x^2 + 4*x^3 + 11*x^4 + ... is the g.f. for A005200.
|
|
MAPLE
|
# First form T(x) = g.f. for A000081 and F(x) = g.f. for A005200. Then:
t1 := subs(x=x^2, F); series(T*(1-t1)-t1, x, 31);
# second Maple program:
with(numtheory): t:= proc(n) option remember; local d, j; if n<1 then 0 elif n=1 then 1 else add(add(d*t(d), d=divisors(j)) *t(n-j), j=1..n-1)/ (n-1) fi end: f:= proc(n) option remember; t(n) +add((t(n-i) -t(n-2*i)) *f(i), i=0..n-1) end: t1 := n-> `if`(type(n, odd), 0, f(n/2)): a:= proc(n) t(n) -add(t(n-i) *t1(i), i=0..n) -t1(n) end: seq(a(n), n=1..50); # Alois P. Heinz, Sep 17 2008
|
|
MATHEMATICA
|
t[n_] := t[n] = If[n<1, 0, If[n == 1, 1, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]]; f[n_] := f[n] = t[n]+Sum[(t[n-i]-t[n-2*i])*f[i], {i, 0, n-1}]; t1[n_] := If[OddQ[n], 0, f[n/2]]; a[n_] := t[n]-Sum[t[n-i]*t1[i], {i, 0, n}]-t1[n]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Mar 24 2014, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|