3
$\begingroup$

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?
  • 1
    Since down moves $a$re forbidden in the first $p$lace, 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.2012-09-10

2 Answers 2

1

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.

  • 0
    @user1509863: Hey if you don't properly understand the question yourself, what's the point of asking __us__ to answer it? I suppose somebody is posing __you__ the question (and has not been very clear), and you should clear that up with that person. And try to answer yourself.2012-09-10
1

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. $

  • 0
    Than$k$s Marc, I have edited question a bit, Can you look at it please?2012-09-10