A003120 Number of rooted trees with n nodes and omega-valency 1.

1, 1, 2, 3, 7, 13, 31, 66, 159, 365, 900, 2162, 5417, 13436, 34165, 86603, 223028, 574493, 1495524, 3900055, 10246172, 26982966, 71447432, 189664782, 505605729, 1351179886, 3623051567, 9737403960, 26243202664, 70878565004

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

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]

Other names: Number of arborescences of type (n,1), or tapeworms.

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]

Examples

			For n=4, the 3 rooted trees are
O     O       O
|    / \      |
|    |       / \
|
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• J.-C. Arditti, Dénombrement des arborescences dont le graphe de comparabilité est Hamiltonien, Discrete Math., 5 (1973), 189-200.
• F. Harary and R. W. Robinson, Tapeworms, Unpublished manuscript, circa 1973. (Annotated scanned copy)
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A193487, A193488, A193489, A193490, A193491.

Programs

Maple

(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.)
S:=x*y + x^2*y + 2*x^3*y + x^4*(3*y+y^2) + x^5*(7*y+y^2+y^3);
M:=30;
for n from 6 to M do
t5:=series(series(S,y,n),x,n+1);
t6:=add( subs(x=x^k,subs(y=y^k,t5))/k, k=1..n+1);
t7:=series(series(t6,y,n),x,n+1);
t8:=(x/y)*(exp(t7)-1);
t9:=series(series(t8,y,n),x,n+1);
xf1:=subs(y=0,series(t5/y,y,n));
t10:=series(series(xf1,y,n),x,n+1);
t11:=series(series(t9-x*t10,y,n),x,n+1);
t12:=series(series(t11+x*y*t10+x*y,y,n),x,n+1);
t13:=coeff(t12,x,n);
S:=S+x^n*t13;
od:
xf1:=subs(y=0,series(S/y,y,M+1));
series(%,x,M+1);
seriestolist(%);

Sage

def A003120_list(n):
    a = polygen(QQ, 'a')
    an = FractionField(a.parent())
    ri = PowerSeriesRing(an, 'x')
    x = ri.gen()
    t = ri.zero().O(1)
    v = ri.zero().O(1)
    for l in range(n):
        truc = ri.zero()
        for k in range(1, l + 1):
            truc += ri([u(a=a**k) for u in t(x**k).truncate(l+1)]) / k
        t = a*x+x*v+x*(t-v)/a-x/a*(t+1)+x*(exp(truc))/a
        v = a*ri([u(a=0) for u in t/a])
    return (v / a).coefficients()
A003120_list(33) # F. Chapoton, Jul 26 2011

Formula

The generating function is probably not rational. - F. Chapoton, Jul 26 2011

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

Extensions

Corrected by F. Chapoton, Jul 26 2011

Confirmed and extended to n = 30 by N. J. A. Sloane, Jul 27 2011