"A vertical seam is a path of pixels connected from top to bottom in an image with one pixel in each row" - Wikipedia. For each pixel, if it is not on either edge, then it can either be connected to the pixel right below, the pixel diagonally left, or the pixel diagonally right. If it is on the edge, then the pixel can be connected to the pixel right below or diagonally to the side opposite of the edge.
I was wondering what the total number of possible vertical seams was for an n by m image (n rows and m columns, so a width of m and height of n).
So far I have an upper and lower bound, but I'm not sure how to move forward. For the lower bound, I got $2^{n-1} \cdot m$, since each pixel has at least 2 choices. For the upper bound, I initially got $3^{n-1} \cdot m$, but I reduced it to $3^{n-1} \cdot m - 2^n$.
Does anyone know a way to find an exact explicit formula?
The number of vertical seams in an $n$-row-by-$m$-column image, $S(n,m)$, is the same as the number of "smooth words" of length $n$ over a size-$m$ alphabet – a smooth word has adjacent letters differing by at most one. Knopfmacher, Mansour, Munagi and Prodinger gave the following formula: $$S(n,m)=\frac1{m+1}\sum_{j=1}^m(1+(-1)^{j+1})\cot^2\frac{j\pi}{2(m+1)}\left(1+2\cos\frac{j\pi}{m+1}\right)^{n-1}$$ All the sequences of seam counts are OEIS A188866.