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
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
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
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Corrected by F. Chapoton, Jul 26 2011
Confirmed and extended to n = 30 by N. J. A. Sloane, Jul 27 2011
STATUS
approved