|
Search: id:A005200
|
|
|
| A005200 |
|
Total number of fixed points in rooted trees with n nodes.
(Formerly M1247)
|
|
+0
6
|
|
| 1, 2, 4, 11, 28, 78, 213, 598, 1670, 4723, 13356, 37986, 108193, 309169, 884923, 2538369, 7292170, 20982220, 60451567, 174385063, 503600439, 1455827279, 4212464112, 12199373350, 35357580112, 102552754000, 297651592188, 864460682777
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
F. Harary and E. M. Palmer, Probability that a point of a tree is fixed, Math. Proc. Camb. Phil. Soc. 85 (1979) 407-415.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..200
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
|
|
FORMULA
|
G.f. satisfies A(x)=T(x)[ 1+A(x)-A(x^2) ], where T(x)=x+x^2+2*x^3+... is g.f. for A000081.
|
|
MAPLE
|
# First construct T(x), the g.f. for A000081. Then we form A005200 = s and its g.f. A as follows:
s := [ 1, 2 ]; A := series(add(s[ i ]*x^i, i=1..2), x, 3); G := series(subs(x=x^2, A), x, 3);
for n from 3 to 30 do t1 := coeff(T, x, n)+add( coeff(T, x, i)*s[ n-i ], i=1..n-1)-add(coeff(T, x, i)*coeff(G, x, n-i), i=1..n-1); s := [ op(s), t1 ]; A := series(A+t1*x^n, x, n+1); G := series(subs(x=x^2, A), x, n+1); od: s; A;
with (numtheory): b:= proc(n) option remember; local d, j; if n<1 then 0 elif n=1 then 1 else add (add (d*b(d), d=divisors(j)) *b(n-j), j=1..n-1)/ (n-1) fi end: a:= proc(n) option remember; b(n) +add ((b(n-i) -b(n-2*i)) *a(i), i=0..n-1) end: seq (a(n), n=1..100); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 16 2008]
|
|
CROSSREFS
|
Cf. A000081, A005201, A000055.
Sequence in context: A007048 A148132 A032101 this_sequence A148133 A148134 A151425
Adjacent sequences: A005197 A005198 A005199 this_sequence A005201 A005202 A005203
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
