Smallest region of the plane that contains all free n-ominoes On Math Stack Exchange, I asked a question about the smallest region that can contain all free n-ominos. 

I'd like to add this sequence to the On-Line Encyclopedia of Integer Sequences once I have more terms.

Example

A nine-cell region is the smallest subset of the plane that can contain all twelve free 5-ominoes, as illustrated below. (A free polyomino is one that can be rotated and flipped.)



(A twelve-cell region is the smallest subset of the plane the can contain all 35 free 6-ominoes.)



The Challenge

Compute upper bounds on the smallest regions of the plane that can contain all n-ominoes as a function of n.

Such a table begins:

n | size
--+-------
1 | 1*
2 | 2*
3 | 4*
4 | 6*
5 | 9*
6 | 12*
7 | 37
8 | 50
9 | 65

*These values are the smallest possible.




Example submission

1-omino: 1
#

2-omino: 2
##

3-omino: 4
###
 #

4-omino: 6
####
 ##

5-omino: 9
 #
#####
 ###

6-omino: 12
####
######
  ##

7-omino: &lt;= 37
#######
######
######
######
######
######




Scoring

Run your program for as long as you'd like, and post your list of upper bounds together with the shapes that achieve each.

The winner will be the participant whose table is lexicographically the earliest (with "infinity" appended to the shorter submissions.) If two participants submit the same results, then the earlier submission wins.

For example, if the submissions are

Aliyah: [1,2,4,6,12,30,50]
Brian:  [1,2,4,6,12,37,49,65]
Clare:  [1,2,4,6,12,30]


then Aliyah wins. She beats Brian because 30 &lt; 37, and she beats Clare because 50 &lt; infinity.
In the interest of getting the process started, here's a quick (but not very optimal) answer.

Pattern:

n = 8:
########
 ######
  #####
   ####
    ###
     ##


Take a triangle with length n - 1, stick an extra square onto the corner, and cut off the bottom square.

Proof that all n-ominos fit:

Note that any n-omino can fit in a rectangle with length + width at most n + 1.

If an n-omino fits in a rectangle with length + width at most n, it fits nicely in the triangle (which is the union of all such rectangles). If it happens to use the cut-off square, transposing it will fit in the triangle.

Otherwise, we have a chain with at most one branch.  We can always fit one end of the chain into the extra square (prove this with casework), and the rest fits into a rectangle with length + width at most n, reducing to the case above.

The only case where the above doesn't work is the case where we use both the extra square and the cut-off square.  There's only one such n-omino (the long L), and that one fits inside the triangle transposed.

Code (Python 2):

def f(n):
    if n &lt; 7:
        return [0, 1, 2, 4, 6, 9, 12][n]
    return n * (n - 1) / 2


Table:

 1:   1
 2:   2
 3:   4
 4:   6
 5:   9
 6:  12
 7:  21
 8:  28
 9:  36
10:  45
11:  55
12:  66
13:  78
14:  91
15: 105
16: 120
17: 136
18: 153
19: 171
20: 190
... more cases can be generated if necessary.