|
|
|
|
combinations without specified separations
|
|
|
|
|
|
|
|
نویسنده
|
allen michael
|
|
منبع
|
communications in combinatorics and optimization - 2026 - دوره : 11 - شماره : 2 - صفحه:695 -711
|
|
چکیده
|
We consider the restricted subsets of $mathbb{n}_n={1,2,ldots,n}$ with $qgeq1$ 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 ($1times1$ 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_iinmathbb{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.
|
|
کلیدواژه
|
restricted combination ,combinatorial proof ,tiling ,directed pseudograph
|
|
آدرس
|
mahidol university, faculty of science, physics department, thailand
|
|
پست الکترونیکی
|
maa5652@gmail.com
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|