|
COMMENT
|
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).
|
|
FORMULA
|
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.yu), 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
|
