A006080 Number of rooted projective plane trees with n nodes. (Formerly M1188)

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

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

Formula

Stockmeyer gives g.f.

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

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

Prog

(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

Crossrefs

Cf. A006079, A006081, A006082.

Sequence in context: A001430 A148073 A057513 * A287694 A148074 A130866

Adjacent sequences: A006077 A006078 A006079 * A006081 A006082 A006083

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved