Article ID Journal Published Year Pages File Type
4656392 Journal of Combinatorial Theory, Series A 2007 8 Pages PDF
Abstract

Given a sequence of integers b=(b0,b1,b2,…)b=(b0,b1,b2,…) one gives a Dyck path P of length 2n the weightwt(P)=bh1bh2⋯bhn,wt(P)=bh1bh2⋯bhn, where hihi is the height of the ith ascent of P. The corresponding weighted Catalan number isCnb=∑Pwt(P), where the sum is over all Dyck paths of length 2n  . So, in particular, the ordinary Catalan numbers CnCn correspond to bi=1bi=1 for all i⩾0i⩾0. Let ξ(n)ξ(n) stand for the base two exponent of n, i.e., the largest power of 2 dividing n. We give a condition on b   which implies that ξ(Cnb)=ξ(Cn). In the special case bi=(2i+1)2bi=(2i+1)2, this settles a conjecture of Postnikov about the number of plane Morse links. Our proof generalizes the recent combinatorial proof of Deutsch and Sagan of the classical formula for ξ(Cn)ξ(Cn).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,