学术文献库

We consider a one-dimensional variant of a recently introduced settlement planning problem in which houses can be built on finite portions of the rectangular integer lattice subject to certain requirements on the amount of insolation they receive. In our model, each house occupies a unit square on a $1 \times n$ strip, with the restriction that at least one of the neighboring squares must be free. We are interested mostly in situations in which no further building is possible, i.e. in maximal configurations of houses in the strip. We reinterpret the problem as a problem of restricted packing of vertices in a path graph and then apply the transfer matrix method in order to compute the bivariate generating functions for the sequences enumerating all maximal configurations of a given length with respect to the number of houses. This allows us to determine the asymptotic behavior of the enumerating sequences and to compute some interesting statistics. Along the way, we establish close connections between our maximal configurations and several other types of combinatorial objects, including restricted permutations and walks on certain small oriented graphs. In all cases we provide combinatorial proofs. We then generalize our results in several directions by considering multi-story houses, by varying the insolation restrictions, and, finally, by considering strips of width 2 and 3. At the end we comment on several possible directions of future research.