Volume 19

DOI: 10.1137/25S178417X

Authors

Ejmen Al-Ubejdij (Corresponding author – Hamad Bin Khalifa University), Elyas Al-Amri (Hamad Bin Khalifa University), Marwan Humaid (Hamad Bin Khalifa University), Hamad Aldous (Hamad Bin Khalifa University), Yousef Abu Dayeh (Carnegie Mellon University in Qatar)

Project Advisors

Dr. Samir Brahim Belhaouari (Hamad Bin Khalifa University)

Abstract

This paper presents a unified combinatorial framework for counting iterations in nested loop structures with generalized constraints. Traditional approaches limit themselves to strictly increasing index sequences, yielding binomial coefficient (n/k). We introduce the ghost element transformation, which enables efficient counting under non-strict inequalities by establishing a bijection between constrained sequences and selections from an augmented set. For the fundamental case with nonstrict inequalities, this transformation yields the formula (n+k−1/k), with extensions to gap constraints and variable offsets. We prove that sequences with minimum spacing d between consecutive indices have count (n−(k−1)(d−1)/k), and provide a general formula for variable offset constraints. Our computational analysis demonstrates that direct enumeration requires O(nk) time, while our formulas evaluate in O(1) time assuming constant-time arithmetic. For typical parameters (n = 100, k = 20), our approach reduces computation time from over 10 hours to under 1 millisecond. The methodology applies broadly to algorithm analysis, combinatorial optimization, and statistical sampling.