A003120 Number of rooted trees with n nodes and omega-valency 1. (Formerly M0836)

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,3

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]

References

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

Links

Table of n, a(n) for n=1..30.

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

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

Example

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

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(%);

Prog

(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

Crossrefs

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

Sequence in context: A002013 A171416 A193530 * A032131 A324844 A007827

Adjacent sequences: A003117 A003118 A003119 * A003121 A003122 A003123

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

Corrected by F. Chapoton, Jul 26 2011

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

Status

approved