|
%I M3803 #35 Oct 27 2023 19:33:59
%S 1,0,1,1,5,10,31,72,201,509,1374,3587,9647,25686,69348,187052,508480,
%T 1384959,3791466,10407842,28677319,79231664,219557624,609922977,
%U 1698526750,4740469708,13258136509,37151664771,104294992317,293279485007
%N Total number of fixed points in trees with n nodes.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A005201/b005201.txt">Table of n, a(n) for n = 1..1000</a> (first 200 terms from T. D. Noe)
%H F. Harary and E. M. Palmer, <a href="https://doi.org/10.1017/S0305004100055857">The probability that a point of a tree is fixed</a>, Math. Proc. Camb. Phil. Soc. 85(1979) 407-415.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F 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.
%p # First form T(x) = g.f. for A000081 and F(x) = g.f. for A005200. Then:
%p t1 := subs(x=x^2,F); series(T*(1-t1)-t1, x,31);
%p # second Maple program:
%p 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
%t 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_ *)
%Y Cf. A005200, A000081, A000055.
%K nonn,easy,nice
%O 1,5
%A _N. J. A. Sloane_
|
