\\ A360055: Number of L-connected free polyominoes with n cells.
\\ PARI program and formula by Andrew Howroyd, Jan 2023.

\\ References:
\\ G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, 
\\     Combinatorial aspects of L-convex polyominoes, European J. Combin. 28 (2007), no. 6, 1724-1741.
\\ A link to the above can be found in A126764 which covers the fixed case.

\\ The basic solution (see the reference) is that solutions consist of the union of a
\\ sequence of rectangles R_1 ... R_k on integer points, such that
\\   for i<j left(R_i) <= left(R_j) < right(R_j) <= right(R_i)
\\     and bottom(R_j) <= bottom(R_i) < top(R_i) <= top(R_j).
\\
\\ The nesting of rectangles is illustrated below.
\\          ___
\\     ____|   |_____
\\    |__            |
\\       |           |
\\       |____  _____|
\\           |_|
\\

\\ Enumeration formulas a functions.
\\ The generating functions given here have not been tested and may contain tyographic errors.
\\ They are given to assist in reading the PARI code which is definitive!


\\ 1. No symmetry (A126764)
\\ This is fully documented in the reference.
\\ The polyomino consists of a widest rectangle to which a stack of rectangles of decreasing width
\\ are placed above and below, so that their edges do not overlap.
\\ G.f.: 1 + Sum_{k>=1} (x^k/(1-x^k)) * B(k,x) where B(k,x) is the generating function for
\\ two stacks that are strictly narrower than k.
NoSym(n)={my(p=1 + O(x*x^n), f = p + 2*x - x^2, g = p, q = p); for(k=1, n, q += x^k*g*p/(1-x^k); my(h=f); f=2*f - (1-x^(k+1))^2*g; g=h; p /= (1-x^k)^2); q }

\\ 2. Diagonal reflection
\\ The polyomino construction starts with a largest square which is then extended upwards and downwards by an arbitrary number
\\ of rows keeping the same width and also to the left and right by identical amounts (so that the shape is now a cross with diagonal symmetry).
\\ A stack of rectangles of decreasing width are then placed above and below in a similar manner to the base case
\\ and duplicated to the left and right to maintain diagonal symmetry.
\\ G.f.: 1 + Sum_{k>=1} (x^(k^2)/(1-x^(2*k))^2) * B(k, x^2) where B(k,x) is defined as in the base case.
Diag(n)={my(p=1 + O(x*x^n), f = p + 2*x - x^2, g = p, q = p); for(k=1, sqrt(n), q += x^(k^2)*subst(g*p/(1-x^k)^2,x,x^2); my(h=f); f=2*f - (1-x^(k+1))^2*g; g=h; p /= (1-x^k)^2); q }

\\ 3. Vertical or Horizontal reflection
\\ Considered here is the case for a vertical line of symmetry. Either the line of symmetry runs through the middle of a column or between.
\\ In the first case we start with a rectangle of odd width and then add centred rectangles of decreasing odd width above and below. 
\\ Since the rectangles are centred the nesting conditions are automatic. The second case is similar but all rectangles have even width.
\\ G.f.: 1 + Sum_{k>=1} (x^(2*k)/(1-x^(2*k))) * Pe(k-1, x)^2 + (x^(2*k-1)/(1-x^(2*k-1)) * Po(k-1, x)^2
\\        where Pe(k,x) = Product_{j=1..k} 1/(1 - x^(2*j))
\\        and Po(k,x) = Product_{j=1..k} 1/(1 - x^(2*j-1)).
\\ It will be recognised that Pe(k,x) and Po(k,x) are the g.f.'s for the number of paritions into even and odd parts with parts of size at most 2*k.
Reflect(n)={my(pe=1 + O(x*x^n), po=pe, q=pe); for(k=1, (n+1)\2, q += x^(2*k)*pe/(1-x^(2*k)) + x^(2*k-1)*po/(1-x^(2*k-1)); pe /= (1 - x^(2*k))^2; po /= (1 - x^(2*k-1))^2); q} 

\\ 4. Rotation by 180 degrees.
\\ Guarantees both horizontal and vertical symmetry. (otherwise the nesting rule would be violated)
\\ Similar to the vertical case, but now the top and bottom are constrained to be identical.
\\ G.f.: 1 + Sum_{k>=1} (x^(2*k)/(1-x^(2*k))) * Pe(k-1, x^2) + (x^(2*k-1)/(1-x^(2*k-1)) * Po(k-1, x^2) where Pe and Po are defined as above.
R180(n)={my(pe=1 + O(x*x^n), po=pe, q=0); for(k=1, (n+1)\2, pe /= 1 - x^(4*k); po /= 1 - x^(4*k-2) ; q += x^(2*k)*pe + x^(2*k-1)*po); q+pe+po-1}

           
\\ 5. Rotation by 90 degrees
\\ Guarantees full symmetry.
\\ The line of symmetry will either run through the center column and row or between them.
\\ The construction starts with a single column and row of equal length or a pair of such columns and rows.
\\ Then identical L's of deceasing size are added into the four quarters.
\\ G.f.: 1 + Sum_{k>=0} x^(4*k+1) * Q(k, x^4) + x^(8*k+4) * Q(k, x^4)
\\     where Q(k, x) = Product_{k>=1} (1 + x^(2*k-1)). 
R90(n)={my(p=1 + O(x*x^n), q=0); for(k=0, (n-1)\4, q += x^(4*k+1)*p; p*= 1 + x^(8*k+4)); p + q}


\\ Final solution by Burnside
seq(n) = {Vec((R180(n) + NoSym(n) + 2*(Reflect(n) + Diag(n) + R90(n)))/8)}

\\ End