A375770 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 distinct under reflections and rotations.

1, 1, 10, 149, 3177, 76258, 1991098, 56431302, 1738662461, 58282168670, 2121623710614, 83566630166058, 3545346228604588, 161250925229195536, 7827463597195165900, 403872784815626357788, 22069190323151660044413, 1273007854598883147607470, 77288239799225577008977654

Offset

1,3

Comments

This sequence contains some, but not all of the spanning trees in A349718.

Links

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

Andrew Howroyd, PARI Program and formula, Sep 2024.

Example

a(2)=1:
+=======+
| o - o |
| |   | |
| o ║ o |
+===+===+
a(3)=10:
+===========+  +=======+===+  +=======+===+  +===+===+===+  +===========+
| o - o - o |  | o - o ║ o |  | o - o ║ o |  | o ║ o ║ o |  | o - o - o |
| |   |   | |  | |   |   | |  | |   | ║ | |  | |   |   | |  | |   |   ══+
| o ║ o ║ o |  | o ║ o - o |  | o ║ o ║ o |  | o - o - o |  | o ║ o - o |
| | ║ | ║ | |  | | ║ |   | |  | | ║ |   | |  | |   |   | |  | | ║ |   | |
| o ║ o ║ o |  | o ║ o ║ o |  | o ║ o - o |  | o ║ o ║ o |  | o ║ o ║ o |
+===+===+===+  +===+===+===+  +===+=======+  +===+===+===+  +===+===+===+
+===+=======+  +=======+===+  +===========+  +===========+  +=======+===+
| o ║ o - o |  | o - o ║ o |  | o - o - o |  | o - o - o |  | o - o ║ o |
| |   |   ══+  | |   |   | |  | |   |   ══+  +═══  |   ══+  +═══  |   | |
| o - o - o |  | o ║ o - o |  | o ║ o - o |  | o - o - o |  | o - o - o |
| |   |   | |  | | ║ |   ══+  | | ║ |   ══+  | |   |   | |  | |   |   ══+
| o ║ o ║ o |  | o ║ o - o |  | o ║ o - o |  | o ║ o ║ o |  | o ║ o - o |
+===+===+===+  +===+=======+  +===+=======+  +===+===+===+  +===+=======+
n=4 sample
+===+===+===+===+  +=======+===+===+
| o ║ o ║ o ║ o |  | o - o ║ o ║ o |
| |   |   |   | |  +═══  | ║ |   | |
| o - o - o - o |  | o - o ║ o - o |
+═══  |   |   ══+  | |   | ║ |   ══+
| o - o ║ o - o |  | o ║ o ║ o - o |
| |   | ║ |   ══+  | | ║ |   |   | |
| o ║ o ║ o - o |  | o ║ o - o ║ o |
+===+===+=======+  +===+=======+===+
n=5 sample
+===+===+===+===+===+
| o ║ o ║ o ║ o ║ o |
| |   | ║ | ║ |   | |
| o - o ║ o ║ o - o |
| |   |   |   |   ══+
| o ║ o - o - o - o |
| | ║ |   |   |   ══+
| o ║ o ║ o ║ o - o |
| | ║ | ║ | ║ |   | |
| o ║ o ║ o ║ o ║ o |
+===+===+===+===+===+
n=6 sample
+===========+===+===+===+
| o - o - o ║ o ║ o ║ o |
| |   |   | ║ | ║ | ║ | |
| o ║ o ║ o ║ o ║ o ║ o |
| | ║ | ║ |   |   | ║ | |
| o ║ o ║ o - o - o ║ o |
| | ║ | ║ |   |   | ║ | |
| o ║ o ║ o ║ o ║ o ║ o |
| | ║ | ║ | ║ | ║ |   | |
| o ║ o ║ o ║ o ║ o - o |
| | ║ | ║ | ║ | ║ |   ══+
| o ║ o ║ o ║ o ║ o - o |
+===+===+===+===+=======+
Examples of spanning trees where some of the walls do not start at a border, so they are not included in this sequence.
+===+===+=======+  +===============+
| o ║ o ║ o - o |  | o - o - o - o |
| | ║ |   |   | |  +══════════   | |
| o ║ o - o ║ o |  | o - o - o ║ o |
| | ║ ═════ ║ | |  | |   ══  | ║ | |
| o ║ o - o ║ o |  | o ║ o - o ║ o |
| |   |   | ║ | |  | |   ═════   | |
| o - o ║ o - o |  | o - o - o - o |
+=======+=======+  +===============+

Prog

(PARI) \\ See Link section for program file.
vector(20, n, A375770(n)) \\ Andrew Howroyd, Sep 03 2024

Crossrefs

Cf. A349718, A375817 (not reduced for symmetries), A375859 (up to rotations), A375860 (up to symmetries of rectangle).

Sequence in context: A098270 A262738 A271467 * A212471 A157867 A116156

Adjacent sequences: A375767 A375768 A375769 * A375771 A375772 A375773

Keyword

nonn

Author

Lars Blomberg, Aug 27 2024

Extensions

a(1) set to 1 and a(9) onwards from Andrew Howroyd, Aug 31 2024

Status

approved