{"ID":2860789,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.02727","arxiv_id":"2510.02727","title":"On the Enumeration of all Unique Paths of Recombining Trinomial Trees","abstract":"Recombining trinomial trees are a workhorse for modeling discrete-event systems in option pricing, logistics, and feedback control. Because each node stores a state-dependent quantity, a depth-$D$ tree naively yields $\\mathcal{O}(3^{D})$ trajectories, making exhaustive enumeration infeasible. Under time-homogeneous dynamics, however, the graph exhibits two exploitable symmetries: (i) translational invariance of nodes and (ii) a canonical bijection between admissible paths and ordered tuples encoding weak compositions. Leveraging these, we introduce a mass-shifting enumeration algorithm that slides integer \"masses\" through a cardinality tuple to generate exactly one representative per path-equivalence class while implicitly counting the associated weak compositions. This trims the search space by an exponential factor, enabling markedly deeper trees -- and therefore tighter numerical approximations of the underlying evolution -- to be processed in practice. We further derive an upper bound on the combinatorial counting expression that induces a theoretical lower bound on the algorithmic cost of approximately $\\mathcal{O}\\bigl(D^{1/2}1.612^{D}\\bigr)$. This correspondence permits direct benchmarking while empirical tests, whose pseudo-code we provide, corroborate the bound, showing only a small constant overhead and substantial speedups over classical breadth-first traversal. Finally, we highlight structural links between our algorithmic/combinatorial framework and Motzkin paths with Narayana-type refinements, suggesting refined enumerative formulas and new potential analytic tools for path-dependent functionals.","short_abstract":"Recombining trinomial trees are a workhorse for modeling discrete-event systems in option pricing, logistics, and feedback control. Because each node stores a state-dependent quantity, a depth-$D$ tree naively yields $\\mathcal{O}(3^{D})$ trajectories, making exhaustive enumeration infeasible. Under time-homogeneous dyn...","url_abs":"https://arxiv.org/abs/2510.02727","url_pdf":"https://arxiv.org/pdf/2510.02727v1","authors":"[\"Ethan Torres\",\"Ramavarapu Sreenivas\",\"Richard Sowers\"]","published":"2025-10-03T05:12:40Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}