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?
  • 0
    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$?2012-09-10
  • 0
    Diagonally Up only2012-09-10
  • 0
    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?2012-09-10
  • 0
    All moves should have _UUDDUD_ a as _subsequence_ and it should be _consecutive_2012-09-10
  • 1
    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.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
    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?2012-09-10
  • 0
    @user1509863: What do you mean by a *down* move? Your only options are up, right, and diagonal.2012-09-10
  • 0
    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)2012-09-10
  • 0
    @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.2012-09-10
  • 0
    Down move is only allowed _after_ up move. I was asking what if that sequence of moves should include subsequence UUDDUD.2012-09-10
  • 0
    @user1509863: Are you allowed to go above $y=10$ or below $y=0$?2012-09-10
  • 0
    No. That's why we can only take down move after up. I'm also little bit confused by this, Exactly quetions is, If we say that all moves should have the subsequence of moves UUDDUD then how many ways are there?2012-09-10
  • 0
    @Makoto: If I’ve understood correctly and not made any silly mistakes, what I’ve added to my answer should cover the rest of the question.2012-09-10
  • 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
    Thanks Marc, I have edited question a bit, Can you look at it please?2012-09-10