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 :
- non-emptiness : have at least one vertex per label
- 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?
