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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005200 Total number of fixed points in rooted trees with n nodes.
(Formerly M1247)
8
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 (list; graph; refs; listen; history; text; internal format)
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 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 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

max = 30; sol[m_] := (c[0] = 0; f81[x_] := Sum[c[k]*x^k, {k, 0, m}]; cc = CoefficientList[Series[f81[x] - x*Exp[Sum[f81[x^k]/k, {k, 1, m}]], {x, 0, m}], x]; sc = First[Solve[Thread[cc == 0]]]; t[x_] := f81[x] /. sc; f[x_] := Sum[b[k]*x^k, {k, 0, m}]; b[0] = 0; bb = CoefficientList[Series[f[x] - t[x]*(1 + f[x] - f[x^2]), {x, 0, m}], x]; sb = First[Solve[Thread[bb == 0]]]; Apply[Set, sc, {1}]; Apply[Set, sb, {1}]); Do[sol[m], {m, 5, max, 5}]; Drop[CoefficientList[f[x] /. sb, x], 1] (* Jean-François Alcover, Sep 30 2011 *)

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

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 December 16 08:07 EST 2017. Contains 296076 sequences.