What power of two divides a weighted Catalan number?

摘要

Given a sequence of integers b = (b(0), b(1), b(2), one gives a Dyck path P of length 2n the weight wt(P) = b(h1)b(h2) (...) b(hn), where hi is the height of the ith ascent of P. The corresponding weighted Catalan number is C-n(b) = Sigma(wt(P)(p) where the sum is over all Dyck paths of length 2n. So, in particular, the ordinary Catalan numbers Cn correspond to b(i) = 1 for all i >= 0. Let xi(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 xi (C-n(b)) = xi(Cn). In the special case b(i) = (2i + 1)(2), n 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 xi (C-n). (c) 2006 Elsevier Inc. All rights reserved.