A379241 Maximum number of connections for a 2 X n rectangle.

1, 5, 22, 54, 134, 269, 534, 934, 1618, 2573, 4062, 6030, 8902, 12549, 17614, 23854, 32194, 42229, 55238

Offset: 2

Author

Rodolfo Kurchan, Dec 18 2024

Keywords

• nonn
• more

Comments

In a 2 X n board (with n > 1) with numbers 1 and 2, at least 2 of each, find the arrangement with more solutions connecting a pair of numbers 1 and a pair of number 2, covering the entire board and without passing through the same square twice.

Terms a(7)-a(20) from Giorgio Vecchi.

In a vertex-colored graph, partition the vertices into paths of positive lengths. It is required that the two terminal vertices of each path have the same color, and that there is exactly one such path for each color of the terminal vertices. a(n) is the maximum number of such partitions for all possible 2-colorings (at least two vertices of each color) of the 2 X n grid graph. - Pontus von Brömssen, Dec 19 2024

Examples

			For n = 3 the with the board
  +---+---+---+
  | 1 | 1 | 2 |
  +---+---+---+
  | 1 | 2 | 2 |
  +---+---+---+
the maximum number of solutions is 5 being the squares with this letters:
  +---+---+---+
  | A | B | C |
  +---+---+---+
  | D | E | F |
  +---+---+---+
Solutions:
  1) ABED - CF
  2) ADEB - CF
  3) BAD - CFE
  4) AD - CBEF
  5) AD - EBCF
There are five solutions so a(3) = 5.
		

Links

• Rodolfo Kurchan and Claudio Meller, Number Connections, Puzzle Fun, Problems (2024).