4
$\begingroup$

Consider $\mathbb{Z}^2$ as an infinite grid where the nodes are elements , choose a startpoint $x$ and an endpoint $y$.
Let $n$ be a natural number, we would like to know the number of paths from $x$ to $y$ with exactly length $n$.
For a path $p : \{1,...,n\} \to \mathbb{Z}^2$ to be a valid solution it has to satisfy following conditions:

  1. $p(1) = x$ and $p(n) = y$.
  2. The path is injective, meaning $p(i) \neq p(j)$ if $i \neq j$.
  3. $p(i+1) = p(i) \pm (1,0)$ or $p(i+1) = p(i) \pm (0,1)$.

If we discard the second condition the problem was solved over here.
I do not understand why the given recusive form is a solution to the problem posed over there.
Perhaps understanding why that solution is correct would be helpfull for this problem.

example

Without loss of generality we can asume $x = (0,0)$ let $y = (1,1)$ clearly there will be no paths of uneven length.
The sequence for the first 10 even numbers is: $(2 , 4, 16, 76, 396, 2164, 12240, 71024, 20436, 2528780)$.
Graphed on a semilogarithmic scale: example.
We can see an exponential-like graph.
(this of course is only an example for $y = (1,1)$ it would be nice to have a closed form for all $y$)

I tried some other examples too they all seem to display exponential-like behavior when they are not zero, I cannot calulate a lot of terms but it seems like it grows a bit faster than exponential: $t_n/t_{n-1}$ seems to grow.
For the example from (0,0) to (1,1) the terms the sequence of fractions are approximately $(2, 4, 4.75, 5.21, 5.46, 5.66, 5.80, 5.92, 6.01) $
Graph:

graph

It seems like the fractions possibly converge.

basecase

If we expect to prove an explicit or recursive form the proof will probably be with induction on $n$.
Here I prove the basecase: the number of different paths with minimal distance, the proof will be in the more general setting of $\mathbb{Z}^p$.

Let $x=(0,0, ... ,0)$, $y = (y_1, y_2, ... , y_p)$.

For a path $p:\{1,2, ...,d\} \to \mathbb{Z}^p $ from $x$ to $y$ to be of minimal length it is neccesary and sufficient that $p$ is monotone in every component.
Since $p$ has to end in $y$: $\sum_i(\delta_i) = \sum_i(p(i+1) - p(i)) = y$.
Here $\delta_i \in \{\mbox{sign(}y_j)\cdot e_j | j \in \{1,2,...,p\}\}$
$e_j$ is the j'th basis vector for $\mathbb{Z}^p$ in the standard basis.
Every permutation of the $\delta_i$'s will result in an alternative path of minimal length from $x$ to $y$. Therefor the number of paths of minimal length is equal to $$\frac{(d-1)!}{\lvert y_1\rvert!\cdot \lvert y_2 \rvert!\cdot ...\cdot \lvert y_p \rvert!}$$ $$\tag*{$\blacksquare$}$$

$\endgroup$
  • $\begingroup$ What conditions do we have to impose on a set of n-2 nodes so that there is exactly one path from x to y of length n going through the nodes? Does every path satisfy the condition that there is exactly one path through the collection of nodes? If the answer on the second question is true, the sets satisfying the first question map one-to-one onto paths therefor there will be equally many of them as there are paths of length n. (I could not find any counterexamples to the second question) $\endgroup$ – A. Van Werde May 23 '17 at 12:00
  • $\begingroup$ never mind: counterexample $\endgroup$ – A. Van Werde May 23 '17 at 12:07
1
$\begingroup$

There is good news and bad news. The good news is that there is a nice formula for the number of general paths in $\mathbb{Z}^2$ from one point to another as a sum of multinomial coefficients, as opposed to the recursive formula that you linked to. Also, it's straightforward to generalize this formula to higher dimensions. The bad news is that enumeration of injective paths probably requires the inclusion-exclusion principle, so the resulting formula won't be nearly as nice.

For general paths, let $x$ and $y$ be points in $\mathbb{Z}^2$, let the (signed) horizontal and vertical displacements between $x$ and $y$ be $h$ and $v$ (in $\mathbb{Z}$), and let $P_{x,y,n}$ be the number of paths of length $n$ between points $x$ and $y$. A path is equivalent to a sequence of moves to the left, right, up or down. Let $l, r, u, d \ge0$ be the number of such moves, respectively. Then, considering the total number of moves, $$l+r+u+d=n$$ and considering the horizontal and vertical displacements $$r-l=h,\quad u-d=v.$$ If $l,r,u,d$ satisfy these conditions, there are exactly the multinomial coefficient $\binom{n}{l,r,u,d} $ paths from $x$ to $y$ in $n$ steps. So, $$P_{x,y,n}=\sum_{l,r,u,d}\binom{n}{l,r,u,d},$$ where the indices of the sum are non-negative integers satisfying the three conditions. You can solve the system of three equations in four variables to rewrite the sum with a single index, for instance $$P_{x,y,n}=\sum_{l\ge0}\binom{n}{l,l+h,\frac{n-h-v}2-l,\frac{n-h+v}2-l}.$$

Now for the case of injective paths, we can use the inclusion-exclusion principle. From the collection of general paths, subtract those that have at least one point of intersection (in time and space), leaving $P_{x,y,n}-\sum_{m,z}P_{x,z,m}P_{z,y,n-m}.$ However, this subtracts paths with at least two points of intersection twice, so we have to add these back in, leaving $$P_{x,y,n}-\sum_{m,z}P_{x,z,m}P_{z,y,n-m}+ \sum_{m_1,m_2,z_1,z_2}P_{x,z_1,m_1}P_{z_1,z_2,m_2}P_{z_2,y,n-m_1-m_2}-\cdots,$$ etc. If there is a more direct enumeration of the injective paths avoiding the use of the inclusion-exclusion principle, I'd be surprised (but pleasantly so).

$\endgroup$
  • $\begingroup$ I was thinking of using the inclusion-exclusion principle in the way you did but was unable to implement it myself, thanks! Can the general path reasoning be generalised to grids with diagonals filled in etc. or would this result in insufficient information to actually solve the system? (it appears to me this would result in needing another reasoning?) $\endgroup$ – A. Van Werde May 29 '17 at 9:19
  • $\begingroup$ I'm not 100% sure what you mean by a "grid with the diagonals filled in". If, by chance, you mean that you have to avoid the diagonal, then I agree that sounds like a completely different problem. $\endgroup$ – Rus May May 29 '17 at 11:20
  • $\begingroup$ Sorry, my intention was that apart from having as possible moves $\pm (0,1)$ and $\pm (1,0)$ also having $\pm (1,1)$ and $\pm(-1,1)$,( possibly generalising to a set of random moves of the form $(\delta_x,\delta_y)$.) $\endgroup$ – A. Van Werde May 29 '17 at 17:59
  • 1
    $\begingroup$ Oh, in that case there is an easy fix. Just add variables four more variables for the diagonal moves: ne, se, sw, nw. Then, instead of choosing from four variables, you would choose from eight. Of course, the three equations would have to account for the diagonal moves, but everything else should go the same. $\endgroup$ – Rus May May 29 '17 at 21:02

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.