I came across a problem which reduces itself to computing the number of non-decreasing paths from $(0,0)$ to $(m,n)$ on a rectangular grid. This is however more general than the usual move horizontal/vertical one unit or even the variant where you can move diagonally in one square.

In fact you can move diagonally over all admissible rectangles, not only small squares. More precisely, I'm looking for a formula (if it can be found) for the number of sequences

$$ (0,0) = (a_1,b_1),(a_2,b_2),...,(a_k,b_k)=(m,n)$$ such that $(a_i),(b_i)$ are non-decreasing and $(a_i+b_i)$ is strictly increasing.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.