%I M0836 #106 Apr 13 2022 13:25:16
%S 1,1,2,3,7,13,31,66,159,365,900,2162,5417,13436,34165,86603,223028,
%T 574493,1495524,3900055,10246172,26982966,71447432,189664782,
%U 505605729,1351179886,3623051567,9737403960,26243202664,70878565004
%N Number of rooted trees with n nodes and omega-valency 1.
%C Draw the tree with the root at the bottom. The omega-valency of a leaf is 1; the omega-valency of any other vertex v is max(1,sum(omega-valence(s))-1) where the sum is over the vertices directly above v. Then the omega-valency of the tree itself is the omega-valency of the root. [_F. Chapoton_, Jul 25 2011; _N. J. A. Sloane_, Jul 27 2011]
%C Other names: Number of arborescences of type (n,1), or tapeworms.
%C Let phi_n denote the number of rooted trees on n nodes whose comparability graph is Hamiltonian. Then phi_1=1, phi_n = a(n-1) for n >= 2. [Arditti]
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H J.-C. Arditti, <a href="http://dx.doi.org/10.1016/0012-365X(73)90135-0">Dénombrement des arborescences dont le graphe de comparabilité est Hamiltonien</a>, Discrete Math., 5 (1973), 189-200.
%H F. Harary and R. W. Robinson, <a href="/A001333/a001333_2.pdf">Tapeworms</a>, Unpublished manuscript, circa 1973. (Annotated scanned copy)
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F The generating function is probably not rational. - _F. Chapoton_, Jul 26 2011
%F The g.f. -(z-1)*(3*z**2+z-1)/(-1+3*z+z**2-7*z**3+3*z**4) conjectured by _Simon Plouffe_ in his 1992 dissertation is wrong (starting from index 11).
%e For n=4, the 3 rooted trees are
%e O O O
%e | / \ |
%e | | / \
%e |
%p (Maple program from _N. J. A. Sloane_, Jul 27 2011, based on Eq. (2) of the Arditti paper. This proceeds in very small steps because I was trying to isolate the error in that formula. The error turns out to be in the display following (2): this is not phi(x). Otherwise Eq. (2) is correct.)
%p S:=x*y + x^2*y + 2*x^3*y + x^4*(3*y+y^2) + x^5*(7*y+y^2+y^3);
%p M:=30;
%p for n from 6 to M do
%p t5:=series(series(S,y,n),x,n+1);
%p t6:=add( subs(x=x^k,subs(y=y^k,t5))/k, k=1..n+1);
%p t7:=series(series(t6,y,n),x,n+1);
%p t8:=(x/y)*(exp(t7)-1);
%p t9:=series(series(t8,y,n),x,n+1);
%p xf1:=subs(y=0,series(t5/y,y,n));
%p t10:=series(series(xf1,y,n),x,n+1);
%p t11:=series(series(t9-x*t10,y,n),x,n+1);
%p t12:=series(series(t11+x*y*t10+x*y,y,n),x,n+1);
%p t13:=coeff(t12,x,n);
%p S:=S+x^n*t13;
%p od:
%p xf1:=subs(y=0,series(S/y,y,M+1));
%p series(%,x,M+1);
%p seriestolist(%);
%o (Sage)
%o def A003120_list(n):
%o a = polygen(QQ, 'a')
%o an = FractionField(a.parent())
%o ri = PowerSeriesRing(an, 'x')
%o x = ri.gen()
%o t = ri.zero().O(1)
%o v = ri.zero().O(1)
%o for l in range(n):
%o truc = ri.zero()
%o for k in range(1, l + 1):
%o truc += ri([u(a=a**k) for u in t(x**k).truncate(l+1)]) / k
%o t = a*x+x*v+x*(t-v)/a-x/a*(t+1)+x*(exp(truc))/a
%o v = a*ri([u(a=0) for u in t/a])
%o return (v / a).coefficients()
%o A003120_list(33) # _F. Chapoton_, Jul 26 2011
%Y Cf. A193487, A193488, A193489, A193490, A193491.
%K nonn,nice,easy
%O 1,3
%A _N. J. A. Sloane_
%E Corrected by _F. Chapoton_, Jul 26 2011
%E Confirmed and extended to n = 30 by _N. J. A. Sloane_, Jul 27 2011