A375770 - OEIS

%I #18 Sep 04 2024 08:47:44

%S 1,1,10,149,3177,76258,1991098,56431302,1738662461,58282168670,

%T 2121623710614,83566630166058,3545346228604588,161250925229195536,

%U 7827463597195165900,403872784815626357788,22069190323151660044413,1273007854598883147607470,77288239799225577008977654

%N 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.

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

%H Andrew Howroyd, <a href="/A375770/b375770.txt">Table of n, a(n) for n = 1..100</a>

%H Andrew Howroyd, <a href="/A375770/a375770.gp.txt">PARI Program and formula</a>, Sep 2024.

%e a(2)=1:

%e +=======+

%e | o - o |

%e | |   | |

%e | o ║ o |

%e +===+===+

%e a(3)=10:

%e +===========+  +=======+===+  +=======+===+  +===+===+===+  +===========+

%e | o - o - o |  | o - o ║ o |  | o - o ║ o |  | o ║ o ║ o |  | o - o - o |

%e | |   |   | |  | |   |   | |  | |   | ║ | |  | |   |   | |  | |   |   ══+

%e | o ║ o ║ o |  | o ║ o - o |  | o ║ o ║ o |  | o - o - o |  | o ║ o - o |

%e | | ║ | ║ | |  | | ║ |   | |  | | ║ |   | |  | |   |   | |  | | ║ |   | |

%e | o ║ o ║ o |  | o ║ o ║ o |  | o ║ o - o |  | o ║ o ║ o |  | o ║ o ║ o |

%e +===+===+===+  +===+===+===+  +===+=======+  +===+===+===+  +===+===+===+

%e +===+=======+  +=======+===+  +===========+  +===========+  +=======+===+

%e | o ║ o - o |  | o - o ║ o |  | o - o - o |  | o - o - o |  | o - o ║ o |

%e | |   |   ══+  | |   |   | |  | |   |   ══+  +═══  |   ══+  +═══  |   | |

%e | o - o - o |  | o ║ o - o |  | o ║ o - o |  | o - o - o |  | o - o - o |

%e | |   |   | |  | | ║ |   ══+  | | ║ |   ══+  | |   |   | |  | |   |   ══+

%e | o ║ o ║ o |  | o ║ o - o |  | o ║ o - o |  | o ║ o ║ o |  | o ║ o - o |

%e +===+===+===+  +===+=======+  +===+=======+  +===+===+===+  +===+=======+

%e n=4 sample

%e +===+===+===+===+  +=======+===+===+

%e | o ║ o ║ o ║ o |  | o - o ║ o ║ o |

%e | |   |   |   | |  +═══  | ║ |   | |

%e | o - o - o - o |  | o - o ║ o - o |

%e +═══  |   |   ══+  | |   | ║ |   ══+

%e | o - o ║ o - o |  | o ║ o ║ o - o |

%e | |   | ║ |   ══+  | | ║ |   |   | |

%e | o ║ o ║ o - o |  | o ║ o - o ║ o |

%e +===+===+=======+  +===+=======+===+

%e n=5 sample

%e +===+===+===+===+===+

%e | o ║ o ║ o ║ o ║ o |

%e | |   | ║ | ║ |   | |

%e | o - o ║ o ║ o - o |

%e | |   |   |   |   ══+

%e | o ║ o - o - o - o |

%e | | ║ |   |   |   ══+

%e | o ║ o ║ o ║ o - o |

%e | | ║ | ║ | ║ |   | |

%e | o ║ o ║ o ║ o ║ o |

%e +===+===+===+===+===+

%e n=6 sample

%e +===========+===+===+===+

%e | o - o - o ║ o ║ o ║ o |

%e | |   |   | ║ | ║ | ║ | |

%e | o ║ o ║ o ║ o ║ o ║ o |

%e | | ║ | ║ |   |   | ║ | |

%e | o ║ o ║ o - o - o ║ o |

%e | | ║ | ║ |   |   | ║ | |

%e | o ║ o ║ o ║ o ║ o ║ o |

%e | | ║ | ║ | ║ | ║ |   | |

%e | o ║ o ║ o ║ o ║ o - o |

%e | | ║ | ║ | ║ | ║ |   ══+

%e | o ║ o ║ o ║ o ║ o - o |

%e +===+===+===+===+=======+

%e Examples of spanning trees where some of the walls do not start at a border, so they are not included in this sequence.

%e +===+===+=======+  +===============+

%e | o ║ o ║ o - o |  | o - o - o - o |

%e | | ║ |   |   | |  +══════════   | |

%e | o ║ o - o ║ o |  | o - o - o ║ o |

%e | | ║ ═════ ║ | |  | |   ══  | ║ | |

%e | o ║ o - o ║ o |  | o ║ o - o ║ o |

%e | |   |   | ║ | |  | |   ═════   | |

%e | o - o ║ o - o |  | o - o - o - o |

%e +=======+=======+  +===============+

%o (PARI) \\ See Link section for program file.

%o vector(20, n, A375770(n)) \\ _Andrew Howroyd_, Sep 03 2024

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

%K nonn

%O 1,3

%A _Lars Blomberg_, Aug 27 2024

%E a(1) set to 1 and a(9) onwards from _Andrew Howroyd_, Aug 31 2024