A prominent topic in combinatorics is the enumeration of nonintersecting lattice paths subject to certain conditions. My goal is fairly simple: given starting points $(1,1), (2,1), \ldots, (k,1)$ and endpoints $(x_1, y_1), \ldots, (x_k, y_k)$, I would like to generate all families of $k$ nonintersecting lattice paths with these start/endpoints. By "lattice path," I mean a path in the plane whose steps are either $(1,0)$ or $(0,1)$.

My current method is hugely inefficient, because I first look at all $k$-tuples of paths with the prescribed start/endpoints, and then delete the ones in which the paths intersect. In order to find all paths between $(a,b)$ and $(x,y)$, I use FindPath and GridGraph as follows:

AllPaths[{{a_, b_}, {x_, y_}}] := 
  Map[{a - 1, b - 1} + # &, 
   Round[FindPath[GridGraph[{y - b + 1, x - a + 1}], 
      1, (x - a + 1) (y - b + 1), {x - a + y - b}, All] /. 
     Thread[Range[(x - a + 1) (y - b + 1)] -> 
       GraphEmbedding[GridGraph[{y - b + 1, x - a + 1}]]]], {2}];

By repeating this for each start/endpoint pair, and then taking Tuples with one path from each set, I get the set of all families of lattice paths --- which is humongous, so that deleting the intersecting families takes a long time.

Is there a more efficient way to construct families of nonintersecting lattice paths? Perhaps, for instance, by using Fold in some clever manner to restrict subsequent paths to the region bounded by their predecessor?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.