Skip to main content

Enumeration of lattice paths with respect to a linear boundary

Resource type
Thesis type
(Thesis) M.Sc.
Date created
The history of the enumeration of finite lattice paths with respect to a linear boundary is rich with unexpected patterns and symmetries. Let a, b be coprime and let g be a positive integer. We count the number of lattice paths from the startpoint (0, 0) to the endpoint (ga, gb) whose steps are restricted to { (1, 0), (0, 1) }, with respect to a variable k measuring how much of the path lies above the linear boundary joining the startpoint to the endpoint. A first setting takes a = 1 and takes k to be the number of (0, 1) steps lying above the boundary. A 1949 result due to Chung and Feller for the case b = 1 shows that the number of paths is independent of k. Huq later showed that the same holds for all b. A second setting instead takes k to be the number of lattice points on the path that lie above the boundary. In this setting, let Nₖ(g) be the set of lattice paths for fixed a, b; we wish to determine |Nₖ(g)|. Bizley found |N₀(g)| explicitly in 1954. Firoozi, Marwendo, and Rattan recently showed that |Nₖ(1)| is independent of k. We place both these results in a more general framework by deriving a closed form expression for |Nₖ(g)|, which is significantly more complicated than for the special cases k = 0 and g = 1. We find for each g that the value |Nₖ(g)| is constant over each successive set of a + b values of k. Our proof relies on finding an explicit bijection between a subset of Nₖ(g) and the set Nₖ₊₁(g). This leads to a recursion for |Nₖ(g)| whose base case is given by Bizley's result. We use symmetric functions to show that the closed form expression satisfies the recursion.
54 pages.
Copyright statement
Copyright is held by the author(s).
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Jedwab, Jonathan
Member of collection
Download file Size
etd22480.pdf 612.26 KB

Views & downloads - as of June 2023

Views: 58
Downloads: 10