## DIMACS TR: 2006-21

## What power of two divides a weighted Catalan number

### Authors: Alexander Postnikov and Bruce E. Sagan

**
ABSTRACT
**

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_{h_1} b_{h_2} ... b_{h_n},
where h_i is the height of the ith ascent of P. The corresponding
weighted Catalan number is
C_n^b = sum_P wt(P),
where the sum is over all Dyck paths of length 2n. So, in particular,
the ordinary Catalan numbers C_n correspond to b_i = 1 for all
i >= 0. Let e(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 e(C_n^b) = e(C_n). In the special case b_i = (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 e(C_n).

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-21.ps.gz

DIMACS Home Page