# Number of connected partitions (or labelings) in a grid graph

Let $$G$$ be a 2D lattice graph (undirected) of size $$W\times H$$. Each "inner" vertex has $$4$$ adjacent vertices, whereas "boundary" vertices have $$2$$ or $$3$$ adjacent vertices, whether they are at a corner or border. Here is an example with $$W=4$$ and $$H=3$$ :

$$\begin{array}{ccccccc} O & - & O & - & O & - & O\\ | & & | & & | & & |\\ O & - & O & - & O & - & O\\ | & & | & & | & & |\\ O & - & O & - & O & - & O\\ \end{array}$$

I wish to partition $$G$$ into $$n$$ subgraphs. Each vertex can be labeled with an integer from $$1$$ to $$n$$. I would like to count the number of possible "connected labelings" of $$G$$, as a function of $$W$$, $$H$$ and $$n$$. In image processing, we would call this a segmentation, with non-empty and connected regions. In my "connected labeling", two properties should be verified :

1. non-emptiness : have at least one vertex per label
2. connection : each subgraph made up of vertices labeled i should be connected

Without any constraint, there are $$n^{WH}$$ possible labelings. If we add the non-emptiness constraint, we should remove the labelings having only 1, 2, ... n-1 labels, which gives $$n^{WH} - \sum_{k=1}^{n-1} {n\choose k}k^{WH}$$ But, then, how to handle the connectedness constraint?