%I A002995 M0805
%S A002995 1,1,1,1,2,3,6,14,34,95,280,854,2694,8714,28640,95640,323396,1105335,
%T A002995 3813798,13269146,46509358,164107650,582538732,2079165208,7457847082,
%U A002995 26873059986,97239032056,353218528324,1287658723550,4709785569184
%N A002995 Number of labeled planar trees (also called plane trees) with n nodes.
%C A002995 Noncrossing handshakes of 2(n-1) people (each using only one hand) on 
               round table, up to rotations - Antti Karttunen Sep 03 2000
%C A002995 a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes 
               with all cutpoints of separation degree 2, i.e. ones shared only 
               by two (cyclic) blocks. These are digraphs (without loops) that have 
               a unique Eulerian tour. Such digraphs with labeled nodes are enumerated 
               by A102693. - Valery A. Liskovets (liskov(AT)im.bas-net.by), Oct 
               19 2005
%D A002995 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like 
               Structures, Cambridge, 1998, pp. 285 (4.1.26), 291 (4.1.48)
%D A002995 A. Errara, De quelques problemes d'analysis situs, Comptes Rend. Congr. 
               Nat. Sci. Bruxelles, (1930), 106-110.
%D A002995 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 
               1973, p. 67, (3.3.26).
%D A002995 F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. 
               Math., 278 (1975), 322-335.
%D A002995 G. Labelle, Sur la symetrie et l'asymetrie des structures combinatoires. 
               Theor. Comput. Sci. 117, No. 1-2, 3-22 (1993).
%D A002995 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A002995 D. W. Walkup, The number of plane trees, Mathematika, vol. 19, No. 2 
               (1972), 200-204.
%H A002995 T. D. Noe, <a href="b002995.txt">Table of n, a(n) for n=0..200</a>
%H A002995 <a href="Sindx_Tra.html#trees">Index entries for sequences related to 
               trees</a>
%F A002995 G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. 
               of A000108(n-1).
%F A002995 a(n)=1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*C(2d, d)) - A000108(n-1)/2 
               + (if n is even) A000108(n/2-1)/2.
%p A002995 with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C 
               = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,
               unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) 
               / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) 
               - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); 
               # Ulrich Schimke, Apr 05 2002
%p A002995 with(combinat): with(numtheory): m := 2: for p from 2 to 28 do s1 := 
               0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/
               d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) 
               mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: 
               printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od : - 
               Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 01 2006
%Y A002995 Cf. A000108, A003239, A005354, A057502, A061417, A064640.
%Y A002995 Sequence in context: A032065 A099968 A010357 this_sequence A093467 A080408 
               A001420
%Y A002995 Adjacent sequences: A002992 A002993 A002994 this_sequence A002996 A002997 
               A002998
%K A002995 nonn,easy,nice
%O A002995 0,5
%A A002995 N. J. A. Sloane (njas(AT)research.att.com).
%E A002995 More terms, formula from Christian G. Bower (bowerc(AT)usa.net), Dec 
               15 1999.