\\ Author: Andrew Howroyd, Aug 2024
\\ Sequences related to the following problem by Lars Blomberg
\\ 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.

\\ Grid width:n, height:m, walls from top border are all zero length, at least one wall from bottom border of length m-1.
\\ The walls from the bottom border must have heights that are a unimodal sequence.
\\ The walls from the left and right borders have lengths dependent only on the bottom border wall heights. 
F(n,m) = if(m==1, 1, sum(k=1,n-1, binomial(k+m-2, m-1)*binomial(n-k+m-3, m-2)))

\\ Faster version that avoids summation.
F(n,m) = binomial(2*m+n-4, 2*m-2)

\\ Type 1 solutions. There is at least one wall from the top border that meets a wall from the border with
\\ a one-cell gap between them.
\\ In these solutions, there cannot be a wall from the left border that meets a wall from the right border with
\\ a one cell gap between them. These are also type 1, but counted by switching m and n.
B(n,m) = sum(k=1, n-1, sum(j=1, k, m^(n-k) * F(m,j) * F(m, k-j+1) ))

\\ Vertical line of symmetry.
V(n,m) = sum(k=1, n\2, m^(n\2-k+1) * F(m,k))
\\ Horizontal line of symmetry.
H(n,m) = if(m%2, F(n, (m+1)/2), 0)
\\ 180 degree rotation symmetry.
S(n,m) = if(m%2==1 || n%2==1, sum(k=1, n\2, m^((n+1)\2-k) * F(m,k) ), 0)
\\ Diagonal are 90 degree rotational symmetry are not possible with type 1 solutions. 

\\ Helper: walls from both the top border and the right border are all zero length.
E(n,m) = binomial(n+m-2, n-1)

\\ Type 2 solutions: These have walls from each edge that block each other in a cyclic fashion. (everything except type 1).
\\ So the bottom wall is blocked by the right; the right by the top; the top by the left and the left by the bottom.
\\ The four blocking walls delineate a central rectangle that must either have width 1 or height 1 (or both)
\\ C(n,m) is the case that the central rectangle has width = 1 and height > 1 and half of those with width = height = 1.
\\ Switching m and n gives the rest.
\\ The blocking walls also subdivide the periphery into 4 rectangles of varying sizes.
\\ Illustration: central rectangle is 2 X 1, the peripheral rectangles are 1 X 2, 4 X 1, 2 X 2, 3 X 1.
\\ In this example, only the 2 X 2 rectangle is further partitioned either with a wall from the right or from the bottom.
\\   ._._._._._.
\\   | | ._._._|
\\   |_._.   . |
\\   |_._._|_._| 
C(n,m) = sum(k=1, n-2, sum(j=2, m-1, sum(i=1, j-1, if(j-i>1,2,1)*E(k+1, i)*E(n-k, m-j)*E(m-i, k)*E(j, n-1-k) )))

\\ 90 degree rotational symmetry (when n = m)
R4(n) = if(n%2, E(n\2+1, n\2))
\\ 180 degree rotational symmetry.
R2(n,m) = if(n%2, sum(k=1, (m-1)\2, if(2*k<m-1,2,1)*E(m-k, n\2)*E(n\2+1, k)), 0)
\\ Reflective symmetry is not possible with type 2 solutions.

\\ Functions to compute sequences.

\\ n X n grid up to rotations and reflections.
A375770(n) = if(n==1, 1, (B(n,n) + V(n,n) + H(n,n) + S(n,n) + C(n,n) + 2*R4(n) + R2(n,n))/4)

\\ n X n grid (not reduced for symmetry).
A375817(n) = if(n==1, 1, 2*(B(n,n) + C(n,n)))

\\ n X n grid up to rotations.
A375859(n) = if(n==1, 1, (B(n,n) + S(n,n) + C(n,n) + 2*R4(n) + R2(n,n))/2)

\\ n X n grid up to symmetries of the rectangle.
A375860(n) = if(n==1, 1, (B(n,n) + V(n,n) + H(n,n) + S(n,n) + C(n,n) + R2(n,n))/2)

\\ n X m grid (not reduced for symmetry).
A375858(n,m) = if(n==1||m==1, 1, B(n,m) + B(m,n) + C(n,m) + C(m,n))

\\ n X m grid up to symmetries of the rectangle.
A375861(n,m) = {if(n==1||m==1, 1, (B(n,m) + V(n,m) + H(n,m) + S(n,m) + B(m,n) + V(m,n) + H(m,n) + S(m,n) + C(n,m) + R2(n,m) + C(m,n) + R2(m,n))/4)}