41
$\begingroup$

A triangular grid has $N$ vertices, labeled from 1 to $N$. Two vertices $i$ and $j$ are adjacent if and only if $|i-j|=1$ or $|i-j|=2$. See the figure below for the case $N = 7$.

Triangular grid with 7 vertices

How many trails are there from $1$ to $N$ in this graph? A trail is allowed to visit a vertex more than once, but it cannot travel along the same edge twice.

I wrote a program to count the trails, and I obtained the following results for $1 \le N \le 17$.

$$1, 1, 2, 4, 9, 23, 62, 174, 497, 1433, 4150, 12044, 34989, 101695, 295642, 859566, 2499277$$

This sequence is not in the OEIS, but Superseeker reports that the sequence satisfies the fourth-order linear recurrence

$$2 a(N) + 3 a(N + 1) - a(N + 2) - 3 a(N + 3) + a(N + 4) = 0.$$

Question: Can anyone prove that this equation holds for all $N$?

  • 6
    +1: This is an interesting and very well presented question!2011-05-07
  • 0
    You can partition $a(N)$ into the number $a_1(N)$ of trails that use the edge $(N-1,N)$, the number $a_2(N)$ of trails that visit the vertex $N-1$ but don't use the edge $(N-1,N)$, and the number $a_3(N)$ of trails that don't visit the vertex $N-1$. Then $a_1(N)=a(N-1)$ and $a_3(N)=a(N-2)$, and it remains to be shown that $a_2(N)=2a(N-1)-3a(N-3)-2a(N-4)$.2011-05-07

2 Answers 2

13

Regard the same graph, but add an edge from $n-1$ to $n$ with weight $x$ (that is, a path passing through this edge contributes $x$ instead of 1).

The enumeration is clearly a linear polynomial in $x$, call it $a(n,x)=c_nx+d_n$ (and we are interested in $a(n,0)=d_n$).

By regarding the three possible edges for the last step, we find $a(1,x)=1$, $a(2,x)=1+x$ and

$$a(n,x)=a(n-2,1+2x)+a(n-1,x)+x\,a(n-1,1)$$

(If the last step passes through the ordinary edge from $n-1$ to $n$, you want a trail from 1 to $n-1$, but there is the ordinary edge from $n-2$ to $n-1$ and a parallel connection via $n$ that passes through the $x$ edge and is thus equivalent to a single edge of weight $x$, so we get $a(n-1,x)$.

If the last step passes through the $x$-weighted edge this gives a factor $x$, and you want a trail from $1$ to $n-1$ and now the parallel connection has weight 1 which gives $x\,a(n-1,1)$.

If the last step passes through the edge $n-2$ to $n$, then we search a trail to $n-2$ and now the parallel connection has the ordinary possibility $n-3$ to $n-2$ and two $x$-weighted possibilities $n-3$ to $n-1$ to $n$ to $n-1$ to $n-2$, in total this gives weight $2x+1$ and thus $a(n-2,2x+1)$.)

Now, plug in the linear polynomial and compare coefficients to get two linear recurrences for $c_n$ and $d_n$.

\begin{align} c_n&=2c_{n-2}+2c_{n-1}+d_{n-1}\\ d_n&=c_{n-2}+d_{n-2}+d_{n-1} \end{align}

Express $c_n$ with the second one, eliminate it from the first and you find the recurrence for $d_n$.

(Note that $c_n$ and $a(n,x)$ are solutions of the same recurrence.)

  • 0
    If I do everything correctly, I get $d_n= 3 d_{n-1} + d_{n-2} - 3 d_{n-3} -2 d_{n-4}$ so that looks good. But I have to say, I don't understand what $c_n$ counts (and thereby I also don't understand the equation for $a(n,x)$ you write down).2011-05-07
  • 0
    The first sentence describes what $a(n,x)$ counts, paths in a slightly modified weighted triangular grid. A priori, $c_n$ counts nothing, it is just the coefficient of $x$ in $a(n,x)$.2011-05-07
  • 0
    Same as Fabian: the calculation comes out right, but I don't understand where you get the equation for $a(n,x)$. I've been trying to add up paths for different cases of the final edges, but I never get anything remotely similar.2011-05-07
  • 0
    @joriki, @user9325: To make my question a bit more concrete: The first sentence indicates that $a(n,x)$ should be the same graph (with $n$ vertices) but the edge from $n-1$ to $n$ with weight $1+x$. So I agree with the results $a(1,x)$ and $a(2,x)$. For $a(3,x)$ I would expect $1+(1+x) = 2+ x$, but you have $2+3x$.2011-05-07
  • 0
    @Fabian: This is because you can go back and forth between $2$ and $3$, using the two edges with weights $1$ and $x$, and you can do this in two different orders; that adds $2x$ to the result you expected.2011-05-07
  • 0
    @user9325: Why do you say a priori $c_n$ counts nothing? Doesn't it count the number of trails passing through the additional edge?2011-05-07
  • 0
    @Fabian For this problem, two edges with weights $1$ and $x$ are *not* the same as an edge with weight $1+x$ because each edge can be used at most once.2011-05-07
  • 0
    @joriki: Sure, it does count these trails, but my point is that I remarked that $a(n,x)$ is a linear polynomial and I defined $c_n$ as the linear coefficient whereas Fabian thought that this was an equation and asked for the missing counting definition of $c_n$.2011-05-07
  • 1
    @user9325: Very nice indeed! Thanks for the more detailed explanation. The part I was missing was that the weight of the additional edge counts the possibilities of getting to the penultimate vertex using new vertices and edges that weren't in the lower-order graph. That's cool!2011-05-07
  • 0
    @joriki I know, this would be much easier to explain and follow on a blackboard.2011-05-07
  • 0
    This reminds me of renormalization group theory, where one has to introduce a more general coupling than is present in the original model in order be able to map the scaled model onto the unscaled model.2011-05-07
  • 0
    That was a really elegant solution!2011-05-07
  • 0
    I am speechless. This is much nicer than I had dared to hope. Thank you!2011-05-07
9

This is not a new answer, just an attempt to slightly demystify user9325's very elegant answer to make it easier to understand and apply to other problems. Of course this is based on what I myself find easier to understand; others may prefer user9325's original formulation.

The crucial insight, in my view, is not the use of a variable weight and a polynomial (which serve as convenient bookkeeping devices), but that the problem becomes more tractable if we generalize it. This becomes apparent when we try a similar approach without this generalization: We might try to decompose $a(n)$ into two contributions corresponding to the two edges from $n-2$ and $n-1$ by which we can get to $n$, and in each case account for the new possibilities arising from the new vertices and edges. The contribution from $n-1$ is straightforward, but the contribution from $n-2$ causes a problem: We can now travel between $n-3$ and $n-2$ either directly or via $n-1$, and we can't just add a factor of $2$ to take this into account because there are trails using both of these possibilities. This is where the idea of an edge parallel to the final edge arises: Even though we're only interested in the final result without a parallel edge, the recurrence leads to parallel edges, so we need to include that possibility. We can do this without edge weights or polynomials by just counting the number $b(n)$ of trails that use the parallel edge separately from the number $a(n)$ of trails that don't. (I'm not saying we should; the polynomial, like a generating function, is an elegant and useful way to keep track of things; I'm just trying to emphasize that the polynomial isn't an essential part of the central idea of generalizing the original problem.)

Counting the number $a(n)$ of trails that don't use the parallel edge, we have a contribution $a(n-1)$ from trails ending with the normal edge from $n-1$, and a contribution $a(n-2)+b(n-2)$ from trails ending with the edge from $n-2$, which may ($b$) or may not ($a$) go via $n-1$:

$$a(n)=a(n-1)+a(n-2)+b(n-2)\;.$$

Counting the number $b(n)$ of trails that do use the parallel edge, we have a contribution $a(n-1)+b(n-1)$ from trails ending with the parallel edge, which may ($b$) or may not ($a$) go via $n$, a contribution $b(n-1)$ from trails ending with the normal edge from $n-1$, which have to go via $n$ (hence $b$), and a contribution $2b(n-2)$ from trails ending with the edge from $n-2$, which have to go via $n-1$ (hence $b$) and can use the normal edge from $n-1$ and the parallel edge in either order (hence the factor $2$):

$$b(n)=a(n-1)+b(n-1)+b(n-1)+2b(n-2)\;.$$

This is precisely user9325's result, with $a(n)=d_n$ and $b(n)=c_n$. There was a tad more work in counting the possibilities, but then we didn't have to compare coefficients.