Resource type

Thesis type

(Thesis) M.Sc.

Date created

2023-04-19

Authors/Contributors

Author: Firoozi, Federico

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.

Identifier

etd22480

Copyright statement

Copyright is held by the author(s).

Supervisor or Senior Supervisor

Thesis advisor: Jedwab, Jonathan

Language

English

Member of collection

Download file | Size |
---|---|

etd22480.pdf | 612.26 KB |