# How to enumerate all possible k-connected-components partition of a two dimensional 4-connected grid

Hi all:

Sorry for my bad wordy title, my question is:

Input:

Given a m*n 4-connected grid of points each of which is labelled with an integer $\in\{1,...,k\}$. We say a label configuration z is feasible (k-connected-components partition) if points of the same label are connected on the grid and there are k different labels in total.

Output:

How many different feasible configuration are there?