|
%I M2681 #84 Dec 31 2022 01:33:08
%S 1,1,3,7,22,66,217,715,2438,8398,29414,104006,371516,1337220,4847637,
%T 17678835,64823110,238819350,883634026,3282060210,12233141908,
%U 45741281820,171529836218,644952073662,2430973304732,9183676536076,34766775829452,131873975875180
%N 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 Number of necklaces of 2 colors with 2n beads and n-1 black ones. - _Wouter Meeussen_, Aug 03 2002
%C 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 Number of even permutations avoiding 132.
%C 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_, Nov 13 2004
%C Number of planar trees (A002995) on n edges with one distinguished edge. - _David Callan_, Oct 08 2005
%C Assuming offset 0 this is an analog of A275165: pairs of two Catalan nestings with index sum n. - _R. J. Mathar_, Jul 19 2016
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A007595/b007595.txt">Table of n, a(n) for n=1..200</a>
%H Peter J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a> Quart. J. Math. Oxford Ser., Vol. 38, No. 2 (1987), pp. 155-183. Note that line 3 on p. 163 has a typo. - _N. J. A. Sloane_, Apr 18 2014
%H Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seq., Vol. 3 (2000), Article 00.1.5.
%H Paul Drube and Puttipong Pongtanapaisan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Drube/drube3.html">Annular Non-Crossing Matchings</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.2.4.
%H Andrew Gainer-Dewar, <a href="http://arxiv.org/abs/1401.6202">Pólya theory for species with an equivariant group action</a>, arXiv preprint arXiv:1401.6202 [math.CO], 2014.
%H Toufik Mansour, <a href="https://arxiv.org/abs/math/0211205">Counting occurrences of 132 in an even permutation</a>, arXiv:math/0211205 [math.CO], 2002.
%H Krishna Menon and Anurag Singh, <a href="https://arxiv.org/abs/2212.13794">Grassmannian permutations avoiding identity</a>, arXiv:2212.13794 [math.CO], 2022.
%F G.f.: (2-2*x-sqrt(1-4*x)-sqrt(1-4*x^2))/x/4. - _Vladeta Jovovic_, Sep 26 2003
%F D-finite with recurrence: n*(n+1)*a(n) -6*n*(n-1)*a(n-1) +4*(2*n^2-10*n+9)*a(n-2) +8*(n^2+n-9)*a(n-3) -48*(n-3)*(n-4)*a(n-4) +32*(2*n-9)*(n-5)*a(n-5)=0. - _R. J. Mathar_, Jun 03 2014, adapted to offset Feb 20 2020
%F a(n) ~ 4^n /(2*sqrt(Pi)*n^(3/2)). - _Ilya Gutkovskiy_, Jul 19 2016
%F a(2n) = A000150(2n). - _R. J. Mathar_, Jul 19 2016
%F a(n) = (A000108(n) + 2^n * binomial(1/2, (n+1)/2) * sin(Pi*n/2))/2. - _Vladimir Reshetnikov_, Oct 03 2016
%F Sum_{n>=1} a(n)/4^n = (3-sqrt(3))/2 (A334843). - _Amiram Eldar_, Mar 20 2022
%p A007595 := n -> (1/2)*(Cat(n) + (`mod`(n,2)*Cat((n-1)/2))); Cat := n -> binomial(2*n,n)/(n+1);
%t Table[(Plus@@(EulerPhi[ # ]Binomial[2n/#, (n-1)/# ] &)/@Intersection[Divisors[2n], Divisors[n-1]])/(2n), {n, 2, 32}] (* or *) Table[If[EvenQ[n], CatalanNumber[n]/2, (CatalanNumber[n] + CatalanNumber[(n-1)/2])/2], {n, 24}]
%t Table[(CatalanNumber[n] + 2^n Binomial[1/2, (n + 1)/2] Sin[Pi n/2])/2, {n, 1, 20}] (* _Vladimir Reshetnikov_, Oct 03 2016 *)
%t Table[If[EvenQ[n],CatalanNumber[n]/2,(CatalanNumber[n]+CatalanNumber[(n-1)/2])/2],{n,30}] (* _Harvey P. Dale_, Sep 06 2021 *)
%o (PARI) catalan(n) = binomial(2*n, n)/(n+1);
%o a(n) = if (n % 2, (catalan(n) + catalan((n-1)/2))/2, catalan(n)/2); \\ _Michel Marcus_, Jan 23 2016
%Y a(n) = A047996(2*n, n-1) for n >= 1 and a(n) = A072506(n, n-1) for n >= 2.
%Y Occurs in A073201 as rows 0, 2, 4, etc. (with a(0)=1 included).
%Y Cf. also A003444, A007123.
%Y Cf. A000108, A000150, A334843.
%K nonn,easy
%O 1,3
%A _N. J. A. Sloane_
%E Description corrected by _Reiner Martin_ and _Wouter Meeussen_, Aug 04 2002
|
