How to count the number of connected shapes for $n$ cells on a hexagonal lattice?

282 Views Asked by At

On a hexagonal lattice, we can always definitely say if two cells are adjacent or not. I call a set of $n$ marked cells a 'connected shape' if we can trace a path through all of them without going through some other cell.

Here is the picture representing possible connected shapes for $1,2,3,4$ cells:

enter image description here

How do we compute a number of distinct connected shapes made from $n$ cells on a hexagonal lattice?

I marked red three shapes which have a 'twin' which can't be obtained by rotation. We can either count such shapes as two different shapes (one obtained from another by reflection) or as the same shape. It depends on what is more simple for large $n$.


I'm thinking to use hexagonal coordinates with constraints on the distances between them. We can take one cell as the origin. But this still gives too many equations for large $n$.

1

There are 1 best solutions below

5
On BEST ANSWER

It seems no closed form formula for this problem can be found in the literature.

Here is a paper in which the number of different possible connected configurations of $n$ hexagons (ignoring rotational symmetries) for $n\leq 35$ is listed (on p. 24).

This OEIS gives the same number for $n \leq 21$, but here taking symmetries into consideration.


Note: The OIES-page was found by @Gerry Myerson - if he would like to answer, I will gladly delete this one.