# How many paths possible in this grid given this specific conditions?

In a grid, There is a bottom-left point i, with co-ordinate (0,0) and top-right point j with co-ordinate (10,10). A person is standing at point i, He can go up (1 unit), right (1 unit) and diagonally (1 unit diagonally) given that person don't cross the grid limits. I have two questions here,

1. How many ways, He can go to i to j?
2. What if we say, all moves sould have the following sequence of moves, up,up,down,down,up,down then how many ways are there?
-
When he moves diagonally, must he move diagonally up, for instance from $\langle 3,4\rangle$ to $\langle 4,5\rangle$, or may he move diagonally down as well, for instance from $\langle 3,4\rangle$ to $\langle 4,3\rangle$? –  Brian M. Scott Sep 10 '12 at 4:44
Diagonally Up only –  user1509863 Sep 10 '12 at 5:20
Point 2. is unclear. Do you meant you want to have that sequence as a sequence of consecutive moves? Or just those moves somewhere, in that order? –  Marc van Leeuwen Sep 10 '12 at 7:18
All moves should have UUDDUD a as subsequence and it should be consecutive –  user1509863 Sep 10 '12 at 7:21
Since down moves are forbidden in the first place, I suppose you mean right moves instead. This is because the given set of moves corresponds to moves on a line where each step goes up, down, or stays in place, whence the down-right confusion. –  Marc van Leeuwen Sep 10 '12 at 8:34

Let $d$ be the number of diagonal moves; clearly $0\le d\le 10$. The $d$ diagonal moves account altogether for $d$ steps to the right and $d$ steps up, so he must also make $10-d$ moves to the right and $10-d$ moves up. That’s a total of $20-2d$ orthogonal moves, half to the right and half up, which may be taken in any order, for a grand total of $20-2d+d=20-d$ moves.

There are $\binom{20-d}d$ ways to choose which moves are diagonal, and then there are $\binom{20-2d}{10-d}$ ways to choose which of the remaining moves are up, so there are $\binom{20-d}d\binom{20-2d}{10-d}$ paths with $d$ diagonal moves and a grand total of

$$\sum_{d=0}^{10}\binom{20-d}d\binom{20-2d}{10-d}=\sum_{k=0}^{10}\binom{10+k}{10-k}\binom{2k}k\;.$$

You could calculate this longhand, or you could calculate the corresponding figure for smaller numbers than $10$: for $0$ I get $1$, for $1$ I get $\binom11\binom00+\binom20\binom21=3$, for $2$ I get $$\binom22\binom00+\binom31\binom21+\binom40\binom42=13\;,$$ and for $3$ I get $$\binom33\binom00+\binom42\binom21+\binom51\binom42+\binom60\binom63=1+12+30+20=63\;,$$ which is enough to justify trying the On-Line Encyclopedia of Integer Sequences. It reports $14$ matches, of which the first, A001850, gives the central Delannoy numbers, described as the number of paths from $(0,0)$ to $(n,n)$ in an $n\times n$ grid using only steps North, Northeast and East, which is exactly what you want. The tenth number is listed as $8,097,453$.

Added: The sequence UUDDUD, which I’ll call $S$, has no net effect and may be inserted at any point before the last two moves that increase the $y$-coordinate. As before, suppose that there are $d$ diagonal moves, so that there are $10-d$ up and $10-d$ right moves, not including $S$. Still not counting $S$, there are $10$ moves that increase the $y$-coordinate; call them $m_1,\dots,m_{10}$ in order. They may come in any order, and there are $\binom{10}d$ ways to choose which of them are the diagonal moves. $S$ may come before $m_1$ or between $m_k$ and $m_{k+1}$ for $k=1,\dots,8$, so there are $9$ places to insert $S$ into any of those $\binom{10}d$ possible sequences, for a total of $9\binom{10}d$ sequences of $S$ and the $10$ moves that increase the $y$-coordinate.

The remaining $10-d$ moves may be placed anywhere in the string. This is a standard stars and bars problem: there are $12$ possible places to put the moves, and $10-d$ indistinguishable moves to be placed, for a total of $\binom{10-d+11}{11}=\binom{21-d}{11}$ arrangements. The grand total is therefore

$$9\sum_{d=0}^{10}\binom{10}d\binom{21-d}{11}$$

paths. If I did the arithmetic correctly, this comes to $119,574,387$ paths.

-
What if we say, all moves sould have the following sequence of moves, up,up,down,down,up,down then how many ways are there? –  user1509863 Sep 10 '12 at 5:55
@user1509863: What do you mean by a down move? Your only options are up, right, and diagonal. –  Brian M. Scott Sep 10 '12 at 6:00
Down means, Going (0,0) from (0,1), Or you might consider it as an opposite of up. Here what if all moves should have that subsequence of moves. (up,up,down,down,up,down) –  user1509863 Sep 10 '12 at 6:11
@user1509863: From $\langle 0,0\rangle$ to $\langle 0,1\rangle$ is an up move; from $\langle 0,0\rangle$ to $\langle 1,0\rangle$ is a right move; and from $\langle 0,0\rangle$ is a diagonal move. A down move would be from $\langle 0,1\rangle$ to $\langle 0,0\rangle$, for instance, and that’s not allowed, so I still don’t understand what you mean, unless you’ve turned the $y$-axis upside-down. –  Brian M. Scott Sep 10 '12 at 6:15
Down move is only allowed after up move. I was asking what if that sequence of moves should include subsequence UUDDUD. –  user1509863 Sep 10 '12 at 6:36

The number of possible ways to get from $(0,0)$ to point $(i,j)$ is called the Delannoy number $D(i,j)$, with $i=j$ a central Delannoy number $D(i)$. You want the central number $D(10)=8097453$. One way to compute it, is to sum over all choices $0\leq d\leq10$ of numbers $d$ of diagonal steps, adding the multinomial coefficient $\binom{2n-d}{n-d,d,n-d}$ that computes the number of ways to permute $n-d$ horizontal, $d$ diagonal and $n-d$ vertical steps.

If you want to impose a consecutive subsequence UURRUR, this of course limits the number of solutions considerably. Imposing one such subsequence in a given position effectively reduces the remaining paths, after removal of the subsequence, to be one of the paths counted by $D(7)$; moreover there are $8$ possible positions $k$ such that the subsequence may start after $k$ steps $0\leq k\leq7$). That would give $8D(7)$ solutions; however there is room for more than one such subsequence, and those sequences which contain it more than once will be overcounted.

So a classical inclusion-exclusion argument says one should subtract the number of solutions containing the subsequence twice, then add again the number of solutions that contain the subsequence thrice (more than that is not possible, so it stops here; also note that I've used that the given subsequence can have no self-overlap, otherwise things would become rather complicated). For two subsequences we can choose their positions by fixing the numbers $k_1,k_2,k_3\geq0$ of steps before, between and after them, with $k_1+k_2+k_3=10-2*3=4$ for $\binom{4+3-1}4=\binom62=15$ possibilities, and similarly for three subsequences we can fix their positions by choosing $k_1,k_2,k_3,k_4\geq0$ with $k_1+k_2+k_3+k_4=10-3*3=1$ in $\binom{1+4-1}1=\binom43=4$ ways. All in all the outcome is $$\sum_{l=1}^3(-1)^{l-1}\binom{10-2l}{l}D(10-3l) =8\times48639-15\times321+4\times3=384309.$$

-
Thanks Marc, I have edited question a bit, Can you look at it please? –  user1509863 Sep 10 '12 at 5:31