# Possible paths on a rectangular grid moving also diagonally

The objective is to calculate the number of ways in which you can reach the bottom right corner of a N x M rectangular grid from the top left corner. The hard part is that the problem says that you can move down, right, or diagonally downwards directions. I am used to normal problems in which you can only move down or right, so I don't really know how to solve this! Any help?

• These are the Delannoy numbers. – Brian M. Scott Oct 30 '16 at 23:07
• Use the reccurence relation :$U_{i,j}=U_{i-1,j}+U_{i,j-1}+U_{i-1,j-1}$ – hamam_Abdallah Oct 30 '16 at 23:08
• Aren't Delannoy numbers supposed to be used when moving diagonally only in one direction (down-right) in this case? Because the problem asks for BOTH diagonal directions, either down-right or down-left. – Mr Brain Teaser Oct 30 '16 at 23:14