3
$\begingroup$

Find the number of paths with length of 14 between (0,0) and (7,7) which do not go above the line $y=x+1$ and do not go beneath the line $y=x-3$ ? every step in the path is either right or up.

enter image description here

In order to find the number of the paths from (0,0) to (7,7) which don't go above the line $y=x+1$ I used the reflection Lemma, I did the same for the paths which don't go beneath the line $y=x-3$: I thought about using inclusion-exclusion. let F be the amount of the paths from (0,0) to (7,7) which means: $7+7 \choose 7 $ =3432

Let $F_1$ be the number of paths from (0,0) to (7,7) which GO above the line $y=x+1$ which means: $5+9 \choose 5$

and finally, Let $F_2$ be the number of paths from (0,0) to (7,7) which GO beneath the line $y=x-3$ which means: $11+3 \choose 3$

Now, I need to calculate: $F-(F_1+F_2-F_1\cap F_2$). I can't figure out how to find the intersection between the two.
Thanks in advance.

$\endgroup$
  • $\begingroup$ Have a look at this related question: math.stackexchange.com/questions/2207511/… $\endgroup$ – Jack D'Aurizio Mar 30 '17 at 10:34
  • $\begingroup$ I've seen this question before (I had it in my final exam actually). It has nothing to do with my question $\endgroup$ – Eran Mar 30 '17 at 11:00
3
$\begingroup$

You can find the number of paths crossing both lines by repeated use of the reflection lemma. The paths which cross the upper line reflect to paths to (5,9). Any which later crossed the lower line as well become paths that cross y = x + 7. So reflect again in the line y = x + 8 and these paths become ones ending at (13,1), of which there are 14. Similarly, paths which cross the lower line first and then the upper become, after two reflections, paths to (1,13) and there are again 14.

So $F-(F_1+F_2-F_1\cap F_2) = {14\choose7} - {14\choose5} - {14\choose3} + 28 = 1094$.

$\endgroup$
  • $\begingroup$ [+1] Interesting, and in the spirit of what Eran was looking for. Nevertheless, the method I propose in my answer is more general and does not necessitate witty computations. $\endgroup$ – Jean Marie Apr 2 '17 at 6:50
  • $\begingroup$ @JeanMarie. Thank you. (Not sure what a witty computation is.) The method does generalise fairly easily to any length of path and spacing between the two lines. If there's room for a path to cross outside the lines three (or more) times (on alternate sides) then further inclusion-exclusion rounds are needed, Your method certainly copes better with longer paths. $\endgroup$ – David Hartley Apr 2 '17 at 8:52
3
$\begingroup$

@Jack D'Aurizio.

Here is an approach using linear algebra:

Let us call "admissible" a path situated between the given lines.

Let us define $A_k=(k,k+1), \ \ B_k=(k+1,k), \ \ C_k=(k+2,k-1)$ for $k=1\cdots5.$

(blue dots on figure below)

enter image description here

Let $a_k,b_k,c_k$ the number of admissible paths starting in $O(0,0)$ ending in $A_k,B_k,C_k$ resp.

The only thing is to convince oneself that these numbers are governed by the following iteration:

$$\tag{1}\begin{cases}a_{n+1}&=&a_n&+&b_n&&\\b_{n+1}&=&a_n&+&2b_n&+&c_n\\c_{n+1}&=&&&b_n&+&c_n\end{cases}$$

(coefficient 2 for $b_n$ on the second line is justified by the fact that there are 2 ways to proceed from point $B_n$ to point $B_{n+1}$).

This process works for the major reason that any of the admissible paths from $(0,0)$ to $(7,7)$ crosses line $x+y=2k+1$ either in $A_k$, "exclusive or" in $B_k$ "exclusive or" in $C_k$ (this could be phrased in terms of imbricated partitions of the set of admissible paths).

(1) can be expressed under the form of a matrix-vector iteration:

$$\tag{2}\underbrace{\begin{pmatrix}a_{n+1}\\b_{n+1}\\c_{n+1}\end{pmatrix}}_{V_{n+1}}=\underbrace{\begin{pmatrix}1&1&0\\1&2&1\\0&1&1\end{pmatrix}}_M\underbrace{\begin{pmatrix}a_{n}\\b_{n}\\c_{n}\end{pmatrix}}_{V_{n}} \ \ \ \ \ \ \text{with} \ \ \ \ V_1=\begin{pmatrix}a_1\\b_1\\c_1\end{pmatrix}=\begin{pmatrix}2\\3\\1\end{pmatrix}$$

It suffices then to compute $V_5=M^4 V_1$ in order to get $a_5,b_5,c_5$.

The final result will be:

$$\tag{3}2a_5+3b_5+c_5=1094.$$

Remark 1: coefficients 2,3,1 in (3), which are the same as the coefficients of $V_1$ in (2), are found by looking at the different ways to connect $O(0,0)$ to $A_1,B_1$ or $C_1$ and the same for connecting $A_5,B_5$ or $C_5$ to terminal point $(7,7)$.

Remark 2: I just realized that, instead of considering 3 series of points $A_k,B_k,C_k$, it was enough to consider the 2 series $D_k,E_k$ of intermediate points with coordinates $D_k=(k,k)$ and $E_k=(k+1,k-1)$ ($k=1 \cdots 6$) giving rise to the simpler computation:

$$\begin{pmatrix}2&1\end{pmatrix}\begin{pmatrix}2&1\\1&2\end{pmatrix}^5\begin{pmatrix}2\\1\end{pmatrix}=1094.$$

$\endgroup$
  • $\begingroup$ @G Cab As you like combinatorics, here is a nice issue. $\endgroup$ – Jean Marie Apr 6 '17 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.