Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
6  
+1: This is an interesting and very well presented question! –  Douglas S. Stones May 7 '11 at 4:19
    
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)$. –  joriki May 7 '11 at 8:19

2 Answers 2

up vote 13 down vote accepted

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.)

share|improve this answer
    
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). –  Fabian May 7 '11 at 12:30
    
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)$. –  Phira May 7 '11 at 12:33
    
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. –  joriki May 7 '11 at 12:35
    
@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$. –  Fabian May 7 '11 at 12:43
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! –  joriki May 7 '11 at 13:05

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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