A278299 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.

2, 4, 6, 9, 12, 15, 19, 24, 30, 34

Offset

2,1

Comments

Only edge-to-edge adjacencies are considered.

The sequence is bounded above by A053439(n-1).

a(n) is bounded below by n * ceiling((n - 1)/4). This bound is achieved for n=2, n=6, and n=10.

Links

Table of n, a(n) for n=2..11.

Example

Example: for n = 4, the following diagram gives a minimal polyomino of a(4) = 6 tiles:
      +---+---+
      | 1 | 4 |
  +---+---+---+
  | 4 | 3 | 2 |
  +---+---+---+
          | 1 |
          +---+
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.
              +---+---+
              | 8 | 6 |
          +---+---+---+---+---+
          | 3 | 2 | 5 | 9 | 4 |
  +---+---+---+---+---+---+---+---+
  | 2 | 7 | 5 | 1 | 4 | 2 | 10| 9 |
  +---+---+---+---+---+---+---+---+
  | 6 | 9 | 8 | 3 | 6 | 7 | 8 | 1 |
  +---+---+---+---+---+---+---+---+
  | 10| 3 | 4 | 7 | 1 | 10| 5 |
  +---+---+---+---+---+---+---+
From Ryan Lee, May 14 2019: (Start)
Example for n = 11:
  +---+---+---+---+---+
  | 9 | 11| 2 | 5 | 8 |
  +---+---+---+---+---+---+
  | 1 | 5 | 10| 9 | 2 | 1 |
  +---+---+---+---+---+---+
  | 4 | 6 | 11| 8 | 7 | 3 |
  +---+---+---+---+---+---+
  | 3 | 9 | 7 | 10| 6 | 2 |
  +---+---+---+---+---+---+
  | 11| 4 | 5 | 3 | 8 | 4 |
  +---+---+---+---+---+---+
  | 1 | 10|   | 6 | 1 | 7 |
  +---+---+   +---+---+---+
(End)

Crossrefs

Cf. A053439.

Sequence in context: A194203 A261222 A130025 * A145802 A076271 A036441

Adjacent sequences: A278296 A278297 A278298 * A278300 A278301 A278302

Keyword

nonn,more

Author

Alec Jones and Peter Kagey, Nov 17 2016

Extensions

a(11) from Ryan Lee, May 14 2019

Status

approved