A006081 Number of line-rooted projective plane trees with n nodes.

1, 1, 3, 6, 17, 44, 133, 404, 1319, 4392, 15114, 52796, 187410, 671848, 2430509, 8852584, 32438603, 119463056, 441926206, 1641246060, 6117011262, 22871513128, 85766691938, 322479555096, 1215493792902, 4591852445104, 17383416640308, 65937045017304

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..1000
• P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
• Index entries for sequences related to trees

Crossrefs

Cf. A000108, A001405. - Alois P. Heinz, Feb 03 2009

Programs

Maple

b:= proc(n) option remember; binomial(n, floor(n/2)) end: c:= proc(n) option remember; binomial(2*n, n) /(n+1) end: a:= proc(m) local n; n:=m-2; (add(c(k)*c(n-k) +b(k)*b(n-k), k=0..n)) /4 +`if`(irem(n,2)=0, c(n/2)/2, 0) end: seq(a(n), n=2..30); # Alois P. Heinz, Feb 03 2009

Mathematica

b[n_] := Binomial[n, Floor[n/2]]; c[n_] := Binomial[2n, n]/(n+1); a[m_] := (n = m-2; Sum[c[k]*c[n-k] + b[k]*b[n-k], {k, 0, n}]/4 + If[Mod[n, 2] == 0, c[n/2]/2, 0]); Table[a[n], {n,2,30}] (* Jean-François Alcover, Jul 20 2011, after Alois P. Heinz *)

Formula

Stockmeyer gives g.f.

a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 12 2014

Extensions

More terms from Alois P. Heinz, Feb 03 2009