Lattice paths can be used to model scheduling and routing problems, and, therefore, identifying maximum sets of k-distinct paths is of general interest. We extend the work previously done by Gillman et. al. to determine the order of a maximum set of k-distinct lattice paths. In particular, we disprove a conjecture by Gillman that a greedy algorithm gives this maximum order and also refine an upper bound given by Brewer et. al. We illustrate that brute force is an inefficient method to determine the maximum order, as it has time complexity O(nk).
Yager, Eric J. and Engstrom, Marcus
"k-Distinct Lattice Paths,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 24:
2, Article 6.
Available at: https://scholar.rose-hulman.edu/rhumj/vol24/iss2/6