A005200 Total number of fixed points in rooted trees with n nodes. (Formerly M1247)

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, 2512115979800, 7304240074858

Offset

1,2

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, Probability that a point of a tree is fixed, Math. Proc. Camb. Phil. Soc. 85 (1979) 407-415.

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;
# second Maple program:
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); # Alois P. Heinz, Sep 16 2008

Mathematica

terms = 30; (* T = g.f. of A000081 *)
T[x_] = 0; Do[T[x_] = x*Exp[Sum[ T[x^k]/k, {k, 1, terms}]] + O[x]^(terms+1) // Normal, terms+1];
A[_] = 0; Do[A[x_] = T[x]*(1 + A[x] - A[x^2]) + O[x]^(terms+1) // Normal,
terms+1];
Drop[CoefficientList[A[x], x] , 1] (* Jean-François Alcover, Sep 30 2011, updated Jan 11 2018 *)
b[n_] := b[n] = Module[{d, j}, If[n<1, 0, If[n == 1, 1, Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1)]]]; a[n_] := a[n] = b[n] + Sum[ (b[n-i] - b[n-2*i])*a[i], {i, 0, n-1}]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 11 2015, after Alois P. Heinz *)

Crossrefs

Cf. A000081, A005201, A000055.

Sequence in context: A007048 A148132 A032101 * A148133 A148134 A151425

Adjacent sequences: A005197 A005198 A005199 * A005201 A005202 A005203

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved