June 2022 - Challenge
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:
- ("left-right and then down-up"): (a,b) \le_1 (c,d) \Leftrightarrow a<c \vee (a=c \wedge b\le d)
- ("down-up and then right-left"): (a,b) \le_2 (c,d) \Leftrightarrow b<d \vee (b=d \wedge a\ge c)
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!).
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
01/06/2022 @ 11:30:00 AM EST
Solution:
04/07/2022 @ 12:00 PM EST
List Updated:
02/08/2022 @ 11:30 AM EST
People who answered correctly:
*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)