A005201 - OEIS

A005201

Total number of fixed points in trees with n nodes.
(Formerly M3803)

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

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 200 terms from T. D. Noe)

F. Harary and E. M. Palmer, The probability that a point of a tree is fixed, Math. Proc. Camb. Phil. Soc. 85(1979) 407-415.

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

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