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