2
$\begingroup$

Suppose I have an infinite grid. How many sets of grid points are there that contain $N$ contiguous grid points, and include the grid point at the origin?

So for example, if $N$ = 2, then there are 4 possibilities on a square grid:

0#0  000  000  000
0#0  0##  ##0  0#0
000  000  000  0#0  

(Here I have not counted diagonal neighbors as being contiguous.) Is there a name for this quantity? Are there known formulas or tabulated values?

$\endgroup$
2
  • $\begingroup$ So this is in $\mathbb R^3 $? And by $(x_0,y_0,z_0) , (x_1, y_1, z_1)$ contiguous, do you mean that Min{(x_0-x_1, y_0-y_1, z_0-z_1) }=1? $\endgroup$ – user99680 May 28 '14 at 0:55
  • $\begingroup$ In my case, I'm interested in a two dimensional square lattice. But certainly the question can be generalized to any type of lattice in any number of dimensions. In the case of a square grid, by contiguous I mean that $\left|x_0-x_1\right|+\left|y_0-y_1\right|=1$. $\endgroup$ – Max Radin May 29 '14 at 1:55
2
$\begingroup$

Given an $n$, the number you want is $$nP(n)$$ where $P(n)$ is the number of fixed polyominoes of size $n$. A fixed polyomino in your terminology is just a set of contiguous grid points without the specification that it must include the origin. The origin specification means we want to multiply the number of fixed polyominoes by $n$, because each of the $n$ points on a fixed polyomino could be the base point.

You can find a list of the number of fixed polyominoes here: OEIS A001168.

$\endgroup$
5
  • $\begingroup$ Link is no longer working $\endgroup$ – Code Whisperer Jan 18 '18 at 21:55
  • $\begingroup$ @CodeWhisperer Thanks for letting me know. It is updated now. $\endgroup$ – Peter Woolfitt Jan 18 '18 at 22:56
  • $\begingroup$ It is greater than that because you can orient the polyomino in various ways. Taking an I pentomino there are five positions horizontally and five positions vertically. For some pentominos there are as many as $40$ positions because we have four orientations, two reflections, and five squares that could be the origin. $\endgroup$ – Ross Millikan Jan 18 '18 at 23:59
  • $\begingroup$ @RossMillikan Unless I am mistaken, the "fixed" part of "fixed polyomino" takes care of that. For example there are 2 fixed polyominoes of size 2, and 6 fixed polyominoes of size 3. $\endgroup$ – Peter Woolfitt Jan 19 '18 at 16:57
  • $\begingroup$ @RossMillikan So when $n=5$, the number Max wants is $5P(5)=5\times63=315$ $\endgroup$ – Peter Woolfitt Jan 19 '18 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.