Combinations without specified separations

Document Type : Original paper

Author

Physics Department, Faculty of Science, Mahidol University, Rama 6 Road, Bangkok 10400, Thailand

Abstract

We consider the restricted subsets of $\mathbb{N}_n=\{1,2,\ldots,n\}$ with $q\geq1$ being the largest member of the set $\mathcal{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 $k$-subsets for any $\mathcal{Q}$ when $|{\mathbb{N}_q-\mathcal{Q}}|\leq2$.  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\times1$ tiles) and combs.  A $(w_1,g_1,w_2,g_2,\ldots,g_{t-1},w_t)$-comb is composed of $t$ sub-tiles known as teeth.  The $i$-th tooth in the comb has width $w_i$ and is separated from the $(i+1)$-th tooth by a gap of width $g_i$. Here we only consider combs with $w_i,g_i\in\mathbb{Z}^+$.  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.

Keywords

Main Subjects

References

[1] M.A. Allen, On a two-parameter family of generalizations of Pascal’s triangle, J. Integer Seq. 25 (2022), no. 9, Article 22.9.8.
[2] M.A. Allen, Connections between combinations without specified separations and strongly restricted permutations, compositions, and bit strings, J. Integer Seq. 28 (2025), no. 3, Article 25.3.7.
[3] M.A. Allen and K. Edwards, On two families of generalizations of Pascal’s triangle, J. Integer Seq. 25 (2022), no. 7, Article 22.7.1.
[4] M.A. Allen and K. Edwards, Identities involving the tribonacci numbers squared via tiling with combs, Fibonacci Quart. 61 (2023), no. 1, 21–27.  https://doi.org/10.1080/00150517.2023.12427419
[5] M.A. Allen and K. Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Linear Multilinear Algebra 72 (2024), no. 13, 2091–2103. https://doi.org/10.1080/03081087.2022.2107979
[6] A. Benjamin and  J.J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, Washington, 2003.
[7] K. Edwards, A Pascal-like triangle related to the tribonacci numbers, Fibonacci Quart. 46/47 (2008/2009), no. 1, 18–25. https://doi.org/10.1080/00150517.2008.12428183
[8] K. Edwards and M.A. Allen, Strongly restricted permutations and tiling with fences, Discrete Appl. Math. 187 (2015), 82–90.  https://doi.org/10.1016/j.dam.2015.02.004
[9] K. Edwards and M.A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Integer Seq. 24 (2021), no. 3, Article 21.3.8.
[10] V.J.W. Guo, A new proof of a theorem of Mansour and Sun, European J. Combin. 29 (2008), no. 7, 1582–1584. https://doi.org/10.1016/j.ejc.2007.11.024
[11] J. Guo, V.J.W. and Zeng, On arithmetic partitions of $\mathbb{Z}_n$, European J. Combin. 30 (2009), no. 5, 1281–1288. https://doi.org/10.1016/j.ejc.2008.11.009
[12] I. Kaplansky, Solution of the “probléme des ménages”, Bull. Am. Math. Soc. 49 (1943), no. 10, 784–785. https://doi.org/10.1090/S0002-9904-1943-08035-4
[13] S. Kitaev, Independent sets on path-schemes, J. Integer Seq. 9 (2006), no. 2, Article 06.2.2.
[14] J. Konvalina, On the number of combinations without unit separation, J. Combin. Theory Ser. A 31 (1981), no. 2, 101–107.  https://doi.org/10.1016/0097-3165(81)90006-6
[15] J. Konvalina and Y.H. Liu, Bit strings without q-separation, BIT Numer. Math. 31 (1991), no. 1, 32–35. https://doi.org/10.1007/BF01952780
[16] J. Konvalina and Y.H. Liu, Subsets without $q$-separation and binomial products of Fibonacci numbers, J. Combin. Theory Ser. A 57 (1991), no. 2, 306–310.  https://doi.org/10.1016/0097-3165(91)90054-K
[17] T. Mansour and Y. Sun, On the number of combinations without certain separations, European J. Combin. 29 (2008), no. 5, 1200–1206.  https://doi.org/10.1016/j.ejc.2007.06.024
[18] W.O.J. Moser, The number of subsets without a fixed circular distance, J. Combin. Theory Ser. A 43 (1986), no. 1, 130–132.  https://doi.org/10.1016/0097-3165(86)90030-0
[19] H. Prodinger, On the number of combinations without a fixed distance, J. Combin. Theory Ser. A 35 (1983), no. 3, 362–365.  https://doi.org/10.1016/0097-3165(83)90019-5
[20] N.J.A. Sloane, The on-line encyclopedia of integer sequences, 2010, published electronically at https://oeis.org.
[21] A.A. Valyuzhenich, Some properties of well-based sequences, J. Appl. Ind. Math. 5 (2011), no. 4, 612–614. https://doi.org/10.1134/S1990478911040168
Communications in Combinatorics and Optimization
Volume 11, Issue 2
June 2026
Pages 695-711

Files

Share

How to cite

Statistics