A375817 In an n X n grid draw straight walls between cells, starting at a border, such that the resulting figure is connected and has only one-cell wide paths; a(n) is the number of solutions not reduced for symmetries.

1, 4, 56, 1112, 25000, 607712, 15918280, 451371888, 13908978792, 466254401360, 16972978214456, 668532916285104, 28362769354991656, 1290007395847848160, 62619708755213093360, 3230982278203826268640, 176553522584025285715304, 10184062836771923067636528

Offset: 1

Author

Lars Blomberg, Aug 30 2024

Keywords

• nonn

Comments

This sequence contains some, but not all of the spanning trees in A007341, a(n)<A007341(n), for n>2.

See A375770 for examples.

Examples

			a(3) = 56. The A375770(3) = 10 distinct solutions with their multiplicities are:
  ._._._.   ._._._.   ._._._.   ._._._.   ._._._.
  |     |   |   | |   |   | |   | | | |   |   ._|
  | | | |   | |   |   | | | |   |     |   | |   |
  |_|_|_|   |_|_|_|   |_|_._|   |_|_|_|   |_|_|_|
    (4)       (8)       (4)       (2)       (8)
  ._._._.   ._._._.   ._._._.   ._._._.   ._._._.
  | | ._|   |   | |   |   ._|   |_. ._|   |_. | |
  |     |   | | ._|   | | ._|   |     |   |   ._|
  |_|_|_|   |_|_._|   |_|_._|   |_|_|_|   |_|_._|
    (8)       (8)       (8)       (4)       (2)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100

Crossrefs

Main diagonal of A375858.

Cf. A007341, A375770 (up to rotations and reflections), A375859 (up to rotations), A375860 (up to symmetries of the rectangle).

Programs

PARI

\\ See PARI link in A375770 for program code.
vector(20, n, A375817(n)) \\ Andrew Howroyd, Sep 03 2024

Extensions

Terms corrected and extended by Andrew Howroyd, Sep 03 2024