IBM Ponder This #290 · June 2022

Counting odd polyominoes

A polyomino is a generalization of dominoes and Tetris shapes: a connected set of cells on the 2D grid. Dominoes consist of two cells while Tetris shapes consist of four; a general polyomino has $n$ cells.
We consider two polyominoes to be distinct even if they can be rotated/reflected into one another. In this approach, there are 2 distinct domino shapes and 19 distinct Tetris shapes:

It is easy to check that the sequence of the number of polyominoes of size $n$ is $1,2,6,19,63,216,760,2725,9910,36446,135268,...$ (sometimes polyominoes counted this way are called fixed to differentiate from cases where symmetry is taken into account).

Since polyominoes are sets of 2D grid elements, we can associate a coordinate (a,b) with every cell, and we can use this to define order on cells. We define two such orders:

1. ("left-right and then down-up"): $(a,b){\le }_1(c,d)\iff a<c\vee (a=c\wedge b\le d)$

2. ("down-up and then right-left"): $(a,b){\le }_2(c,d)\iff b<d\vee (b=d\wedge a\ge c)$

Given a polyomino, we can sort its cells according to one of the orders and number them accordingly. Define a function $\pi (i)=j$ such that cell number $i$ in the first numbering is number $j$ in the second numbering.

For example:

It is easy to see that $\pi$ is a permutation. Recall that permutations can be either odd or even, according to the number of 2-cycles in a 2-cycle decomposition of the permutation.

If we count only polyominoes giving rise to odd permutations, we can see the resulting sequence starts with $0,1,3,11,35,108,380,1348,5014,18223,...$.

Your goal: Find the above sequence of odd polyominoes up to $n=18$.

A bonus "*" will be given for finding the sequence up to $n=20$ (or even larger values of $n$ - and tell me how you did it!).

Solution

Best opened after a real attempt

To be added.