2
$\begingroup$

Just to clarify: This is the number of ways to go from point $(0,0)$ to point $(20,10)$ if the only directions allowed are right and up. The catch: Each of the ways must include precisely (only) $1$ instance of a "double right".

I know that all of the ways to go from $(0,0)$ to $(20,10)$ can be found by $C(30,20)$ or $C(30,10)$, but I'm having trouble wrapping my head around how to only include ways that have precisely $1$ double right.

$\endgroup$
5
  • $\begingroup$ Consider these 3 cases: starting with RRU, ending with URR, or having URRU anywhere in the sequence. Also, just to make sure, you need to have a total of 20 U and 10 R, correct? It is impossible if you try to do it the other way around. $\endgroup$
    – Ryan
    Sep 30, 2013 at 18:30
  • $\begingroup$ Indeed breaking it into those 3 cases occurred to me shortly after posting. No, I believe that it is supposed to be (x,y) so 20 R and 10 U. $\endgroup$
    – Akirez
    Sep 30, 2013 at 18:49
  • 1
    $\begingroup$ There will be more than one instance of RR if (20,10) corresponds to 20 R and 10 U... $\endgroup$
    – Ryan
    Sep 30, 2013 at 19:19
  • $\begingroup$ Sorry I need to further clarify: RRR would not violate the "precisely 1 instance of 2 rights". 1 R is ok, 3 R, etc.. $\endgroup$
    – Akirez
    Sep 30, 2013 at 19:47
  • $\begingroup$ If that is the situation, I think you can simplify your approach if you pretend that U, UR, URR, URRR, URRRR, etc... are discrete elements with attached cardinalities. Then your problem is reduced to finding all allowed combinations, and then taking all possible permutations. $\endgroup$
    – Ryan
    Sep 30, 2013 at 21:38

2 Answers 2

0
$\begingroup$

Imagine that your 'long right' was instead a single rightward step. Then, rather than going from $(0,0)$ to $(20,10)$ instead you would move from $(0,0)$ to $(20-k+1,10)$, where $k$ is the length of the 'long right' — but you would do it without any two consecutive rightward moves. What's more, since there's only one 'long right', we can replace any of the $j=20-k+1$ rightward moves by it and get a unique configuration (no two such configs can collide); this means that for each way of getting from $(0,0)$ to $(j, 10)$ without consecutive rightward moves, there are $j$ ways with one 'long right' move. So once we have the quantity $C_j$ of such ways, we can calculate the sum $\sum_kjC_j$ over all $k$ to get the final answer. In fact, since every value of $k$ corresponds to a unique value of $j$ and we never directly use the value of $k$, we may as well make our sum be over $j$ instead of $k$, and we'll consider it to be summed that way from here on out.

Now, let's look at that quantity $C_j$. Since now between any two rightward moves we know that there's at least one upward move, we can eliminate the first upward move between each of the $j-1$ pairs of consecutive moves to get a configuration where we instead have $j$ rightward moves and $10-(j-1)$ upward moves with no restrictions on them; contrariwise, corresponding to any one of these configurations of $j$ rightward moves and $10-(j-1)$ upward moves we have a unique configuration of $j$ rightward moves and $10$ upward moves by just re-inserting the $(j-1)$ upward moves we took out, one between each pair of rightward moves. (You may have seen this under the name 'Stars and Bars' at some point). Can you take it from here to see what $C_j$ must be, and then finish by calculating the original sum?

$\endgroup$
0
$\begingroup$

For each row of the grid we have $3$ different possibilities in what concerning the right directions moves:

  1. $0$ Right moves
  2. $1$ Right move
  3. $N$ sequential Right moves

So enter the new move $BigR$ corresponding to option $3$. We need to perform a path so that $ |\{R, right\ moves\}| + N =20 $. We also know that $0 \leq h=20-N\leq 9$ (thus we have exactly $10$ different chooses for $N$). Suppose now that the first move is exactly the $BigR$ move. After $2$ steps we are exactly in $(N,1)$, so $C(9,h)$ different paths are allowed( the same if $BigR$ is at row $10$). What happens instead if $BigR$ is in a general position? In the final path you have to perform exactly $h$ Right moves, in exactly $h$ differents rows (in total we have $11-1$ free rows). This means, fixed the $BigR$ move, we have $C(10,h)$ different paths. The number of positions in the grid that the $BigR$ move can occupy at row $i$ is $i+1$ if $i+N\leq 20$ or $21-N$ otherwise. Now it remains to multiply the number of possible position for $BigR$ with the number of shortened paths, to find all admissible paths between $(0,0)$ and $(20,10)$ with the $bigR$ of cardinality exacly $N$. Then varying $N$ to all possible values, you would obtain the answer. I hope this could be helpful. If I do some mistakes, please let me know.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .