login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005201 Total number of fixed points in trees with n nodes.
(Formerly M3803)
5
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

F. Harary and E. M. Palmer, Prob. 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 and Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 200 terms from T. D. Noe)

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);

# 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

Cf. A005200, A000081, A000055.

Sequence in context: A052648 A020995 A174467 * A221304 A094234 A052538

Adjacent sequences:  A005198 A005199 A005200 * A005202 A005203 A005204

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 04:03 EST 2018. Contains 299428 sequences. (Running on oeis4.)