What power of two divides a weighted Catalan number?
| dc.creator | Postnikov, Alexander | |
| dc.creator | Sagan, Bruce | |
| dc.date | 2006-01-13 | |
| dc.date | 2006-01-16 | |
| dc.date.accessioned | 2026-07-07T06:58:54Z | |
| dc.date.available | 2026-07-07T06:58:54Z | |
| dc.description | 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 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(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 xi(C_n). | |
| dc.description | Fixed references | |
| dc.identifier | https://arxiv.org/abs/math/0601339 | |
| dc.identifier | http://arxiv.org/abs/math/0601339 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/107545 | |
| dc.subject | Combinatorics | |
| dc.subject | Number Theory | |
| dc.subject | Primary 05A10; Secondary 11A55, 11B75 | |
| dc.title | What power of two divides a weighted Catalan number? | |
| dc.type | text |