A375858 -id:A375858 - cp's OEIS frontend

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

Lars Blomberg, Aug 30 2024

nonn

This sequence contains some, but not all of the spanning trees in A007341, a(n)<A007341(n), for n>2.

See A375770 for examples.

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

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

Main diagonal of A375858.

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

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

Terms corrected and extended by Andrew Howroyd, Sep 03 2024

A375861 Array T(n,m) read by antidiagonals: In an n X m grid draw straight walls between cells, starting at a border, such that the resulting figure is connected and has only one-cell wide paths; T(n,m) is the number of solutions up to symmetries of the rectangle.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 5, 1, 1, 9, 19, 9, 1, 1, 19, 63, 63, 19, 1, 1, 35, 192, 298, 192, 35, 1, 1, 71, 576, 1246, 1246, 576, 71, 1, 1, 135, 1698, 4857, 6351, 4857, 1698, 135, 1, 1, 271, 5042, 18768, 29467, 29467, 18768, 5042, 271, 1, 1, 527, 14963, 72968, 134397, 152516, 134397, 72968, 14963, 527, 1

Offset: 1

Andrew Howroyd, Aug 31 2024

See A375770 and A375860 for additional explanation and illustration of solutions.

			Array begins:
===============================================
n/m | 1  2    3     4      5      6       7 ...
----+------------------------------------------
  1 | 1  1    1     1      1      1       1 ...
  2 | 1  2    5     9     19     35      71 ...
  3 | 1  5   19    63    192    576    1698 ...
  4 | 1  9   63   298   1246   4857   18768 ...
  5 | 1 19  192  1246   6351  29467  134397 ...
  6 | 1 35  576  4857  29467 152516  763479 ...
  7 | 1 71 1698 18768 134397 763479 3982186 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)

Main diagonal is A375860.

Cf. A375858 (not reduced for symmetry).

\\ A375861(n,m) defined in PARI link in A375770.

T(n,m) = T(m,n).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions