cp's OEIS Frontend

A006080 Number of rooted projective plane trees with n nodes.

%I A006080 M1188 #33 May 16 2025 00:55:00
%S A006080 1,1,2,4,9,21,56,155,469,1480,4882,16545,57384,202060,720526,2593494,
%T A006080 9408469,34350507,126109784,465200333,1723346074,6408356210,
%U A006080 23911272090,89495909409,335916761128,1264114452996,4768464309416,18027250459483,68291947831046,259200707489634
%N A006080 Number of rooted projective plane trees with n nodes.
%C A006080 Number of rooted planar trees that can be turned over.
%C A006080 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.
%D A006080 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A006080 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.
%H A006080 T. D. Noe, <a href="/A006080/b006080.txt">Table of n, a(n) for n=1..200</a>
%H A006080 P. J. Stockmeyer, <a href="/A006078/a006078.pdf">The charm bracelet problem and its applications</a>, 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]
%H A006080 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A006080 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A006080 <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>
%F A006080 Stockmeyer gives g.f.
%F A006080 a(n) = A003239(n)/2 + 2^(n-2). (n>=2) (corrected, _Joerg Arndt_, Jan 25 2013)
%t A006080 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 *)
%o A006080 (PARI)
%o A006080 C(n, k)=binomial(n, k);
%o A006080 A003239(n) = if(n<=0, n==0, sumdiv(n, d, eulerphi(n/d) * C(2*d, d)) / (2*n) );
%o A006080 a(n) = if ( n<=1, 1, A003239(n)/2 + 2^(n-2) );
%o A006080 /* _Joerg Arndt_, Jan 25 2013 */
%o A006080 (Python)
%o A006080 from sympy import binomial as C, totient, divisors
%o A006080 def a003239(n): return 1 if n<2 else sum([totient(n//d)*C(2*d, d) for d in divisors(n)])/(2*n)
%o A006080 def a(n): return 1 if n<2 else a003239(n)/2 + 2**(n - 2) # _Indranil Ghosh_, Apr 24 2017
%Y A006080 Cf. A006079, A006081, A006082.
%K A006080 nonn,nice
%O A006080 1,3
%A A006080 _N. J. A. Sloane_
%E A006080 More terms, formula and additional comments from _Christian G. Bower_, Dec 13 2001