A006080 Number of rooted projective plane trees with n nodes.

1, 1, 2, 4, 9, 21, 56, 155, 469, 1480, 4882, 16545, 57384, 202060, 720526, 2593494, 9408469, 34350507, 126109784, 465200333, 1723346074, 6408356210, 23911272090, 89495909409, 335916761128, 1264114452996, 4768464309416, 18027250459483, 68291947831046, 259200707489634

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Number of rooted planar trees that can be turned over.

Also bracelets (or necklaces) with n-1 black beads and n-1 white beads such that the beads switch colors when bracelet is turned over.

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

• T. D. Noe, Table of n, a(n) for n=1..200
• 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
• Index entries for sequences related to rooted trees
• Index entries for sequences related to bracelets

Crossrefs

Cf. A006079, A006081, A006082.

Programs

Mathematica

a[n_] := Sum[ EulerPhi[(n-1)/k]*(Binomial[2*k, k]/(2*(n-1))), {k, Divisors[n-1]}]/2 + 2^(n-3); a[1] = 1; Table[a[n], {n, 1, 27}] (* From Jean-François Alcover, Apr 11 2012, from formula *)

PARI

C(n, k)=binomial(n, k);
A003239(n) = if(n<=0, n==0, sumdiv(n, d, eulerphi(n/d) * C(2*d, d)) / (2*n) );
a(n) = if ( n<=1, 1, A003239(n)/2 + 2^(n-2) );
/* Joerg Arndt, Jan 25 2013 */

Python

from sympy import binomial as C, totient, divisors
def a003239(n): return 1 if n<2 else sum([totient(n//d)*C(2*d, d) for d in divisors(n)])/(2*n)
def a(n): return 1 if n<2 else a003239(n)/2 + 2**(n - 2) # Indranil Ghosh, Apr 24 2017

Formula

Stockmeyer gives g.f.

a(n) = A003239(n)/2 + 2^(n-2). (n>=2) (corrected, Joerg Arndt, Jan 25 2013)

Extensions

More terms, formula and additional comments from Christian G. Bower, Dec 13 2001