2
$\begingroup$

Define Pascal's triangle as follows: it is an array $(T_{m,n})_{m, n \in \mathbf{Z}}$ of integers, satisfying

  • if $m<0$, then $T_{m,n}=0$.

  • $T_{0,0}=1$ and if $n \neq 0$, then $T_{0,n}=0$.

  • if $m>0$, then $T_{m,j} = T_{m-1,j-1} + T_{m-1,j+1}$.

The last item makes the indexing perhaps a little unusual, but if you ignore entries $T_{i,j}$ where $i$ and $j$ have different parity (because those entries are always zero), you get Pascal's triangle.

Now consider a variation on this by truncating it to the left of column 0 and to the right of some column $N$: fix $N$ and replace the last condition with:

  • if $m>0$, then for $0 \leq j \leq N$, $T_{m,j} = T_{m-1,j-1} + T_{m-1,j+1}$. If $j<0$ or $j>N$, then $T_{m,j}=0$.

For example, if $N=3$, we get this:

1
  1
1   1
  2   1
2   3
  5   3
5   8
  13  8

The entries are Fibonacci numbers, and the sums of the rows give the Fibonacci sequence.

If $N=5$, we get this:

1
  1
1   1
  2   1
2   3   1
  5   4   1
5   9   5
  14  14  5
14  28  19

The row sums are 1, 1, 2, 3, 6, 10, 19, 33, 61, 108, 197, ... (presumably this sequence).

I'm interested in what happens as $N$ varies, and in particular when $N$ is two less than a prime. For example, what are the sums of the rows? What is the limit of the $n$th root of the $n$th row? Has anyone seen this sort of thing in the literature?

$\endgroup$

2 Answers 2

2
$\begingroup$

These appear as the Bratteli diagrams of quotients of the Temperley-Lieb algebras at roots of unity.

$\endgroup$
1
$\begingroup$

You are just counting walks of various lengths starting from the leftmost vertex of a path graph $P_{N+1}$ with $N+1$ vertices. It is possible to explicitly write down the eigenvectors and eigenvalues of the adjacency matrix of a path graph: namely, the eigenvectors are $$v_i = \left( \sin \frac{\pi i}{N+2}, \sin \frac{2 \pi i}{N+2}, ... \sin \frac{(N+1) \pi i}{N+2} \right)$$

with eigenvalues $2 \cos \frac{i \pi}{N+2}$. An exact formula for the row sums can be extracted from the above information; see this blog post for a more thorough discussion, and I can write down the formula in an edit if you want. In any case, the $n^{th}$ row sum is $\Theta((2 \cos \frac{\pi}{N+2})^n)$.

$\endgroup$
3
  • $\begingroup$ You mean that the row sums are counting walks of various lengths, not the entries in the diagram, right? $\endgroup$ Commented Jan 26, 2012 at 17:18
  • $\begingroup$ @John: the entries in the diagram count walks from the leftmost vertex to some specific other vertex, while the row sums count walks from the leftmost vertex without regard to the ending vertex. $\endgroup$ Commented Jan 26, 2012 at 17:57
  • $\begingroup$ Ah, of course. I see. $\endgroup$ Commented Jan 26, 2012 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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