%I A007595 M2681
%S A007595 1,1,3,7,22,66,217,715,2438,8398,29414,104006,371516,1337220,
%T A007595 4847637,17678835,64823110,238819350,883634026,3282060210,
%U A007595 12233141908,45741281820,171529836218,644952073662,2430973304732
%N A007595 a(n) = C_n / 2 if n is even or ( C_n + C_((n-1)/2) ) / 2 if n is odd, 
               where C = Catalan numbers (A000108).
%C A007595 Number of necklaces of 2 colors with 2n beads and n-1 black ones. - Wouter 
               Meeussen (wouter.meeussen(AT)pandora.be), Aug 03 2002
%C A007595 Number of rooted planar binary trees up to reflection (trees with n internal 
               nodes, or a total of 2n+1 nodes). - Antti Karttunen, Aug 19 2002
%C A007595 Number of even permutations avoiding 132.
%C A007595 Number of Dyck paths of length 2n having an even number of peaks at even 
               height. Example: a(3)=3 because we have UDUDUD, U(UD)(UD)D and UUUDDD, 
               where U=(1,1), D=(1,-1) and the peaks at even height are shown between 
               parentheses. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 13 
               2004
%C A007595 Number of planar trees (A002995) on n edges with one distinguished edge. 
               - David Callan (callan(AT)stat.wisc.edu), Oct 08 2005
%D A007595 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A007595 P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 
               155-183.
%H A007595 T. D. Noe, <a href="b007595.txt">Table of n, a(n) for n=1..200</a>
%H A007595 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               Sequences realized by oligomorphic permutation groups</a>, J. Integ. 
               Seqs. Vol. 3 (2000), #00.1.5.
%H A007595 T. Mansour, <a href="http://arXiv.org/abs/math.CO/0211205">Counting occurrences 
               of 132 in an even permutation</a>.
%F A007595 G.f.: (2-2*x-sqrt(1-4*x)-sqrt(1-4*x^2))/x/4. - Vladeta Jovovic (vladeta(AT)eunet.rs), 
               Sep 26 2003
%p A007595 A007595 := n -> (1/2)*(Cat(n) + (`mod`(n,2)*Cat((n-1)/2))); Cat := n 
               -> binomial(2*n,n)/(n+1);
%t A007595 Table[(Plus@@(EulerPhi[ # ]Binomial[2n/#, (n-1)/# ] &)/@Intersection[Divisors[2n], 
               Divisors[n-1]])/(2n), {n, 2, 32}] or Table[If[EvenQ[n], cat[n]/2, 
               (cat[n] +cat[(n-1)/2])/2], {n, 24}] with cat[n]=A000108
%Y A007595 a(n)=A047996(2*n, n-1) for n>= 1 and a(n)=A072506(n, n-1) for n>=2. Occurs 
               in A073201 as the rows 0, 2, 4, etc. (with a(0)=1 included). Cf. 
               also A003444, A007123.
%Y A007595 Cf. A000150.
%Y A007595 Sequence in context: A092566 A036719 A166135 this_sequence A148681 A148682 
               A148683
%Y A007595 Adjacent sequences: A007592 A007593 A007594 this_sequence A007596 A007597 
               A007598
%K A007595 nonn,easy
%O A007595 1,3
%A A007595 N. J. A. Sloane (njas(AT)research.att.com).
%E A007595 Description corrected by Reiner Martin and Wouter Meeussen, Aug 04 2002.