# Enumeration of lattice paths with respect to a linear boundary

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2023-04-19
Authors/Contributors
Abstract
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.
Document
Extent
54 pages.

### Keywords

Identifier
etd22480
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Language
English
Member of collection
612.26 KB