1,2

A Catalan-like formula using consecutive odd numbers. Recall that Catalan numbers (A000108) are given by ([n+1]+[n]-1)!/([n+1]![n]!).

Comments from David Callan (callan(AT)stat.wisc.edu), Jun 01 2006:

"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[C(2n-1-2k)C(2k),{k,0,n-1}]. This identity has the following combinatorial interpretation.

"a(n) = 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).

Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math. 204 (1999) 163-166.

Harry J. Smith, Table of n, a(n) for n=1,...,100

a(n)=binomial(4*n-1, 2*n-1)/(2*n+1)

G.f.: (sqrt(2)/2)/sqrt(1+sqrt(1-16*x))-1/2. - Vladeta Jovovic (vladeta(AT)eunet.rs), Sep 26 2003

a(n)=C(2n)/2 where C(n) is the Catalan number A000108. - David Callan (callan(AT)stat.wisc.edu), Jun 01 2006

(Mupad) combinat::dyckWords::count(2*n)/2 $ n = 1..26 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 25 2007

(PARI) { for (n=1, 100, a=(4*n - 1)!/((2*n + 1)!*(2*n - 1)!); write("b065097.txt", n, " ", a) ) } [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Oct 07 2009]

Cf. A003150 (for analogue with consecutive Fibonacci numbers).

Equals (1/2) A048990. Cf. A001795.

Sequence in context: A097819 A152525 A109779 this_sequence A122705 A024395 A003286

Adjacent sequences: A065094 A065095 A065096 this_sequence A065098 A065099 A065100

nonn

Len Smiley (smiley(AT)math.uaa.alaska.edu), Nov 11 2001