Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected?


By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we choose all the "1" sites and all the "0" sites are not chosen. Then 



```
00000
00100
00100
00110
00000

```

is connected and 



```
00000
00100
00010
00010
00000

```

is not connected.


A more difficult question would be, how many ways could we choose sites. Such that there are at most 2 connected "island"(or component):


For example:



```
00001
00001
00110
00100

```

has 2 connected component and



```
00001
00100
00010
00000

```

has 3 connected component.


The ultimate question is, given a cube size of n by m by k, how many ways could we choose sites, such that there are at most j connected components?


I face this question in my research in designing algorithm for material science. Thank you:)



enumeration of connected blocks in finite size square
This answer has two main points:


1. If you find a good upper bound in the case $j=1$, you will get a reasonable bound for small $j$.
2. You cannot get polynomial bounds with respect to $n,m,k$ for any $j\geq1$. (The hope for polynomial bounds was expressed in a comment.)


Let $N(n,m,k;j)$ denote the number of choices on the $n\times m\times k$ block producing at most $j$ connected components.
If we make $i$ choices with a single connected component and put them together (take the pointwise maximum if you regard each choice as a function taking values in $\{0,1\}$), we get a situation with at most $i$ connected components.
This construction yields at most $N(n,m,k;1)^i/i!$ choices for each $i$, so we get the estimate
$$
N(n,m,k;j)
\leq
\sum\_{i=0}^j \frac1{i!} N(n,m,k;1)^i.
$$
(Actually $N(n,m,k;1)-1$ would also work since it is the amount of choices with exactly one component, but this difference is very small.)
My intuition is that this estimate is fairly good when $j$ is very small.
For large $j$ it is not very tight, since $N(n,m,k;\infty)=2^{nmk}$ but the estimate gives $e^{N(n,m,k;1)}$ which is way bigger.
Thus to estimate $N(n,m,k;j)$ for small $j$ the key thing is to estimate $N(n,m,k;1)$ well.


You cannot get upper bounds for $N(n,m,k;1)$ which are polynomial in $n,m,k$.
Let me write $[a,b]=\{a,a+1,\dots,b\}$ for integers $a<b$.
Take any function $f:[1,m]\times[1,k]\to[1,n]$.
Assign the value $1$ to the cell $(a,b,c)\in[1,n]\times[1,m]\times[1,k]$ iff $a\leq f(b,c)$.
(Imagine the graph of the function $f$.)
Now there is exactly one connected component of $1$s, and different choices of $f$ give different choices for the $1$s.
Therefore $N(n,m,k;j)\geq N(n,m,k;1)\geq n^{mk}$ for $j\geq1$, so there is no polynomial bound.


As I mentioned in a comment above, naive arguments give the bounds
$$
\sum\_{i=0}^j{nmk\choose i}
\leq
N(n,m,k;j)
\leq
2^{nmk}.
$$
(Choose only at most $j$ points or make any choice at all to get these bounds.)


As a summary, you have these bounds when $j\geq1$:
$$
\max\left\{\sum\_{i=0}^j{nmk\choose i},n^{mk},m^{nk},k^{nm}\right\}
\leq
N(n,m,k;j)
\leq
\min\left\{2^{nmk},\sum\_{i=0}^j \frac1{i!} N(n,m,k;1)^i\right\}.
$$
These bounds are not optimal, but give an idea of the growth rate.


