A005201 Total number of fixed points in trees with n nodes.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

Crossrefs

Cf. A005200, A000081, A000055.

Programs

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

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.