Given a $2 \times N$ Tile , how to find the number of ways to partition it into $M$ parts ?
Meaning of a part : Cells having same number which are adjacent to each other form a part .
Lets take $N = 5$ , so an example tile looks like :
1 1 1 2 2
3 3 2 2 1
This tile has 4-parts to it :
Part-1 : (1 1 1)
Part-2 :
(X 2 2)
(2 2 X)
Part-3 : (3 3)
Part-4 : (1)
Each cell can be assigned any number between $1$ and $K$ , how many ways exist to partition the tile into "M" parts ?
Number of different tile-configurations possible are : $k^x$ , where $x = 2n$
Hint: You can build a recursion out of it. Notice that either the last column has the same piece or two of them. Call $A_n\in \mathbb{Z}[q]$ the polynomial such that $$A_n(q)=\sum _{i=1}^{2n}A_{n,i}q^i,$$ where $A_{n,i}$ is the number of such tilings with $i$ parts such that the last column has just one part and $B_n$ is such that $$B_n(q)=\sum _{i=1}^{2n}B_{n,i}q^i,$$ where $B_{n,i}$ are the tilings with $i$ parts and ends with a column having two parts. You are interested in $[q^m](A_n(q)+B_n(q)).$
One can build a recurrence by understanding how to connect the last column to the right so $$A_n(q) = A_{n-1}(q)+q(k-1)A_{n-1}(q)+(k-2)qB_{n-1}(q)+2B_{n-1}(q)$$ because you can either place a column of the same color as before, or change the color(so create a new part, that is why we multiply by $q$) or you can put a new part to a column of disconnected pieces. So you get $$A_{n}(q)=(1+q(k-1))A_{n-1}(q)+((k-2)q+2)B_{n-1}(q),$$ Analogously do it for $B_n$ getting $$B_{n}(q)=(q^2(k-1)(k-2)+2q(k-1))A_{n-1}(q)+(1+2q(k-2)+q^2((k-1)(k-2)+1))B_{n-1}(q),$$ where $A_1(q)=kq$ and $B_1(q)=k(k-1)q^2.$
You can try generating functions or any method you know for solving these systems of recurrences.