|
%I #92 Mar 06 2023 12:57:14
%S 1,1,7,66,715,8398,104006,1337220,17678835,238819350,3282060210,
%T 45741281820,644952073662,9183676536076,131873975875180,
%U 1907493251046152,27767032438524099,406472021074865382,5979899192930226746,88366931393503350700,1311063521138246054410
%N a(n) = ((2n+1) + (2n-1) - 1)!/((2n+1)!*(2n-1)!).
%C A Catalan-like formula using consecutive odd numbers. Recall that Catalan numbers (A000108) are given by ((n+1)+(n)-1)!/((n+1)!(n)!).
%C From _David Callan_, Jun 01 2006: (Start)
%C a(n) = number of Dyck (2n)-paths (i.e., semilength = 2n) all of whose interior returns to ground level (if any) occur at or before the (2n-2)-nd step, that is, they occur strictly before the midpoint of the path.
%C For example, a(2)=7 counts UUUUDDDD, UUUDUDDD, UUDUUDDD, UUDUDUDD, UUUDDUDD, UD.UUUDDD, UD.UUDUDD ("." denotes an interior return to ground level).
%C This result follows immediately from an involution on Dyck paths, due to Emeric Deutsch, defined by E->E, UPDQ -> UQDP (where E is the empty Dyck path; U=upstep, D=downstep and P,Q are arbitrary Dyck paths), because the involution is fixed-point-free on Dyck (2n)-paths and contains one path of the type being counted in each orbit.
%C a(n) = Sum_{k=0..n-1} C(2n-1-2k)*C(2k). This identity has the following combinatorial interpretation:
%C a(n) is the number of odd-GL-marked Dyck (2n-1)-paths. An odd-GL vertex is a vertex at location (2i,0) for some odd i >= 1 (path starts at origin). An odd-GL-marked Dyck path is a Dyck path with one of its odd-GL vertices marked. For example, a(2)=7 counts UUUDDD*, UUDUDD*, UD*UUDD, UDUUDD*, UD*UDUD, UDUDUD*, UUDDUD* (the * denotes the marked odd-GL vertex). (End)
%C a(n+1) = Sum_{k=0..n} C(k)*C(2*n+1-k), n >= 0, with C(n) = A000108(n), also gives the odd part of the bisection of the half-convolution of the Catalan sequence A000108 with itself. For the definition of the half-convolution of a sequence with itself see a comment on A201204. There one also finds the rule for the o.g.f. given below in the formula section. The even part of this bisection is found under A201205. - _Wolfdieter Lang_, Jan 05 2012
%C From _Peter Bala_, Dec 01 2015: (Start)
%C Let x = p/q be a positive rational in reduced form with p,q > 0. Define Cat(x) = (1/(2*p + q))*binomial(2*p + q, p). Then Cat(n) = Catalan(n). This sequence is Cat(n + 1/2) = (1/(4*n + 4))*binomial(4*n + 4, 2*n + 1). Cf. A265101 (Cat(n + 1/3), A265102 (Cat(n + 1/4)) and A265103 (Cat(n + 1/5)).
%C Number of maximal faces of the rational associahedron Ass(2*n + 1, 2*n + 3). Number of lattice paths from (0, 0) to (2*n + 3, 2*n + 1) using steps of the form (1, 0) and (0, 1) and staying above the line y = (2*n + 1)/(2*n + 3)*x. See Armstrong et al. (End)
%C Also the number of ordered rooted trees with 2n nodes, most of which are leaves, i.e., the odd bisection of A358585. This follows from Callan's formula below. - _Gus Wiseman_, Nov 27 2022
%H Alois P. Heinz, <a href="/A065097/b065097.txt">Table of n, a(n) for n = 0..834</a> (terms n = 1..100 from Harry J. Smith)
%H D. Armstrong, B. Rhoades, and N. Williams, <a href="http://arxiv.org/abs/1305.7286">Rational associahedra and noncrossing partitions</a> arxiv:1305.7286 [math.CO], 2008.
%H Emeric Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00370-7">An involution on Dyck paths and its consequences</a>, Discrete Math., 204 (1999), no. 1-3, 163-166.
%F a(n) = binomial(4*n-1, 2*n-1)/(2*n+1).
%F a(n) = C(2n)/2 where C(n) is the Catalan number A000108. - _David Callan_, Jun 01 2006
%F G.f.: 1/2 + (sqrt(2)/2)/sqrt(1+sqrt(1-16*x)). - _Vladeta Jovovic_, Sep 26 2003
%F G.f.: 1 + 3F2([1, 5/4, 7/4], [2, 5/2], 16*x). - _Olivier Gérard_, Feb 16 2011
%F O.g.f.: (1 + (cata(sqrt(x)) + cata(-sqrt(x)))/2)/2, with the o.g.f. cata(x) of the Catalan numbers. See the W. Lang comment above. - _Wolfdieter Lang_, Jan 05 2012
%F a(n) = hypergeometric([1-2*n,-2*n],[2],1)/2. - _Peter Luschny_, Sep 22 2014
%F a(n) = A001448(n) / (4*n + 2) if n>0. - _Michael Somos_, Oct 25 2014
%F n*(2*n+1)*a(n) - 2*(4*n-1)*(4*n-3)*a(n-1) = 0. - _R. J. Mathar_, Oct 31 2015
%F O.g.f. is 1 + Revert( x*(1 + x)/(1 + 2*x)^4 ). - _Peter Bala_, Dec 01 2015
%F Sum_{n>=0} 1/a(n) = 39/25 + 4*Pi/(9*sqrt(3)) - 24*log(phi)/(25*sqrt(5)), where phi is the golden ratio (A001622). - _Amiram Eldar_, Mar 02 2023
%e G.f.: 1 + x + 7*x^2 + 66*x^3 + 715*x^4 + 8398*x^5 + 104006*x^6 + ...
%p seq(binomial(4*n-1,2*n-1)/(2*n+1), n=0..30); # _Robert Israel_, Dec 08 2015
%t a[ n_] := If[ n < 1, 0, Binomial[ 4 n - 1, 2 n - 1] / (2 n + 1)]; (* _Michael Somos_, Oct 25 2014 *)
%o (MuPAD) combinat::dyckWords::count(2*n)/2 $ n = 1..26 // _Zerinvary Lajos_, Apr 25 2007
%o (PARI) { for (n=1, 100, a=(4*n - 1)!/((2*n + 1)!*(2*n - 1)!); write("b065097.txt", n, " ", a) ) } \\ _Harry J. Smith_, Oct 07 2009
%o (PARI) vector(100, n, binomial(4*n-1, 2*n-1)/(2*n+1)) \\ _Altug Alkan_, Dec 08 2015
%o (Sage)
%o A065097 = lambda n: hypergeometric([1-2*n,-2*n],[2],1)/2
%o [Integer(A065097(n).n(500)) for n in (1..20)] # _Peter Luschny_, Sep 22 2014
%o (Magma) [Binomial(4*n-1, 2*n-1)/(2*n+1): n in [1..20]]; // _Vincenzo Librandi_, Dec 09 2015
%Y Cf. A003150 (for analog with consecutive Fibonacci numbers).
%Y Equals (1/2) A048990. Cf. A000108, A001795, A201204, A201205, A265101, A265102, A265103.
%Y Cf. A000891, A001263, A001622, A090181, A185650, A358585.
%K nonn,easy
%O 0,3
%A _Len Smiley_, Nov 11 2001
%E a(0)=1 prepended by _Alois P. Heinz_, Nov 28 2021
| 