|
%I #32 May 14 2019 19:22:12
%S 2,4,6,9,12,15,19,24,30,34
%N a(n) is the tile count of the smallest polyomino with an n-coloring such that every color is adjacent to every other distinct color at least once.
%C Only edge-to-edge adjacencies are considered.
%C The sequence is bounded above by A053439(n-1).
%C a(n) is bounded below by n * ceiling((n - 1)/4). This bound is achieved for n=2, n=6, and n=10.
%e Example: for n = 4, the following diagram gives a minimal polyomino of a(4) = 6 tiles:
%e +---+---+
%e | 1 | 4 |
%e +---+---+---+
%e | 4 | 3 | 2 |
%e +---+---+---+
%e | 1 |
%e +---+
%e Example: for n = 10, the following diagram gives a minimal polyomino of a(10) = 30 tiles. Note that redundant adjacencies, e.g., between 2 and 7, can exist in minimal diagrams.
%e +---+---+
%e | 8 | 6 |
%e +---+---+---+---+---+
%e | 3 | 2 | 5 | 9 | 4 |
%e +---+---+---+---+---+---+---+---+
%e | 2 | 7 | 5 | 1 | 4 | 2 | 10| 9 |
%e +---+---+---+---+---+---+---+---+
%e | 6 | 9 | 8 | 3 | 6 | 7 | 8 | 1 |
%e +---+---+---+---+---+---+---+---+
%e | 10| 3 | 4 | 7 | 1 | 10| 5 |
%e +---+---+---+---+---+---+---+
%e From _Ryan Lee_, May 14 2019: (Start)
%e Example for n = 11:
%e +---+---+---+---+---+
%e | 9 | 11| 2 | 5 | 8 |
%e +---+---+---+---+---+---+
%e | 1 | 5 | 10| 9 | 2 | 1 |
%e +---+---+---+---+---+---+
%e | 4 | 6 | 11| 8 | 7 | 3 |
%e +---+---+---+---+---+---+
%e | 3 | 9 | 7 | 10| 6 | 2 |
%e +---+---+---+---+---+---+
%e | 11| 4 | 5 | 3 | 8 | 4 |
%e +---+---+---+---+---+---+
%e | 1 | 10| | 6 | 1 | 7 |
%e +---+---+ +---+---+---+
%e (End)
%Y Cf. A053439.
%K nonn,more
%O 2,1
%A _Alec Jones_ and _Peter Kagey_, Nov 17 2016
%E a(11) from _Ryan Lee_, May 14 2019
| 