Combinations without specified separations
Issued Date
2026-06-01
Resource Type
ISSN
25382128
eISSN
25382136
Scopus ID
2-s2.0-105031715263
Journal Title
Communications in Combinatorics and Optimization
Volume
11
Issue
2
Start Page
695
End Page
711
Rights Holder(s)
SCOPUS
Bibliographic Citation
Communications in Combinatorics and Optimization Vol.11 No.2 (2026) , 695-711
Suggested Citation
Allen M.A. Combinations without specified separations. Communications in Combinatorics and Optimization Vol.11 No.2 (2026) , 695-711. 711. doi:10.22049/cco.2024.29370.1959 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/115628
Title
Combinations without specified separations
Author(s)
Author's Affiliation
Corresponding Author(s)
Other Contributor(s)
Abstract
We consider the restricted subsets of ℕ<inf>n</inf> = {1, 2, …, n} with q ≥ 1 being the largest member of the set Q of disallowed differences between subset elements. We obtain new results on various classes of problem involving such combinations lacking specified separations. In particular, we find recursion relations for the number of ksubsets for any Q when |ℕ<inf>q</inf> − Q| ≤ 2. The results are obtained, in a quick and intuitive manner, as a consequence of a bijection we give between such subsets and the restricted-overlap tilings of an (n + q)-board (a linear array of n + q square cells of unit width) with squares (1 × 1 tiles) and combs. A (w<inf>1</inf>, g<inf>1</inf>, w<inf>2</inf>, g<inf>2</inf>, …, g<inf>t−1</inf>, w<inf>t</inf>)-comb is composed of t sub-tiles known as teeth. The i-th tooth in the comb has width w<inf>i</inf> and is separated from the (i + 1)-th tooth by a gap of width g<inf>i</inf> . Here we only consider combs with w<inf>i</inf>, g<inf>i</inf> ∈ ℤ<sup>+</sup>. When performing a restricted-overlap tiling of a board with such combs and squares, the leftmost cell of a tile must be placed in an empty cell whereas the remaining cells in the tile are permitted to overlap other non-leftmost filled cells of tiles already on the board.