Enumerating and constructing essentially equivalent lattice paths
The paper considers lattice paths from \((0,0)\) to \((m,n)\). The following problem is studied: what is the maximum size of a set of such lattice paths, such that any two lattice paths share at most \(k\) edges? The following conjecture is found: a maximum size set is achieved, if all lattice paths are listed in reverse lexicographic order, and one selects paths from this list with a greedy algorithm. (Denoting a step up by N, and a step to the right by E, the reverse lexicographic order of lattice paths from \((0,0)\) to \((2,2)\) is NNEE, NENE, NEEN, ENNE, ENEN, EENN.) Some partial results are given which support this conjecture.
scientific article; zbMATH DE number 1693694