# How many contiguous subsets of size $N$ does an infinite grid have?

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?

• 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? – user99680 May 28 '14 at 0:55
• 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$. – Max Radin May 29 '14 at 1:55

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.
• 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. – Ross Millikan Jan 18 '18 at 23:59
• @RossMillikan So when $n=5$, the number Max wants is $5P(5)=5\times63=315$ – Peter Woolfitt Jan 19 '18 at 17:06