Combinatorial Interpretation of Graph Theoretical Relation Involving Chebyshev Polynomials

Given a graph $G$ and its adjacency matrix $A$. The $(i,j)$-th element of $A^r$ gives the number of ways to get from vertex $i$ to $j$ in $r$ steps (including backtracking).

Now, the number of reduced paths on cubic graphs of length $n$ (without backtracking) may be written as $p_n(x) =2^{n/2}U_n(\sqrt{2}x)$, where $U_n(x)$ is a Chebyshev Polynomial of the Second Kind.

The linked MathWorld page also says that

The polynomials can also be defined in terms of the sums $$U_n(x)= \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \binom{n-r}{r}(2x)^{n-2r}\tag{16}$$

My question is:

What is the combinatorial interpretation of this relation?

$$p_n(A/\sqrt{2})=2^{n/2}\sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \binom{n-r}{r}(2A)^{n-2r}$$

Why do alternating signs, binomial coefficients and powers of $2$ come into play while you're summing powers of $A$, i.e. number of ways with $r$ steps including backtracking, to finally get something without backtracking?

• Inspired by Chris' answer. – draks ... Nov 27 '13 at 21:36
• Are you sure that $p_n(A/\sqrt{2})$ actually is a Chebyshev polynomial? According to the answer of Chris Godsil that you link to, $p_2(A)$ does not satisfy the same recurrence as $p_r(A)$ with $r\ge3$ does. – Will Orrick May 9 '15 at 14:18
• I think the correct relation is $$p_n(x)=\begin{cases}1 & n=0,\\ x & n=1,\\ 2^{n/2}U_n(x/2^{3/2})-2^{(n-2)/2}U_{n-2}(x/2^{3/2}) & n\ge2.\end{cases}$$ The first few terms in the sequence $2^{n/2}U_n(x/2^{3/2})$ are $1$, $x$, $x^2-2$, $x^3-4x$, $x^4-6x^2+4$, $x^5-8x^3+12x$. The first few terms in the sequence $p_n(x)$ are $1$, $x$, $x^2-3$, $x^3-5x$, $x^4-7x^2+6$, $x^5-9x^3+16x$. Both sequences obey the recurrence $f_n(x)=xf_{n-1}(x)-2f_{n-2}(x)$ for $n\ge3$. The difference is that $2^{n/2}U_n(x/2^{3/2})$ also obeys the recurrence when $n=2$, whereas $p_n(x)$ does not. – Will Orrick May 9 '15 at 21:15
• The MathWorld expression you quote implies that $$2^{n/2}U_n(x/2^{3/2})=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r},$$ and therefore that $$p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}-\sum_{r=0}^{\lfloor (n-2)/2\rfloor}(-2)^r\binom{n-2-r}{r}x^{n-2-2r}.$$ It seems likely that this can be understood in terms of the Principle of Inclusion-Exclusion, but it looks a bit messy. – Will Orrick May 9 '15 at 22:04
• @WillOrrick I remember being confused about this chebychev connection till I convinced myself that they are second kin, but it's been a while since I checked it. Maybe one should ask Chris again at the other post for clarification. Would you like to, since you're not convinced...When it's correct I don't care about a mess... – draks ... May 10 '15 at 11:41

First a correction regarding the connection with Chebyshev polynomials. Quoting from Chris Godsil's answer to your earlier question:

Observe that $$p_0(A)=I,\quad p_1(A) =A,\quad p_2(A) = A^2-\Delta,$$ where $\Delta$ is the diagonal matrix of valencies of $X$. If $n\ge3$ we have the recurrence $$Ap_n(A) = p_{n+1}(A) +(\Delta-I) p_{n-1}(A).$$

(I have changed $r$ to $n$ in the quoted text.) For cubic graphs, $\Delta=3I$, which results in the recurrence $$p_{n+1}(t)=tp_n(t)−2p_{n−1}(t).$$ This is related to the recurrence for Chebyshev polynomials by a change of variable, $$p_{n+1}(2^{3/2}t)=2^{3/2}tp_n(2^{3/2}t)−2p_{n−1}(2^{3/2}t),$$ followed by a rescaling, $$2^{−(n+1)/2}p_{n+1}(2^{3/2}t)=2t\cdot2^{−n/2}p_n(2^{3/2}t)−2^{−(n−1)/2}p_{n−1‌}(2^{3/2}t).$$ Hence $q_n(t):=2^{−n/2}p_n(2^{3/2}t)$ satisfies the Chebyshev recurrence, $q_{n+1}(t)=2tq_n(t)-q_{n-1}(t)$. This can be used to obtain $q_n(t)$ for $n\ge3$. For $n<3$, $$q_0(t)=1,\quad q_1(t)=2t,\quad q_2(t)=4t^2-3/2.$$

The Chebyshev polynomials of the second kind are generated from the same recurrence with the initial conditions $$U_0(t)=1,\quad U_1(t)=2t,$$ which result in $$U_2(t)=4t^2-1$$ rather than $4t^2-3/2$. The appearance of the $3/2$ term $q_2(t)$ can be traced to the occurrence of $\Delta$ rather than $\Delta-I$ in the expression for $p_2(A)$. The recurrence implies that $U_{-1}(t)=0$. As a consequence, $$q_n(t)=U_n(t)-\frac{1}{2}U_{n-2}(t)$$ holds for $n=1$ and $n=2$. By linearity of the recurrence, this extends to all $n\ge1$. It does not hold for $n=0$, however, since $U_{-2}(t)=-1$.

From $p_n(t)=2^{n/2}q_n(2^{-3/2}t)$ it follows that $$p_n(t)=2^{n/2}U_n(2^{-3/2}t)-2^{(n-2)/2}U_{n-2}(2^{-3/2}t)$$ for $n\ge1$. The MathWorld expression you quote then implies that $$2^{n/2}U_n(2^{-3/2}t)=\sum_{r=0}^{\lfloor n/2\rfloor}(−2)^r\binom{n−r}{r}t^{n−2r},$$ and therefore that $$p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}-\sum_{r=0}^{\lfloor (n-2)/2\rfloor}(-2)^r\binom{n-2-r}{r}x^{n-2-2r}.$$ Shifting the summation index in the second sum in the expression above and bringing the minus sign inside gives $$p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}+\sum_{r=1}^{\lfloor n/2\rfloor}(-1)(-2)^{r-1}\binom{n-1-r}{r-1}x^{n-2r},$$ which is a useful form for the purpose of interpretation.

Original answer: This formula can be understood in terms of the process of iteratively carrying out the recurrence in Chris Godsil's answer, which gives rise to sums of products of $A$ and $\Delta$. Define $$\Delta':=\begin{cases}\Delta & \text{if first factor in the product}\\ \Delta-I & \text{otherwise.}\end{cases}$$ Note that for cubic graphs, $$\Delta':=\begin{cases}3I& \text{if first factor in the product}\\ 2I & \text{otherwise.}\end{cases}$$ Starting with $p_1(A)=A$, $p_{n+1}(A)$ is obtained from $p_n(A)$ by

1. appending a factor of $A$ to every term in the sum;
2. for any term in the resulting sum that ends with two consecutive factors of $A$, subtracting the product that results from replacing these final two factors of $A$ with a single factor of $\Delta'$. Carrying this out in the case $n=1$, Step 1 gives $AA$ and Step 2 gives $AA-\Delta'$, with the result $$p_2(A)=AA-\Delta'.$$ Then for $n=2$, Step 1 gives $AAA-\Delta'A$, and Step 2 gives $-A\Delta'$, with the result $$p_3(A)=AAA-\Delta'A-A\Delta'.$$ One more time: Step 1 gives $AAAA-\Delta'AA-A\Delta'A$ and Step 2 gives $-AA\Delta'+\Delta'\Delta'$, with the result $$p_4(A)=AAAA-\Delta'AA-A\Delta'A-AA\Delta'+\Delta'\Delta'.$$

It should be clear that the result of the recurrence is that $p_n(A)$ is a sum with the following characteristics:

1. every string of weight $n$ consisting of $A$ and $\Delta'$ occurs exactly once; here weight is computed as $$(\text{number of As})+2\cdot(\text{number of \Delta's})$$ since each $\Delta'$ replaces two $A$s;
2. the sign equals $$(-1)^\text{number of \Delta's}.$$

The sum may have anywhere between $0$ and $\lfloor n/2\rfloor$ $\Delta'$s. A string containing $r$ $\Delta'$s consists of $n-r$ symbols since each $\Delta'$ has weight $2$. Hence there are $\binom{n-r}{r}$ strings with $r$ $\Delta'$s.

These observations can be related to the expression for $p_n(x)$ given above. We start by incorrectly replacing every occurrence of $\Delta'$ in each string with $2I$. This gives the incorrect formula $$p_n(A)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}A^{n-2r}.$$ The formula is wrong because the first $\Delta'$ in a string should have been replaced with $3I$ instead of $2I$ if that $\Delta'$ were the first letter of the string. We therefore correct our expression by adding $(-1)\cdot(-2)^{r-1}A^{n-2r}$ for each string with $r$ $\Delta'$s in which $\Delta'$ is the first letter. There are $\binom{n-1-r}{r}$ such strings. As a result, the correct expression is $$p_n(A)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}A^{n-2r}+\sum_{r=1}^{\lfloor n/2\rfloor}(-1)\cdot(-2)^{r-1}\binom{n-1-r}{r}A^{n-2r}.$$

New answer (19 May 2015): The powers of $-1$ suggest that the sum arises from the principle of inclusion-exclusion. In general terms, given a finite set $S$ and a set $T$, the size of the complement of $T$ is given by $$\lvert T'\rvert=\lvert S\rvert-\sum_{i=1}^N S_i+\sum_{1\le i<j\le N}S_i\cap S_j-\sum_{1\le i<j<k\le N}S_i\cap S_j\cap S_k+\ldots,$$ where $S_1$, $S_2$, $\ldots$, $S_N$ are subsets of $S$ whose union is $T$. In your problem, the role of $S$ is played by the set of paths from $a$ to $b$ of length $n$, which we will denote $P(a,b,n,\{\})$; the role of $T$ is played by the subset of $P(a,b,n,\{\})$ consisting of those paths containing at least one reversing step, and the role of $T'$ is played by the subset of $P(a,b,n,\{\})$ consisting of those paths containing no reversing step.

To carry out an inclusion-exclusion calculation, the first step is to choose sets to play the role of $S_i$. A natural choice is to use the sets $$P(a,b,n,\{j\})=\text{set of paths from a to b of length n in which step j reverses step j-1,}$$ where $j$ ranges from $2$ to $n$. It is clear that the union of these sets is the set of paths from $a$ to $b$ of length $n$ containing one or more reversing steps. In performing the inclusion-exclusion sum one needs to compute sizes of intersections of two or more sets—intersections like $P(a,b,n,\{j\})\cap P(a,b,n,\{k\})=:P(a,b,n,\{j,k\})$, for example. In this example, the size of the intersection depends on whether $k=j+1$ or $k>j+1$, and this makes the computation a bit involved. It is carried out in this post.

Since the only requirement on the sets $S_i$ is that their union equal $T$, many choices are possible. In this problem, a better choice for the sets to play the role of $S_i$ are the sets \begin{aligned} R(a,b,n,\{j\})=\,&\text{set of paths from a to b of length n in which step j reverses step j-1 and}\\ &\text{step j-1 does not reverse step j-2,} \end{aligned} where again $j$ ranges from $2$ to $n$. (When $j=2$ we consider the condition that step $1$ not reverse step $0$ to be vacuously true as there is no step $0$.) Again, the union of these sets is the set of all paths from $a$ to $b$ of length $n$ containing one or more reversing steps. This follows from the fact that in any path containing a reversing step, there is a reversing step of least index. Hence if that least index is $j$, then the path is contained in $R(a,b,n,\{j\})$.

Since $R(a,b,n,\{j\})\cap R(a,b,n,\{j+1\})=\emptyset$, we need only consider the case $R(a,b,n,\{j\})\cap R(a,b,n,\{k\})=:R(a,b,n,\{j,k\})$ with $k>j+1$ and, more generally, intersections like $R(a,b,n,\{j_1\})\cap\ldots\cap R(a,b,n,\{j_r\})=:R(a,b,n,\{j_1,\ldots,j_r\})$ in which $\lvert j_k-j_i\rvert\ge2$ for all distinct $i$, $k$ in $\{1,2,\ldots,r\}$. We will assume this condition from now on.

The set $R(a,b,n,\{\})$ of all paths from $a$ to $b$ of length $n$ has size given by the $(a,b)$ element of $A^n$. To handle the case where a reversing step is required at a given position, we need to consider products in which a pair of $A$s has been replaced by $\Delta$ or $\Delta-I$. We use the definition of $\Delta'$ given in the earlier answer. Since a reversal in step $j$ implies that the same vertex is visited after the $(j−2)^\text{nd}$ and $j^\text{th}$ steps, and since if $j>2$ the vertex visited after the $(j-1)^\text{st}$ step cannot be the same as that visited immediately prior to the $(j-2)^\text{nd}$ step, $\lvert R(a,b,n,\{j\})\rvert$ is the $(a,b)$ element of $$A^{j−2}\Delta'A^{n−j}= \begin{cases}(3I)A^{n-2}=3A^{n-2} & \text{if j=2,}\\ A^{j−2}(2I)A^{n−j}=2A^{n−2} & \text{if j>2.} \end{cases}$$ In other words, the two factors of $A$ at positions $j-1$ and $j$ in $A^n$ have been replaced with $\Delta'$. By the same argument, $\lvert R(a,b,n,\{j_1,\ldots,j_r\})\rvert$ is the $(a,b)$ element of the product in which the two $A$s at each of the pairs of positions $(j_1-1, j_1)$, $\ldots$, $(j_r-1,j_r)$ in the product $A^n$ get replaced with $\Delta'$. Because of the condition $\lvert j_k-j_i\rvert\ge2$ for distinct $i$, $k$, these replacements never occur in overlapping positions and can therefore be made independently of one another. Denote by $D_r$ the set of subsets of $\{2,3,\ldots,n\}$ of size $r$ in which this "difference-$2$" condition holds.

By the principle of inclusion-exclusion, the number of paths from $a$ to $b$ of length $n$ with no reversing steps is given by $$\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{A\in D_r}\lvert R(a,b,n,A)\rvert.$$ This is equal to the $(a,b)$ element of $$\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{A\in D_r}[2+\mathbf{1}_A(2)]2^{r-1}A^{n-2r}=\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\left[\sum_{A\in D_r}2^rA^{n-2r}+\sum_{A\in D_r,2\in A}2^{r-1}A^{n-2r}\right],$$ where $\mathbf{1}_A(x)$ is the indicator function whose value is $1$ if $x\in A$ and $0$ if $x\notin A$. There is a one-to-one correspondence between elements of $D_r$ and strings containing $n-2r$ $A$s and $r$ $\Delta'$s. There is a one-to-one correspondence between elements of $D_r$ containing $s$ and strings containing $n-2r$ $A$s and $r$ $\Delta'$s such that the initial element of the string is a $\Delta'$. This implies that there are $\binom{n-r}{r}$ elements in $D_r$ and $\binom{n-1-r}{r-1}$ elements in $D_r$ that contain $2$. The sum given in my earlier answer results.