Ponder This Challenge - June 2022 - Counting odd polyominoes

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) \Leftrightarrow a<c \vee (a=c \wedge b\le d)$

2. ("down-up and then right-left"): $(a,b) \le_2 (c,d) \Leftrightarrow 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

• Click here to view the solution

  June 2022 Solution:

  The number of odd polyominoes is

  0, 1, 3, 11, 35, 108, 380, 1348, 5014, 18223, 67634, 252849, 950346, 3602437, 13697333, 52293534, 200399576,

  770410271, 2970369338, 11482572252

  One way to obtain this sequence is by a slight modificationof Redelmeier’s algorithm for counting polyominoes. This algorithm generates each polyomino once, without repitition, and for every such polyomino the permutation can be explicitly computed.

Solvers

• *Paul Revenant (1/6/2022 7:56 PM IDT)
• *Bert Dobbelaere (2/6/2022 7:13 AM IDT)
• *Gareth Ma (2/6/2022 12:21 PM IDT)
• *Uoti Urpala (2/6/2022 4:18 PM IDT)
• *Phil Proudman (2/6/2022 9:39 PM IDT)
• *Sanandan Swaminathan (3/6/2022 6:05 AM IDT)
• *Dominik Reichl (3/6/2022 3:36 PM IDT)
• *Vladimir Volevich (4/6/2022 12:12 AM IDT)
• *Anders Kaseorg (4/6/2022 9:32 AM IDT)
• Gary M. Gerken (4/6/2022 3:03 PM IDT)
• *Andreas Stiller (4/6/2022 5:27 PM IDT)
• *Alper Halbutogullari (4/6/2022 7:55 PM IDT)
• *David Greer (4/6/2022 11:32 PM IDT)
• *Lawrence Au (5/6/2022 7:23 AM IDT)
• *John Tromp (5/6/2022 9:49 AM IDT)
• *Bertram Felgenhauer (6/6/2022 12:29 AM IDT)
• Lorenz Reichel (7/6/2022 7:18 AM IDT)
• Franciraldo Cavalcante (9/6/2022 11:30 PM IDT)
• *Daniel Chong Jyh Tar (10/6/2022 2:44 AM IDT)
• Balakrishnan V (10/6/2022 7:43 AM IDT)
• *Harald Bögeholz (12/6/2022 4:57 AM IDT)
• Daniel Bitin (12/6/2022 11:50 AM IDT)
• Ali Gurel (12/6/2022 4:43 PM IDT)
• *Latchezar Christov (13/6/2022 11:50 AM IDT)
• Reda Kebbaj (13/6/2022 8:20 PM IDT)
• Graham Hemsley (15/6/2022 9:31 AM IDT)
• *Dieter Beckerle (15/6/2022 1:55 PM IDT)
• Daniel Johnson-Chyzhykov (24/6/2022 3:32 AM IDT)
• Tim Walters (25/6/2022 2:43 AM IDT)
• *Nyles Heise (27/6/2022 5:06 AM IDT)
• Marco Bellocchi (27/6/2022 9:20 PM IDT)
• John Goh (28/6/2022 9:44 AM IDT)
• *Antonio García Astudillo (28/6/2022 10:29 PM IDT)
• *Karl Mahlburg (29/6/2022 1:47 PM IDT)
• Michael Moffitt (30/6/2022 2:51 PM IDT)
• *Andrew Milas (1/7/2022 9:50 AM IDT)
• *Kang Jin Cho (1/7/2022 2:03 PM IDT)
• FabioMichele Negroni (1/7/2022 6:08 PM IDT)
• Todd Will (1/7/2022 8:26 PM IDT)
• *Stéphane Higueret (2/7/2022 9:11 AM IDT)
• Shouky Dan & Tamir Ganor (3/7/2022 8:30 AM IDT)
• *Motty Porat (3/7/2022 11:54 PM IDT)
• *Li Li (5/7/20228:39 PM IDT)