Posting on behalf of Richard Brak: ---------- Forwarded message --------- From: Richard Brak <rb1@unimelb.edu.au> Date: Sun, Mar 15, 2020 at 10:26 PM Subject: Fwd: [DOMINO] [math-fun] Question about Motzkin nmubers from Vladimir Retakh To: James Propp <jamespropp@gmail.com> Hi Jim, Whilst I do receive emails from the list server I am unable to post messages (the message below seems to have been rejected) so I have sent the reply directly to you. Cheers Richard. ------------------------------ *From:* Richard Brak <rb1@unimelb.edu.au> *Sent:* Monday, March 16, 2020 11:50:51 AM *To:* Domino Forum <DOMINO@LISTSERV.UML.EDU> *Subject:* Re: [DOMINO] [math-fun] Question about Motzkin nmubers from Vladimir Retakh Hi Jim, Here is an outline of a proof (the final bijection is rather simple). Richard. A bijection between the set of Motzkin paths and HE-Dyck paths (Dyck paths all of whose horizontal segments are even length - a horizontal segment is a maximal sequence of adjacent horizontal steps - ) can be proved using a universal bijection. To do this it is necessary to show the HE-Dyck paths are a free algebra (or n-magma) generated by a single element with a unary and binary function. This can proved using theorem 1 ofarXiv:1909.09296 <https://arxiv.org/abs/1909.09296>. To use the theorem four properties have to be proved: 1. The unary and binary maps (see below) must be injective 2. The images of the unary and binary maps be disjoint. 3. The norm must be additive (see below) 4. The union of the images of the unary and binary maps must be all of the set of HE-Dyck paths expect for one element. Denoting horizontal steps by H and vertical steps by V and the set of all HE-Dyck paths by D (this includes the zero step path represented by a single vertex), the maps can be defined as: 1. Unary map: u: D->D with u(d)=dHHVV, where dinD 2. Binary map: D imes D -> D with d_1 * d_2 = d_1 HHHH d_2 VVVV, where d_1,d_2in D. 3. Norm: || d|| = (total number of steps in d )/4 +1 4. The generator is the zero step path (or single vertex). The norm is a size function which has to be “additive”: ||u(d)||=||d||+1 and ||d_1 * d_2|| = ||d_1 ||+|| d_2||. This is straightforward to show using the above three definitions. The images of the two maps have to be disjoint (clearly the case: the former end on HHVV and the latter VVVV). Injectivity is equivalent to unique factorisation of all but one path: 1. if a path ends HHVV the preceding path is unique (unary factorisation). 2. If the path end VVVV then the last HHHH sequence (certain to exist) uniquely defines the two sub-paths. Every HE-Dyck path is one of the above to cases except for the zero step path. This shows the HE-Dyck paths with the above two maps format a (1,2)-magma (or free algebra) and hence there exists a universal isomorphism between the two families. The isomorphism defines the bijection which is also recursive. Basically the image of an HE-Dyck path d, is found by using the two maps to fully factorise d to a “product” of the two maps then replacing the two maps by the Mozkin maps and the Mozkin path generator. For example, the HE-path d=HHVVHHHHVVVVHHVVHHVV = u(u(u(o)*(o*o))) u(u(u(o)*(o*o))) -> f(f(f(o)#(o#o))) Where f and # are the Motzkin path unary and binary maps, giving f(f(f(o)#o)) = f(f(s # o)) = f(f(shv))=shvss Where s a a diagonal Motzkin step and h, v the horizontal and vertical. On 16 Mar 2020, at 3:31 am, James Propp <jamespropp@GMAIL.COM> wrote: Can anyone provide a reference or a proof? Jim Propp On Sun, Mar 15, 2020 at 11: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