Maximal 2-dimensional binary words of bounded degree
Maximal 2-dimensional binary words of bounded degree
Let d be an integer between 0 and 4, and W be a 2-dimensional word of dimensions h x w on the binary alphabet {0, 1}, where h, w in Z > 0. Assume that each occurrence of the letter 1 in W is adjacent to at most d letters 1. We provide an exact formula for the maximum number of letters 1 that can occur in W for fixed (h, w). As a byproduct, we deduce an upper bound on the length of maximum snake polyominoes contained in a h x w rectangle.
Alexandre Blondin Massé、Alain Goupil、Ralphael L'Heureux、Louis Marin
数学
Alexandre Blondin Massé,Alain Goupil,Ralphael L'Heureux,Louis Marin.Maximal 2-dimensional binary words of bounded degree[EB/OL].(2025-05-19)[2025-07-09].https://arxiv.org/abs/2505.13640.点此复制
评论