OFFSET
0,3
COMMENTS
A Catalan-like formula using consecutive odd numbers. Recall that Catalan numbers (A000108) are given by ((n+1)+(n)-1)!/((n+1)!(n)!).
From David Callan, Jun 01 2006: (Start)
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.
For example, a(2)=7 counts UUUUDDDD, UUUDUDDD, UUDUUDDD, UUDUDUDD, UUUDDUDD, UD.UUUDDD, UD.UUDUDD ("." denotes an interior return to ground level).
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.
a(n) = Sum_{k=0..n-1} C(2n-1-2k)*C(2k). This identity has the following combinatorial interpretation:
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)
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
From Peter Bala, Dec 01 2015: (Start)
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)).
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)
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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..834 (terms n = 1..100 from Harry J. Smith)
D. Armstrong, B. Rhoades, and N. Williams, Rational associahedra and noncrossing partitions arxiv:1305.7286 [math.CO], 2008.
Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math., 204 (1999), no. 1-3, 163-166.
FORMULA
a(n) = binomial(4*n-1, 2*n-1)/(2*n+1).
a(n) = C(2n)/2 where C(n) is the Catalan number A000108. - David Callan, Jun 01 2006
G.f.: 1/2 + (sqrt(2)/2)/sqrt(1+sqrt(1-16*x)). - Vladeta Jovovic, Sep 26 2003
G.f.: 1 + 3F2([1, 5/4, 7/4], [2, 5/2], 16*x). - Olivier Gérard, Feb 16 2011
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
a(n) = hypergeometric([1-2*n,-2*n],[2],1)/2. - Peter Luschny, Sep 22 2014
a(n) = A001448(n) / (4*n + 2) if n>0. - Michael Somos, Oct 25 2014
n*(2*n+1)*a(n) - 2*(4*n-1)*(4*n-3)*a(n-1) = 0. - R. J. Mathar, Oct 31 2015
O.g.f. is 1 + Revert( x*(1 + x)/(1 + 2*x)^4 ). - Peter Bala, Dec 01 2015
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
From Peter Bala, Apr 29 2024: (Start)
For n >= 1, a(n) = (1/8)*Sum_{k = 0..2*n-1} (-1)^k * 4^(2*n-k)*binomial(2*n-1, k)*Catalan(k+1).
For n >= 1, a(n) = (1/8)*(16^n)*hypergeom([1 - 2*n, 3/2], [3], 1). (End)
EXAMPLE
G.f.: 1 + x + 7*x^2 + 66*x^3 + 715*x^4 + 8398*x^5 + 104006*x^6 + ...
MAPLE
seq(binomial(4*n-1, 2*n-1)/(2*n+1), n=0..30); # Robert Israel, Dec 08 2015
MATHEMATICA
a[ n_] := If[ n < 1, 0, Binomial[ 4 n - 1, 2 n - 1] / (2 n + 1)]; (* Michael Somos, Oct 25 2014 *)
PROG
(MuPAD) combinat::dyckWords::count(2*n)/2 $ n = 1..26 // Zerinvary Lajos, Apr 25 2007
(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
(PARI) vector(100, n, binomial(4*n-1, 2*n-1)/(2*n+1)) \\ Altug Alkan, Dec 08 2015
(Sage)
A065097 = lambda n: hypergeometric([1-2*n, -2*n], [2], 1)/2
[Integer(A065097(n).n(500)) for n in (1..20)] # Peter Luschny, Sep 22 2014
(Magma) [Binomial(4*n-1, 2*n-1)/(2*n+1): n in [1..20]]; // Vincenzo Librandi, Dec 09 2015
CROSSREFS
Cf. A003150 (for analog with consecutive Fibonacci numbers).
KEYWORD
nonn,easy
AUTHOR
Len Smiley, Nov 11 2001
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Nov 28 2021
STATUS
approved