login
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.
6
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, 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
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