|
Search: id:A005201
|
|
|
| A005201 |
|
Total number of fixed points in trees with n nodes.
(Formerly M3803)
|
|
+0
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; listen)
|
|
|
OFFSET
|
1,5
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
F. Harary and E. M. Palmer, Prob. that a point of a tree is fixed, Math. Proc. Camb. Phil. Soc. 85(1979) 407-415.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..200
Index entries for sequences related to trees
|
|
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 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);
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); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 17 2008]
|
|
CROSSREFS
|
Cf. A005200, A000081, A000055.
Sequence in context: A032296 A052648 A020995 this_sequence A094234 A052538 A073705
Adjacent sequences: A005198 A005199 A005200 this_sequence A005202 A005203 A005204
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
