A NSWE-path is a path consisting of North, South, East and West steps of length 1 in the plane. Define a weight w for the paths by w(N)=w(E)=1 and w(S)=w(W)=t. Define the height of a path as the y-coordinate of the endpoint. For example the path NEENWSSSEENN has length 12, height 1 and its weight is t^4.
Let B(n,k) be the weight of all non-negative NSEW-paths of length n (i.e. those which never cross the x-axis) with endpoint on height k.
With generating functions it can be shown that for each n the identity
(*) B(n,0)+(1+t)B(n,1)+…+(1+t+…+t^n)B(n,n)=(2+2t)^n
holds. The right-hand side is the weight of all paths of length n.
Is there a combinatorial proof of this identity?
For example B(2,0)=1+3t+t^2 because the non-negative paths of length 2 with height 0 are EE with weight 1, EW+WE+NS with weight 3t, and WW with weight t^2.
B(2,1)=2+2t because the non-negative paths are NE+EN with weight 2 and NW+WN with weight 2t. And B(2,2)=1 because w(NN)=1.
In this case we get the identity
B(2,0)+(1+t)B(2,1)+(1+t+t^2)B(2,2)=(2+2t)^2.
In the meantime I have found a combinatorial proof in the literature: Naiomi T. Cameron and Asamoah Nkwanta, On some (pseudo) involutions in the Riordan group, J. Integer Sequences 8 (2005), Article 05.3.7, proof of identity 1. https://www.researchgate.net/profile/Asamoah_Nkwanta/publications?sorting=newest
Instead of NSWE-paths they use bicolored Motzkin paths, but their proof can easily be translated to the situation of NSWE-paths. So my question has been answered.
In the meantime I have found a combinatorial proof in the literature: Naiomi T. Cameron and Asamoah Nkwanta, On some (pseudo) involutions in the Riordan group, J. Integer Sequences 8 (2005), Article 05.3.7, proof of identity 1. https://www.researchgate.net/profile/Asamoah_Nkwanta/publications?sorting=newest
Instead of NSWE-paths they use bicolored Motzkin paths, but their proof can easily be translated to the situation of NSWE-paths. So my question has been answered.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Algebra