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

Author

Lars Blomberg, Aug 27 2024

Keywords

• nonn

Comments

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

Examples

			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 |
+=======+=======+  +===============+
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100
• Andrew Howroyd, PARI Program and formula, Sep 2024.

Crossrefs

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

Programs

PARI

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

Extensions

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