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,2

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.

Links

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

Example

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

Prog

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

Crossrefs

Main diagonal of A375858.

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

Sequence in context: A358886 A371678 A009058 * A276363 A361541 A218309

Adjacent sequences: A375814 A375815 A375816 * A375820 A375824 A375825

Keyword

nonn,new

Author

Lars Blomberg, Aug 30 2024

Extensions

Terms corrected and extended by Andrew Howroyd, Sep 03 2024

Status

approved