What power of two divides a weighted Catalan number?

الأصل · EN

Given a sequence of integers b = (b₀,b₁,b₂,...) one gives a Dyck path P of length 2n the weight wt(P) = bₕ₁ bₕ₂... bₕₙ, where hᵢ is the height of the ith ascent of P. The corresponding weighted Catalan number is Cₙᵇ = sumₚ wt(P), where the sum is over all Dyck paths of length 2n. So, in particular, the ordinary Catalan numbers Cₙ correspond to bᵢ = 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ₙᵇ) = xi(Cₙ). In the special case bᵢ=(2i+1)², 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ₙ).