"Also number of Motzkin n-paths: paths from (0,0) to (n,0) in an n X n grid using only steps U = (1,1), F = (1,0) and D = (1,-1). - David Callan, Jul 15 2004". If U,F,D are redefined +(0,1) as U = (1,2), F = (1,1) and D = (1,0) then the path will go from (0,0) to (n,n), but you can also transpose to U = (2,1), F = (1,1) and D = (0,1). The original constraint to the positive first quadrant then becomes y <= x as desired. The best resource I could find was Alin Bostan's Habilitation: "Calcul Formel pour la Combinatoire des Marches", but I don't know if it will have any better answer to this particular question. --Brad On Sun, Mar 15, 2020 at 10:22 AM Neil Sloane <njasloane@gmail.com> wrote:
Dear Math Fun, My Rutgers colleague Vladimir Retakh ( vretakh@math.rutgers.edu) has a question about Motzkin numbers; He asks:
I consider Dyck paths on the integer grid from (0,0) to (n,n) consisting of zigzags with horizontal and vertical segments and staying below the diagonal x=y. I claim that the number of such paths with horizontal segments of length non-equal to 3, 5, 7, ... (odd numbers greater than 1) is equal to the n-th Motzkin numbers. May I have a reference confirming this statement?
Me: The literature about these numbers is huge (see https://oeis.org/A001006, which is about the second-biggest entry after the Catalan numbers). Can someone help Professor Retakh with a reference or proof? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun