Number of $k$-cuts of grid graphs

Question

Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$. Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on the number of simple $st$-path using those edges.

If I see the grid as a box in the plane, I can visualize an $st$-path as a rectilinear curve cutting this box. In this way I can associate each cell of the grid to either one or the other partition, getting as a trivial upper bound the value of $2^{n^2}$. Is there any better?

I also thought that, if I am considering only the paths using the $k$ given edges on the upper line, then I can map each of these paths to a cut of the grid graph into $k+1$ partitions. Do you know whether any non-trivial upper bound on this number is known?

Thanks for the help!

Answer 1

Consider this variation: we want to find number of paths which goes from $(1,1)->(n-2,n)$ in $(n-2)\times n$ solid grid, this can be done in almost $2^{n(n-2)}$ possible ways. Then is simple to convert it to your case. Just go up one step, then go left $n$ steps, again up one step and then right $n$ steps. That path covers all of that $k$ edges, and these are just restricted versions, that means independent to $k$, the upperbound is big : $2^{O(n^2)}$.