Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple polyominos overlap.)

For instance, for $n=3$, the fixed 3-polyominos are:

```
###  #..  ##.  ##.  #..  .#.
...  #..  #..  .#.  ##.  ##.
...  #..  ...  ...  ...  ...
```

and these polyominos all embed in the following shape with 5 cells, which is the best possible:

```
.#.
###
.#.
```

More generally, a suitable shape for arbitrary $n$ is the $n \times n$ square (with $n^2$ cells) and a naive lower bound would be $2n-1$ cells (necessary to embed the horizontal and vertical line $n$-polyomino).

I define an integer sequence $S_n$ to be the minimal number of cells of a shape in which all $n$-polyominos embed, and I am interested in understanding this sequence. In particular, specific questions are:
- **Can we always find an optimal shape that fits into an $n \times n$ square?** (this seems intuitively reasonable but I do not know how to prove it)
- **Can we prove that, asymptotically, $S_n = \Theta(n^2)$?** (the challenge is to show an $\Omega(n^2)$ lower bound -- maybe this is already possible by simply looking at a subset of the polyominos, but I couldn't see how to do it)

More generally, **has this sequence already been studied**?

To understand what happens here, I was able to compute by bruteforce computer search the first values of $S_n$, *making the assumption* that optimal shapes always fit in an $n$ by $n$ square (first point above) -- these values may turn out not to be optimal if this assumption is wrong:

- We have $S_1 = 1$, $S_2 = 3$ (easily), and $S_3 = 5$ (see above)
- We have $S_4=9$ with a surprising shape:
```
..#.
.##.
####
.##.
```
- We have $S_5 = 13$, with the unsurprising shape:
```
..#..
.###.
#####
.###.
..#..
```
- We have $S_6 = 18$ with a surprising shape:
```
..##..
..##..
######
#####.
..##..
..#...
```
- We have $S_7 = 24$, the shape is similar to $n=5$ but with a hole:
```
...#...
..###..
.#.###.
#######
.#####.
..###..
...#...
```
- I do not know $S_8$

There are matching sequences for these terms in OEIS, but their definitions do not seem relevant... **Edit:** maybe https://oeis.org/A203567 https://www.sciencedirect.com/science/article/pii/S0012365X01003570 would be worth investigating.

Acknowledgement: This question is by [Thomas Colcombet](https://www.irif.fr/~colcombe/) and [Antonio Casares](https://www.labri.fr/perso/acasaressant/).

**Edit:** fixed the values of $S_5$ and $S_7$, many thanks a lot to @RobPratt for noticing and reporting the errors!