OFFSET
1,3
COMMENTS
A123663 provides the maximum number of cardinal adjacencies among n-celled polyominoes. The sequence under consideration here provides the maximum number of intercardinal (edge-to-edge and vertex-to-vertex) adjacencies among all n-celled polyplets.
Both A123663 and this sequence are used by landscape ecologists and geographic information system (GIS) professionals to determine quantitative measures over time of landscape erosion in high density coastal areas.
For initial terms n <= 20, M_O(n) is known to be optimal; for n > 20, the optimality of M_O(n) is probable. - Nicholas P. Taliceo, Jul 12 2021
LINKS
K. McGarigal, FRAGSTATS Webpage—Contains the Aggregation Index
N. P. Taliceo, ICAI Python Code
N. P. Taliceo, Intercardinal Adjacencies: A New Landscape Metric, Westfield State University Honors Program (2016).
N. P. Taliceo and J. F. Fleron (2021), A Prime Example of the Strong Law of Small Numbers, Mathematics Magazine, 94:1, 59-61.
FORMULA
By empirical observation a split-rule formula with 15 conditions generates the sequence M = 0, 1, 3, 6, 8, 11, ... correctly for small n - this includes comparison with configurations known to be optimal (n < 20) and with computer generated searches for optimal configurations (n < 500):
M_O(n) = 4n - 14p + 10 - e
where
n = number of tiles in the polyplet t
p = Max{p>=1 : n >= 7p^2-10p+4}
e = 0, if n = 7p^2 - 10p + 4
e = 1, if 7p^2 - 10p + 4 < n <= 7p^2 - 9p + 3
e = 2, if 7p^2 - 9p + 3 < n <= 7p^2 - 8p + 2
e = 3, if 7p^2 - 8p + 2 < n <= 7p^2 - 7p + 2
e = 4, if 7p^2 - 7p + 2 < n <= 7p^2 - 6p + 1
e = 5, if 7p^2 - 6p + 1 < n <= 7p^2 - 5p + 1
e = 6, if 7p^2 - 5p + 1 < n <= 7p^2 - 4p + 1
e = 7, if 7p^2 - 4p + 1 < n <= 7p^2 - 3p
e = 8, if 7p^2 - 3p < n <= 7p^2 - 2p
e = 9, if 7p^2 - 2p < n <= 7p^2 - p
e = 10, if 7p^2 - p < n <= 7p^2
e = 11, if 7p^2 < n <= 7p^2 + p
e = 12, if 7p^2 + p < n <= 7p^2 + 2p
e = 13, if 7p^2 + 2p < n <= 7p^2 + 3p
e = 14, if n > 7p^2 + 3p
This split-rule formula is derived geometrically using an approach described in the Example section.
Subsequently we have proved that M_O can be represented analytically by a single expression: M_O(n) = 4n-ceiling(sqrt(28n-12)).
We have proved the important estimate M_O(n) <= M(n) <= 2*(2n-2*ceiling(sqrt(n))) where 2n-2*ceiling(sqrt(n)) is A123663. This upper bound is not sharp for small n. The relative difference between M_O(n) and 2*(2n-2*ceiling(sqrt(n))) is less than 3% for at least 145 <= n <= 10^7 tiles and the relative difference goes to zero. For practical uses like GIS, our formula will have very small relative error if, in fact, it does not describe the sequence exactly.
EXAMPLE
For n = 12, the optimal configuration is a "regular octagon" of side length two (i.e., the symmetric, cross-shaped configuration with rows of length 2, 4, 4, and 2). This yields 30 intercardinal adjacencies.
In general, when n = 7p^2 - 10p + 4 the n tiles can be arranged into the shape of a regular octagon with side length p and 28p^2 - 54p + 26 intercardinal adjacencies. We conjecture these are optimal.
Moreover, we believe all of the intermediary cases are generated by a family of archetypes where one moves from a regular octagon to a "stretched octagon" to a "small corners octagon" and then to the next largest regular octagon. This geometric approach gives rise to the split rule formula described above.
PROG
(Python) # See N. P. Taliceo link.
CROSSREFS
KEYWORD
nonn
AUTHOR
Nicholas P. Taliceo and Julian F. Fleron, Sep 09 2019
STATUS
approved