On a variant of Flory model

arXiv2210.12411MaRDI QIDQ6414769FDOQ6414769

Josip Žubrinić, Tomislav Došlić, Mate Puljiz, Stjepan Šebek

Publication date: 22 October 2022

Abstract: 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 $1imesn$ 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.

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of packing and covering (05B40) Mathematics and architecture (00A67)

This page was built for publication: On a variant of Flory model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414769)