\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}

\newtheorem{thm}{Theorem}[section]
%\newtheorem{pro}[thm]{Proposition}
%\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\renewcommand{\thethm}{\thesection.\arabic{thm}}
\makeatletter\@addtoreset{equation}{section}\makeatother
%\def\qed{$\quad$\rule{0mm}{3mm}\hfill \rule{2mm}{3mm}}
\newcommand{\E}{{\mathbf E}}
\newcommand{\D}{{\mathbf D}}
\newcommand{\C}[1]{1-C^{#1}}
\newcommand{\CC}[1]{(1-C^{#1})}
\newcommand{\B}{{\mathbf B}}
\newcommand{\G}[2]{G_{#1}^{(#2)}}
\renewcommand{\H}[2]{H_{#1}^{(#2)}}
\newcommand\sumz[1]{\sum_{#1=0}^\infty}
\newcommand\superscript{$^1$}
\def\comment#1{\textbf{Comment: }\emph{#1}}


\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf On Integer Sequences Associated With the\\
\vskip .1in 
Cyclic and Complete Graphs}
\vskip 1cm
\large Paul Barry\\
School of Science\\
Waterford Institute of Technology\\
Ireland \\
\href{mailto:pbarry@wit.ie}{\tt pbarry@wit.ie} \\
\end{center}

\vskip .2 in

\begin{abstract} 
We study integer sequences associated with the cyclic graph $C_r$ and
the complete graph $K_r$. Fourier techniques are used to characterize
the sequences that count walks of length $n$ on both these families of
graphs. In the case of the cyclic graph, we show that these sequences
are associated with an induced colouring of Pascal's triangle. This
extends previous results concerning the Jacobsthal numbers.
\end{abstract}

\section{Preliminaries} In \cite{Barry} we studied the Jacobsthal numbers, and
showed that they provide a decomposition (or colouring) of Pascal's
triangle. In this article, we shall relate this decomposition to the
cyclic graph $C_{3}$, and then we will generalize the result to the
general cyclic graph on $r$ vertices $C_{r}$. In addition, we will
study integer sequences related to $K_{r}$, the complete graph on
$n$ vertices.

Many of the integer sequences that we will encounter are to be found
in The On-Line Encylopedia of Integer Sequences (OEIS)
\cite{Sloane1,Sloane2}.

We begin with a brief recall of the relevant results of
\cite{Barry}. For this, we let the sequence of numbers $J(n)$, be
the solution of the recurrence
\begin{displaymath}a_{n}=a_{n-1}+2a_{n-2},\textrm{ }a_{0}=0,\textrm{
}a_{1}=1,\end{displaymath} with $$\begin{array}{c|cccccccc}
        n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline
        J(n) & 0 & 1 & 1 & 3 & 5 & 11 & 21 & \ldots \\
      \end{array}$$
\begin{equation}J(n)=\frac{2^n}{3}-\frac{(-1)^n}{3}.\end{equation}
These are the Jacobsthal numbers \cite{Jac}. In section $4$, we
shall relate these numbers to a count of walks on $C_3$. They have
many other applications, as detailed for instance in
\cite{EightyFive} and \cite{FreySellers}. They appear in the OEIS as
\seqnum{A001045}. When we change the initial conditions to
$a_{0}=1,\textrm{ }a_{1}=0$, we get a sequence which we will denote
by $J_1(n)$, \seqnum{A078008}, given by
$$\begin{array}{c|cccccccc}
        n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline
        J_1(n) & 1 & 0 & 2 & 2 & 6 & 10 & 22 & \ldots \\
      \end{array}$$
\begin{equation}\label{eqJ1}J_1(n)=
\frac{2^n}{3}+\frac{2(-1)^n}{3}.\end{equation} We see that
\begin{equation}2^n=2J(n)+J_1(n).\end{equation} What is less obvious
is that the Jacobsthal numbers are sums of binomial coefficients.
In fact, we have
\begin{eqnarray*}J_1(n)=\sum_{(n+k)\bmod3=0}\binom{n}{k}\\
J(n)=\sum_{(n+k)\bmod3=1}\binom{n}{k}\\
J(n)=\sum_{(n+k)\bmod3=2}\binom{n}{k}.\end{eqnarray*} In
\cite{Barry}, an inductive argument was used to prove this. We
give below a more direct proof, using an identity that will be
used later for a more general result. This is
\begin{equation}\sum_{k\equiv l (\bmod
m)}\binom{n}{k}=\frac{1}{m}\sum_{j=0}^{m-1}(1+\omega^j)^n\omega^{-lj}\end{equation}
where $\omega=e^{2{\pi}i/m}$. We then have, for $m=3$,
\begin{eqnarray*}\sum_{k\equiv -n (\bmod
3)}\binom{n}{k}&=&\frac{1}{3}\sum_{j=0}^{2}(1+\omega^j)^n\omega^{nj}\\
&=&\frac{1}{3}(2^n+(1+\omega)^n\omega^n+(1+\omega^2)^n\omega^{2n})\\
&=&\frac{1}{3}(2^n+(-\omega^2)^n\omega^n+(-\omega)^n\omega^{2n})\\
&=&\frac{1}{3}(2^n+(-1)^n\omega^{2n}\omega^n+(-1)^n\omega^n\omega^{2n})\\
&=&\frac{1}{3}(2^n+(-1)^n(\omega^{3n}+\omega^{3n}))\\
&=&\frac{1}{3}(2^n+2(-1)^n)=J_1(n).\end{eqnarray*} In like manner,
we have \begin{eqnarray*}\sum_{k\equiv (-n+1) (\bmod
3)}\binom{n}{k}&=&\frac{1}{3}\sum_{j=0}^{2}(1+\omega^j)^n\omega^{(n-1)j}\\
&=&\frac{1}{3}(2^n+(1+\omega)^n\omega^{n-1}+(1+\omega^2)^n\omega^{2(n-1)})\\
&=&\frac{1}{3}(2^n+(-\omega^2)^n\omega^{n-1}+(-\omega)^n\omega^{2(n-1)})\\
&=&\frac{1}{3}(2^n+(-1)^n\omega^{2n}\omega^{n-1}+(-1)^n\omega^n\omega^{2(n-1)})\\
&=&\frac{1}{3}(2^n+(-1)^n(\omega^{3n-1}+\omega^{3n-2}))\\
&=&\frac{1}{3}(2^n+(-1)^n(\omega^{-1}+\omega^{-2}))\\
&=&\frac{1}{3}(2^n+(-1)^n(\omega^{2}+\omega^{1}))\\
&=&\frac{1}{3}(2^n-(-1)^n)=J(n).\end{eqnarray*} The third identity
is proven in similar fashion.

Since
\begin{displaymath}2^n=\sum_{k=0}^n\binom{n}{k}\end{displaymath}
we immediately obtain the required decomposition property of
Pascal's triangle. We shall express this in terms of
lower-triangular matrices, where we identify Pascal's triangle with
the Binomial Matrix $\mathbf{B}$ whose $(n,k)$-th element is equal
to $\binom{n}{k}$:
\begin{displaymath}\mathbf{B}=\left(\begin{array}{ccccccc} 1 & 0 & 0
& 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 1 & 2 & 1
& 0 & 0 & 0 & \ldots \\ 1 & 3 & 3 & 1 & 0 & 0 & \ldots \\
1 & 4 & 6 & 4 & 1 & 0 & \ldots
\\1 & 5 & 10 & 10 & 5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} We shall call
a lower-triangular matrix a \emph{zero-binomial} matrix if its
elements are either $0$ or binomial coefficients. We can then
state the relevant result of \cite{Barry} as follows.
\begin{theorem} There exists a partition
\begin{displaymath}\mathbf{B}=\mathbf{B_{0}}+\mathbf{B_{1}}+\mathbf{B_{2}}\end{displaymath}
where the $\mathbf{B_{i}}$ are zero-binomial matrices with row sums
equal to $J_1(n)$, $J(n)$, $J(n)$ respectively for $i=0,\ldots,2$.
\end{theorem} We have
$$\mathbf{B}_i=([n+k \equiv i \bmod 3]\binom{n}{k}),$$ where we use
the Iverson notation $[P(j)]$ to denote $1$ if the logical
expression $P(j)$ is true, and $0$ if it is false \cite{Concrete}.

 We can see this decomposition in the following coloured
rendering of $\mathbf{B}$.
\begin{displaymath}\mathbf{B}=\left(\begin{array}{ccccccc} \textcolor{red}{1} & 0 & 0
& 0 & 0 & 0 & \ldots \\\textcolor{blue}{1} & \textcolor{green}{1} & 0 & 0 & 0 & 0 & \ldots \\
\textcolor{green}{1} & \textcolor{red}{2} & \textcolor{blue}{1}
& 0 & 0 & 0 & \ldots \\ \textcolor{red}{1} & \textcolor{blue}{3} & \textcolor{green}{3} & \textcolor{red}{1} & 0 & 0 & \ldots \\
\textcolor{blue}{1} & \textcolor{green}{4} & \textcolor{red}{6} &
\textcolor{blue}{4} & \textcolor{green}{1} & 0 & \ldots
\\\textcolor{green}{1} & \textcolor{red}{5} & \textcolor{blue}{10} & \textcolor{green}{10} & \textcolor{red}{5} & \textcolor{blue}{1} &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\begin{array}{ccc}
\textcolor{red}{1}&\textcolor{green}{0}&\textcolor{blue}{0}\\
\textcolor{red}{0}&\textcolor{green}{1}&\textcolor{blue}{1}\\
\textcolor{red}{2}&\textcolor{green}{1}&\textcolor{blue}{1}\\
\textcolor{red}{2}&\textcolor{green}{3}&\textcolor{blue}{3}\\
\textcolor{red}{6}&\textcolor{green}{5}&\textcolor{blue}{5}\\
\textcolor{red}{10}&\textcolor{green}{11}&\textcolor{blue}{11}\\
\textcolor{red}{.}&\textcolor{green}{.}&\textcolor{blue}{.}\\
\end{array}
\end{displaymath}
 \section{Graphs} We now wish to draw a link between the foregoing and graph theory. To this end, we recall a number of relevant definitions \cite{Grimaldi,West}.
A graph $X$ is a triple consisting of a vertex set $V=V(X)$, an
edge set $E=E(X)$, and a map that associates to each edge two
vertices (not necessarily distinct) called its endpoints. A
\emph{loop} is an edge whose endpoints are equal. To any graph, we
may associate the \emph{adjacency matrix}, which is an $n\times n$
matrix, where $|V|=n$ with rows and columns indexed by the
elements of the vertex set $V$ and the $(x,y)$-th element is the
number of edges connecting $x$ and $y$. As defined, graphs are
undirected, so this matrix is symmetric. We will restrict
ourselves to \emph{simple} graphs, with no loops or multiple
edges.

The \emph{degree} of a vertex $v$, denoted deg($v$), is the number
of edges incident with $v$. A graph is called $k$-regular if every
vertex has degree $k$. The adjacency matrix of a
$k$-\emph{regular} graph will then have row sums and column sums
equal to $k$.

If $x$, $y \in V$ then an $x$-$y$ \emph{walk} in $X$ is a
(loop-free) finite alternating sequence
\begin{displaymath}x=x_{0},e_{1},x_{1},e_{2},x_{2},e_{3},\ldots,e_{r-1},x_{r-1},e_{r},x_{r}=y\end{displaymath}
of vertices and edges from $X$, starting at the vertex $x$ and
ending at the vertex $y$ and involving the $r$ edges
$e_{i}=\{x_{i-1},x_{i}\}$, where $1\le i \le r$. The \emph{length}
of this walk is $r$. If $x = y$, the walk is \emph{closed},
otherwise it is \emph{open}. If no edge in the $x$-$y$ walk is
repeated, then the walk is called an $x$-$y$ \emph{trail}. A closed
$x$-$x$ trail is called a \emph{circuit}. If no vertex of the
$x$-$y$ walk is repeated, then the walk is called an $x$-$y$
\emph{path}. When $x$ = $y$, a closed path is called a \emph{cycle}.
The number of walks from $x$ to $y$ of length $n$ is given by the
$x,y$-th entry of $\mathbf{A}^n$, where $\mathbf{A}$ is the
adjacency matrix of the graph $X$.

The \emph{cyclic graph} $\mathrm{C}_r$ on $r$ vertices is the
graph with $r$ vertices and $r$ edges such that if we number the
vertices $0, 1, \ldots, r-1$, then vertex $i$ is connected to the
two adjacent vertices $i+1$ and $i-1 (\bmod r)$. The
\emph{complete graph} $\mathrm{K}_r$ on $r$ vertices is the
loop-free graph where for all $x,y\in V, x\ne y$, there is an edge
$\{x,y\}$.

We note that $C_{3}$=$K_{3}$.

A final graph concept that will be useful is that of the
\emph{chromatic polynomial} of a graph. If $X=(V,E)$ is an
undirected graph, a \emph{proper colouring} of X occurs when we
colour the vertices of $X$ so that if $\{x,y\}$ is an edge in $X$,
then $x$ and $y$ are coloured with different colours. The minimum
number of colours needed to properly colour $X$ is called the
\emph{chromatic number} of $X$ and is written $\chi(X)$. For $k \in
\mathbf{Z^{+}}$, we define the polynomial $P(X, k)$ as the number of
different ways that we can properly colour the vertices of X with
$k$ colours.

For example,
\begin{equation}
P(K_{r},k)=k(k-1)\ldots(k-r+1)\end{equation} and
\begin{equation}P(C_{r},k)=(k-1)^r+(-1)^r(k-1).\end{equation}
\section{Notation}
In this note, we shall employ the following notation. $r$ will
denote the number of vertices in a graph. Note that the adjacenty
matrix $A$ of a graph with $r$ vertices will then be an $r \times r$
matrix. We shall reserve the number variable $n$ to index the
elements of a sequence, as in $a_n$, the $n$-th element of the
sequence $\mathbf{a}=\{a_n\}$, or as the $n$-th power of a number or
a matrix (normally this will be related to the $n$-th term of a
sequence). The notation $0^n$ signifies the integer sequence with
generating function $1$, which has elements $1,0,0,0,\ldots$.

Note that the Binomial matrix $\mathbf{B}$ and the Fourier matrix
$\mathbf{F}_r$ (see below) are indexed from $(0,0)$, that is, the
leftmost element of the first row is the $0,0$-th element. This
allows us to give the simplest form of their general $n,k$-th
element ($\binom{n}{k}$ and $e^{-\frac{2 \pi i n k}{r}}$
respectively).

The adjacency matrix of a graph, normally denoted by $\mathbf{A}$,
will be indexed as usual from $(1,1)$. Similarly the eigenvalues of
the adjacency matrix will be labelled
$\lambda_1,\lambda_2,\ldots,\lambda_r$.


\section{Circulant matrices}
We now provide a quick overview of the theory of circulant
matrices \cite{Davis}, as these will be encountered shortly. An $r
\times r$ circulant matrix $\mathbf{C}$ is a matrix whose rows are
obtained by shifting the previous row one place to the right, with
wraparound, in the following precise sense. If the elements of the
first row are $(c_{1}, \ldots, c_{r})$ then
\begin{displaymath}c_{jk}=c_{k-j+1}\end{displaymath} where subscripts are taken modulo $n$. Circulant matrices are
diagonalized by the discrete Fourier transform, whose matrix
$\mathbf{F}_r$ is defined as follows : let
$\omega(r)=e^{-2{\pi}i/r}$ where $i=\sqrt{-1}$. Then
$\mathbf{F}_r$ has $i,j$-th element $\omega^{i\cdot j}$, $0\le i,j
\le r-1$.

We can write the above matrix as $\mathbf{C}=\textrm{circ}(c_{1},
\ldots, c_{r})$. The permutation matrix
$\mathbf{\pi}=\textrm{circ}(0,1,0, \ldots, 0)$ plays a special
role. If we let $p$ be the polynomial
$p(x)=c_{1}+c_{2}x+\ldots+c_{r}x^{r-1}$, then
$\mathbf{C}=p(\mathbf{\pi})$.

We have, for $\mathbf{C}$ a circulant matrix,
\begin{eqnarray*}\mathbf{C}&=&\mathbf{F}^{-1}\mathbf{\Lambda F},\\
\mathbf{\Lambda}&=&\textrm{diag}(p(1),p(\omega),\ldots,p(\omega^{r-1})).\end{eqnarray*}
The $i$-th eigenvalue of $\mathbf{C}$ is $\lambda_i=p(\omega^i)$,
$1\le i \le r$.

\section{The graph $\mathrm{C}_{3}$ and Jacobsthal numbers}

We let $\mathbf{A}$ be the adjacency matrix of the cyclic graph
$C_{3}$. We have
\begin{displaymath}\mathbf{A}=\left(\begin{array}{ccc} 0 & 1 & 1
 \\1 & 0 & 1 \\ 1 & 1 & 0 \end{array}\right)\end{displaymath} We note
 that this matrix is circulant. We shall be interested both in the powers $\mathbf{A}^n$ of
$\mathbf{A}$ and its eigenvalues. There is the following
connection between these entities:
\begin{displaymath}\textrm{trace}(\mathbf{A}^n)=\sum_{j=1}^r\lambda_{j}^n\end{displaymath}
where $\lambda_{1},\ldots,\lambda_{r}$ are the eigenvalues of
$\mathbf{A}$. Here, $r=3$.  In order to obtain the eigenvalues of
$\mathbf{A}$, we use $\mathbf{F}_{3}$ to diagonalize it. We
obtain\begin{displaymath}\mathbf{F}_3^{-1}\mathbf{A}\mathbf{F}_3=\left(\begin{array}{ccc}
2 & 0 & 0
 \\0 & -1 & 0 \\ 0 & 0 & -1 \end{array}\right)\end{displaymath}
 We immediately have
 \begin{displaymath}\textrm{trace}({\mathbf{A}^n})=2^n+2(-1)^n\end{displaymath}
 Comparing with (\ref{eqJ1}), we have
 \begin{proposition}$J_1(n)=\frac{1}{3}\textrm{trace}(\mathbf{A}^n)$
 \end{proposition}
 Our next observation relates $J_1(n)$ to 3-colourings of $C_r$. For this, we recall that $P(C_r,k)=(k-1)^r+(-1)^r(k-1)$. Letting
 $k=3$, we get $P(C_r,3)=2^r+2(-1)^r$.
 \begin{proposition} $J_1(r)=\frac{1}{3}P(C_r,3).$
 \end{proposition}
 Since $\mathbf{A}$ is circulant, it and its powers $\mathbf{A}^n$
 are determined by the elements of their first rows. We shall look at
 the integer sequences determined by the first row elements of $\mathbf{A}^n$ - that is, we
 shall look at the sequences $a_{1j}^{(n)}$, for $j=1,2,3$.
\begin{theorem}\begin{eqnarray*}a_{11}^{(n)}=J_1(n),\textrm{  }
a_{12}^{(n)}=J(n),\textrm{  } a_{13}^{(n)}=J(n)
\end{eqnarray*}\end{theorem}
\begin{proof} We use the fact that
\begin{equation}\mathbf{A}^n=\mathbf{F}^{-1}\left(\begin{array}{ccc} 2^n & 0 &
0
 \\0 & (-1)^n & 0 \\ 0 & 0 & (-1)^n \end{array}\right)\mathbf{F}\end{equation}
 Then
 \begin{eqnarray*}\mathbf{A}^n&=&\frac{1}{3}\left(\begin{array}{ccc}1&1&1\\1&\omega&\omega^2\\1&\omega^2&\omega^4\end{array}\right)
 \left(\begin{array}{ccc}2^n&0&0\\0&(-1)^n&0\\0&0&(-1)^n\end{array}\right)
\left(\begin{array}{ccc}1&1&1\\1&\omega&\omega^2\\1&\omega^2&\omega^4\end{array}\right)\\
&=&\frac{1}{3}\left(\begin{array}{ccc}2^n&(-1)^n&(-1)^n\\
\vdots&\vdots&\vdots\end{array}\right)
\left(\begin{array}{ccc}1&1&1\\1&\omega&\omega^2\\1&\omega^2&\omega^4\end{array}\right)
\\&=&\frac{1}{3}\left(\begin{array}{ccc}2^n+2(-1)^n&(2^n+(-1)^n\omega_{3}+(-1)^n\omega_{3}^2)&
(2^n+(-1)^n\omega_{3}^2+(-1)^n\omega_{3}^4)\\\vdots&\vdots&\vdots\end{array}\right)\end{eqnarray*}
 Thus we obtain \begin{eqnarray*}
 a_{11}^{(n)}&=&(2^n+2(-1)^n)/3\\
 a_{12}^{(n)}&=&(2^n+(-1)^n\omega_{3}+(-1)^n\omega_{3}^2)/3\\
  a_{13}^{(n)}&=&(2^n+(-1)^n\omega_{3}^2+(-1)^n\omega_{3}^4)/3. \end{eqnarray*}
The result now follows from the fact that
\begin{displaymath}1+\omega_{3}+\omega_{3}^2=1+\omega_{3}^2+\omega_{3}^4=0.\end{displaymath}\end{proof}
\begin{corollary} The Jacobsthal numbers count the number of walks on
$C_{3}$. In particular, $J_1(n)$ counts the number of closed walks
of length $n$ on the edges of a triangle based at a vertex. $J(n)$
counts the number of walks of length $n$ starting and finishing at
different vertices.
\end{corollary}
An immediate calculation gives
\begin{corollary}\begin{displaymath}2^n=a_{11}^{(n)}+a_{13}^{(n)}+a_{13}^{(n)}.\end{displaymath}\end{corollary}
The identity
\begin{displaymath}2^n=2J(n)+J_1(n)\end{displaymath}
now becomes a consequence of the identity \begin{displaymath}
2^n=a_{11}^{(n)}+a_{13}^{(n)}+a_{13}^{(n)}.\end{displaymath} This is
a consequence of the fact that $C_3$ is $2$-regular. We have arrived
at a link between the Jacobsthal partition (or colouring) of
Pascal's triangle and the cyclic graph $C_{3}$. We recall that this
comes about since $2^n=J_1(n)+2J(n)$, and the fact that $J_1(n)$ and
$J(n)$ are expressible as sums of binomial coefficients.

We note that although $C_{3}=K_{3}$, it is the cyclic nature of
the graph and the fact that it is 2-regular that links it to this
partition. We shall elaborate on this later in the article.

 In
terms of ordinary generating functions, we have the identity
\begin{displaymath}\frac{1}{1-2x}=\frac{1-x}{(1+x)(1-2x)}+\frac{x}{(1+x)(1-2x)}+\frac{x}{(1+x)(1-2x)}\end{displaymath}
and in terms of exponential generating functions, we have
\begin{displaymath}\exp(2x)=\frac{2}{3}\exp(-x)(1+\exp(\frac{3x}{2})\sinh(\frac{3x}{2}))+2\frac{2}{3}\exp(\frac{x}{2})\sinh(\frac{3x}{2})\end{displaymath}or
more
simply,\begin{displaymath}\exp(2x)=\frac{1}{3}(\exp(2x)+2\exp(-x))+2\frac{1}{3}(\exp(2x)-\exp(-x)).\end{displaymath}
An examination of the calculations above and the fact that
$\mathbf{F}$ is symmetric allows us to state
\begin{corollary}\begin{displaymath}\left(\begin{array}{c}a_{11}^{(n)}\\a_{12}^{(n)}\\a_{13}^{(n)}\end{array}\right)
=\frac{1}{3}\left(\begin{array}{ccc}1&1&1\\1&\omega&\omega^2\\1&\omega^2&\omega^4\end{array}\right)
\left(\begin{array}{c}2^n\\(-1)^n\\(-1)^n\end{array}\right)\end{displaymath}\end{corollary}
In fact, this result can be easily generalized to give the
following
\begin{equation}\left(\begin{array}{c}a_{11}^{(n)}\\a_{12}^{(n)}\\\vdots\\a_{1r}^{(n)}\end{array}\right)
=\frac{1}{r}\mathbf{F}_{r}\left(\begin{array}{c}\lambda_{1}^{n}\\\lambda_{2}^{n}\\\vdots\\\lambda_{r}^{n}\end{array}\right)\end{equation}
so that
\begin{displaymath}\mathbf{A}^n=\mathrm{circ}(a_{11}^{(n)},a_{12}^{(n)},\ldots,a_{1r}^{(n)})=\mathrm{circ}(\frac{1}{r}\mathbf{F}_r(\lambda_{1}^n,\ldots,\lambda_{r}^n)').\end{displaymath}
It is instructive to work out the generating function of these
sequences. For instance, we have
$$a^{(n)}_{12}=1.2^n+\omega.(-1)^n+\omega^2.(-1)^n.$$ This implies
that $a^{(n)}_{12}$ has generating function
\begin{eqnarray*}g_{12}(x)&=&\frac{1}{1-2x}+\frac{\omega}{1+x}+\frac{\omega^2}{1+x}\\
&=&\frac{(1+x)^2+\omega(1+x)(1-2x)+\omega^2(1-2x)(1+x)}{(1-2x)(1+x)(1+x)}\\
&=&\frac{3x(1+x)}{3(1-2x)(1+x)^2}\\
&=&\frac{x}{1-x-2x^2}.\end{eqnarray*} This is as expected, but it
also highlights the importance of $$(1-2x)(1+x)(1+x)=(1-\lambda_1
x)(1-\lambda_2 x)(1-\lambda_3 x)=1-3x^2-2x^3.$$ Hence each of these
sequences not only obeys the Jacobsthal recurrence
$$a_n=a_{n-1}+2a_{n-2}$$ but also
$$a_n=3a_{n-2}+2a_{n-3}.$$
Of course,
$$1-3x^2-2x^3=(1-p(\omega_3^0)x)(1-p(\omega_3^1)x)(1-p(\omega_3^2)x)$$
where $p(x)=x+x^2$.
\section{The case of $C_{4}$}
For the cyclic graph on four vertices $C_{4}$ we have the following
adjacency matrix
\begin{equation}\mathbf{A}=\left(\begin{array}{cccc} 0 & 1 & 0 & 1
 \\1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\1 & 0 & 1 & 0\end{array}\right)\end{equation}
We can carry out a similar analysis as for the case $n=3$. Using
$\mathbf{F}$ to diagonalize $\mathbf{A}$, we obtain
\begin{displaymath}\mathbf{F}^{-1}\mathbf{A}\mathbf{F}=\left(\begin{array}{cccc} 2 & 0 & 0 &
0
 \\0 & 0 & 0 & 0 \\ 0 & 0 & -2 & 0 \\0 & 0 & 0 &
 0\end{array}\right)\end{displaymath}
 From this, we can immediately deduce the following result.
 \begin{theorem}\begin{displaymath}\frac{1}{4}\mathrm{trace}\mathbf{A}^n=\frac{1}{4}(2^n+(-2)^n+2.0^n)=1,0,2,0,8,0,32,\ldots
 \end{displaymath}\end{theorem}
 \begin{theorem}\begin{eqnarray*}a_{11}^{(n)}&=&(2^n+(-2)^n+2.0^n)/4=1,0,2,0,8,0,32,\ldots\\
 a_{12}^{(n)}&=&(2^n-(-2)^n)/4=0,1,0,4,0,16,0\ldots\\
 a_{13}^{(n)}&=&(2^n+(-2)^n-2.0^n)/4=0,0,2,0,8,0,32,\ldots\\
 a_{14}^{(n)}&=&(2^n-(-2)^n)/4=0,1,0,4,0,16,0,\ldots\end{eqnarray*}\end{theorem}
 \begin{proof}
 We have\begin{displaymath}\mathbf{A}^n=\frac{1}{4}\left(\begin{array}{cccc} 1 & 1 & 1 &
1
 \\1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\1 & i & -1 &
 -i\end{array}\right)\left(\begin{array}{cccc} 2^n & 0 & 0 &
0
 \\0 & 0^n & 0 & 0 \\ 0 & 0 & (-2)^n & 0 \\0 & 0 & 0 &
 0^n\end{array}\right)\left(\begin{array}{cccc} 1 & 1 & 1 &
1
 \\1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\1 & -i & -1 &
 i\end{array}\right)\end{displaymath} From this we obtain
 \begin{eqnarray*}
 a_{11}^{(n)}&=&(2^n+0^n+(-2)^n+0^n)/4=(2^n+(-2)^n+2.0^n)/4\\
a_{12}^{(n)}&=&(2^n-i.0^n-(-2)^n+i.0^n)/4=(2^n-(-2)^n)/4\\
a_{13}^{(n)}&=&(2^n-1.0^n+(-2)^n-1.0^n)/4=(2^n+(-2)^n-2.0^n)/4\\
a_{14}^{(n)}&=&(2^n+i.0^n-(-2)^n-i.0^n)/4=(2^n-(-2)^n)/4.\end{eqnarray*}\end{proof}
\begin{corollary} The sequences above count the number of walks on the
graph $C_{4}$. In particular, $a_{11}^{(n)}$ counts the number of
closed walks on the edges of a quadrilateral based at a vertex.
\end{corollary} An easy calculation also gives us the important
\begin{corollary}\begin{displaymath}2^n=a_{11}^{(n)}+a_{12}^{(n)}+a_{13}^{(n)}+a_{14}^{(n)}.\end{displaymath}
\end{corollary} In terms of ordinary generating
functions of the sequences $a_{11}^{(n)}$, $a_{12}^{(n)}$,
$a_{13}^{(n)}$, $a_{14}^{(n)}$, we have the following algebraic
expression
\begin{displaymath}\frac{1}{1-2x}=\frac{1}{1-2x}\left(\frac{1-2x^2}{1+2x}+\frac{x}{1+2x}
+\frac{2x^2}{1+2x}+\frac{x}{1+2x}\right).\end{displaymath}
Anticipating the general case, we can state
\begin{theorem} There exists a partition
\begin{displaymath}\mathbf{B}=\mathbf{B_{0}}+\mathbf{B_{1}}+\mathbf{B_{2}}+\mathbf{B_{3}}\end{displaymath}
where the $\mathbf{B_{i}}$ are zero-binomial matrices with row
sums equal to $a_{11}^{(n)}$, $a_{12}^{(n)}$, $a_{13}^{(n)}$,
$a_{14}^{(n)}$, respectively, for $i=0\ldots3$.
\end{theorem}
In fact, we have
\begin{eqnarray*}a_{11}^{(n)}&=&\sum_{2k-n\equiv0 \bmod
4}\binom{n}{k}\\
a_{12}^{(n)}&=&\sum_{2k-n\equiv1 \bmod
4}\binom{n}{k}\\
a_{13}^{(n)}&=&\sum_{2k-n\equiv2 \bmod
4}\binom{n}{k}\\
a_{14}^{(n)}&=&\sum_{2k-n\equiv3 \bmod 4}\binom{n}{k}.
\end{eqnarray*} We shall provide a proof for this
later, when we look at the general case. Each of these sequences
satisfy the recurrence $$a_n=4a_{n-2}.$$ We can see the
decomposition induced from $C_4$ in the following coloured rendering
of $\mathbf{B}$.
\begin{displaymath}\mathbf{B}=\left(\begin{array}{cccccccc} \textcolor{magenta}{1} & 0 & 0
& 0 & 0 & 0 & 0 &\ldots \\

\textcolor{blue}{1} & \textcolor{red}{1} & 0 & 0 & 0 & 0 & 0 &\ldots \\


\textcolor{green}{1} & \textcolor{magenta}{2} &
\textcolor{green}{1}
& 0 & 0 & 0 & 0 &\ldots \\

\textcolor{red}{1} & \textcolor{blue}{3} & \textcolor{red}{3} & \textcolor{blue}{1} & 0 & 0 & 0  &\ldots \\

\textcolor{magenta}{1} & \textcolor{green}{4} &
\textcolor{magenta}{6} & \textcolor{green}{4} &
\textcolor{magenta}{1} & 0 & 0 &\ldots
\\\textcolor{blue}{1} & \textcolor{red}{5} & \textcolor{blue}{10} & \textcolor{red}{10} & \textcolor{blue}{5} & \textcolor{red}{1} & 0 & \ldots\\
\textcolor{green}{1} & \textcolor{magenta}{6} & \textcolor{green}{15} & \textcolor{magenta}{20} & \textcolor{green}{15} & \textcolor{magenta}{6} &\textcolor{green}{1} &  \ldots\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &
\ddots\end{array}\right)\begin{array}{cccc}
\textcolor{magenta}{1}&\textcolor{red}{0}&\textcolor{green}{0}&\textcolor{blue}{0}\\
\textcolor{magenta}{0}&\textcolor{red}{1}&\textcolor{green}{0}&\textcolor{blue}{1}\\
\textcolor{magenta}{2}&\textcolor{red}{0}&\textcolor{green}{2}&\textcolor{blue}{0}\\
\textcolor{magenta}{0}&\textcolor{red}{4}&\textcolor{green}{0}&\textcolor{blue}{4}\\
\textcolor{magenta}{8}&\textcolor{red}{0}&\textcolor{green}{8}&\textcolor{blue}{0}\\
\textcolor{magenta}{0}&\textcolor{red}{16}&\textcolor{green}{0}&\textcolor{blue}{16}\\
\textcolor{magenta}{32}&\textcolor{red}{0}&\textcolor{green}{32}&\textcolor{blue}{0}\\
\textcolor{magenta}{.}&\textcolor{red}{.}&\textcolor{green}{.}&\textcolor{blue}{.}\\
\end{array}
\end{displaymath}
\section{The case of $C_{5}$}
This case is worth noting, in the context of integer sequences, as
there is a link with the Fibonacci numbers. For the cyclic graph on
five vertices $C_{5}$ we have the following adjacency matrix
\begin{equation}\mathbf{A}=\left(\begin{array}{ccccc} 0 & 1 & 0 &
0 & 1
 \\1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\0 & 0 & 1 & 0 & 1\\
 1 & 0 & 0 & 1 & 0\end{array}\right)\end{equation} Diagonalizing
 with $\mathbf{F}$, we obtain \begin{displaymath}\mathbf{\Lambda}=\left(\begin{array}{ccccc} 2 & 0 & 0 &
0 & 0
 \\0 & \frac{\sqrt{5}}{2}-\frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & -\frac{\sqrt{5}}{2}-\frac{1}{2} & 0 & 0 \\0 & 0 & 0 & -\frac{\sqrt{5}}{2}-\frac{1}{2} & 0\\
 0 & 0 & 0 & 0 &
 \frac{\sqrt{5}}{2}-\frac{1}{2}\end{array}\right)\end{displaymath}
 \begin{proposition}
 $\frac{1}{5}\mathrm{trace}(\mathbf{A}^n)=(2^n+2(-1)^n(F(n+1)+F(n-1)))/5.$
 \end{proposition}
\begin{proof} We have
 $\frac{1}{5}\mathrm{trace}(\mathbf{A}^n)=(2^n+2(\frac{\sqrt{5}}{2}-\frac{1}{2})^n+2(-\frac{\sqrt{5}}{2}-\frac{1}{2})^n)/5$.
 An easy manipulation produces the result. \end{proof} This sequence is \seqnum{A054877}.
 \begin{theorem}\label{C_5} \begin{eqnarray*}
 a_{11}^{(n)}&=&(2^n+2(\frac{\sqrt{5}}{2}-\frac{1}{2})^n+2(-\frac{\sqrt{5}}{2}-\frac{1}{2})^n)/5\\
 a_{12}^{(n)}&=&(2^n+(\frac{\sqrt{5}}{2}-\frac{1}{2})^{n+1}+(-\frac{\sqrt{5}}{2}-\frac{1}{2})^{n+1})/5\\
 a_{13}^{(n)}&=&(2^n+(\frac{\sqrt{5}}{2}-\frac{1}{2})^n(\frac{\sqrt{5}}{2}+\frac{1}{2})+(-\frac{\sqrt{5}}{2}-\frac{1}{2})^n)(\frac{\sqrt{5}}{2}-\frac{1}{2}))/5\\
 a_{14}^{(n)}&=&(2^n+(\frac{\sqrt{5}}{2}-\frac{1}{2})^n(\frac{\sqrt{5}}{2}+\frac{1}{2})+(-\frac{\sqrt{5}}{2}-\frac{1}{2})^n)(\frac{\sqrt{5}}{2}-\frac{1}{2}))/5\\
 a_{15}^{(n)}&=&(2^n+(\frac{\sqrt{5}}{2}-\frac{1}{2})^{n+1}+(-\frac{\sqrt{5}}{2}-\frac{1}{2})^{n+1})/5.\end{eqnarray*}\end{theorem}
\begin{proof} The result follows from the fact that the first row of
$\mathbf{A}^n$ is given by
 $\frac{1}{5}\mathbf{F}(\lambda_{1}^n,\lambda_{2}^n,\lambda_{3}^n,\lambda_{4}^n,\lambda_{5}^n)'$.
 \end{proof}
 \begin{corollary} The sequences in Theorem \ref{C_5} count walks on
 $C_{5}$. In particular, the sequence $a_{11}^{(n)}$ counts
 closed walks of length n along the edges of a pentagon, based at
 a vertex. \end{corollary} We note that
 $a_{12}^{(n)}=a_{15}^{(n)}$. This is \seqnum{A052964}. Similarly
 $a_{13}^{(n)}=a_{14}^{(n)}$. This is (the absolute value of)
 \seqnum{A084179}.

 An easy calculation gives us the important result
 \begin{corollary}
 \begin{displaymath}2^n=a_{11}^{(n)}+a_{12}^{(n)}+a_{13}^{(n)}+a_{14}^{(n)}+a_{15}^{(n)}.\end{displaymath}\end{corollary}
 In terms of the ordinary generating functions for these
 sequences, we obtain the following algebraic identity
 \begin{displaymath}\frac{1}{1-2x}=\frac{1}{1-2x}\left(\frac{1-x-x^2}{1+x-x^2}+\frac{2x(1-x)}{1+x-x^2}+\frac{2x^2}{1+x-x^2}.\right)\end{displaymath}
Anticipating the general case, we can state the
\begin{theorem} There exists a partition
\begin{displaymath}\mathbf{B}=\mathbf{B_{0}}+\mathbf{B_{1}}+\mathbf{B_{2}}+\mathbf{B_{3}}+\mathbf{B_{4}}\end{displaymath}
where the $\mathbf{B_{i}}$ are zero-binomial matrices with row
sums equal to $a_{11}^{(n)}$, $a_{12}^{(n)}$, $a_{13}^{(n)}$,
$a_{14}^{(n)}$, $a_{15}^{(n)}$, respectively, for $i=0\ldots4$.
\end{theorem}
In fact, we have
\begin{eqnarray*}a_{11}^{(n)}&=&\sum_{2k-n\equiv0 \bmod
5}\binom{n}{k}\\
a_{12}^{(n)}&=&\sum_{2k-n\equiv1 \bmod
5}\binom{n}{k}\\
a_{13}^{(n)}&=&\sum_{2k-n\equiv2 \bmod
5}\binom{n}{k}\\
a_{14}^{(n)}&=&\sum_{2l-n\equiv3 \bmod
5}\binom{n}{k}\\
a_{15}^{(n)}&=&\sum_{2k-n\equiv4 \bmod
5}\binom{n}{k}.\end{eqnarray*} We note that
$$(1-p(\omega_5^0)x)(1-p(\omega_5^1)x)(1-p(\omega_5^2)x)(1-p(\omega_5^3)x)(1-p(\omega_5^4)x)=1-5x^3+5x^4-2x^5$$
for $p(x)=x+x^4$ which implies that each of the sequences satisfies
the recurrence
$$a_n=5a_{n-3}-5a_{n-4}+2a_{n-5}.$$
\section{The General Case of $C_{r}$}
We begin by remarking that since ${C}_r$ is a 2-regular graph, its
first eigenvalue is $2$. We have seen explicit examples of this in
the specific cases studied above. We now let $\mathbf{A}$ denote the
adjacency matrix of $C_{r}$. We have $\mathbf{A}=p(\mathbf{\pi})$
where $p(x)=x+x^{r-1}$, so
$\mathbf{A}=\mathrm{circ}(0,1,0,\ldots,0,1)$.
\begin{theorem}\begin{displaymath} 2^n=\sum_{j=1}^r
a_{1j}^{(n)}\end{displaymath} where $a_{1j}^{(n)}$ is the $j$-th
element of the first row of $\mathbf{A}^n$. \end{theorem}
\begin{proof} We have
\begin{eqnarray*}(a_{1j}^{(n)})_{1\le j \le
r}&=&\frac{1}{r}\mathbf{F}(\lambda_{1}^n,\lambda_{2}^n,\ldots,\lambda_{r}^n)'\\
&=&\frac{1}{r}(\sum_{k=1}^{r}
\lambda_{k}^n\omega^{(j-1)(k-1)}).\end{eqnarray*} Hence we
have\begin{eqnarray*}\sum_{j=1}^r
a_{1j}^{(n)}&=&\frac{1}{n}\sum_{j=1}^r\sum_{k=1}^{r}
\lambda_{k}^n\omega^{(j-1)(k-1)}\\
&=&\frac{1}{r}\sum_{k=1}^{r}
\lambda_{k}^n\sum_{j=1}^r \omega^{(j-1)(k-1)}\\
&=&\frac{1}{r} r\lambda_{1}^n=\frac{1}{r} r2^n=2^n.\end{eqnarray*}
\end{proof} We can now state the main result of this
section.
\begin{theorem}Let $\mathbf{A}$ be the adjacency matrix
of the cyclic graph on $r$ vertices $C_{r}$. Let $a_{1j}^{(n)}$ be
the first row elements of the matrix $\mathbf{A}^n$. There exists a
partition
\begin{displaymath}\mathbf{B}=\mathbf{B_{0}}+\mathbf{B_{1}}+\ldots+\mathbf{B_{r-1}}\end{displaymath}
where the $\mathbf{B_{i}}$ are zero-binomial matrices with row sums
equal to the sequences $a_{1,i+1}^{(n)}$, respectively, for
$i=0\ldots r-1$. \end{theorem}
\begin{proof}
We have already shown that \begin{displaymath}
2^n=\sum_{i=0}^n\binom{n}{i}=\sum_{j=1}^r
a_{1j}^{(n)}.\end{displaymath} We shall now exhibit a partition of
this sum which will complete the proof. For this, we recall that
$\mathbf{A}=p(\pi)$, where $p(x)=x+x^{r-1}$.
Then\begin{eqnarray*}(a_{1j}^{(n)})_{1\le j \le
r}&=&\frac{1}{r}\mathbf{F}_{r}\left(\begin{array}{c}p(\omega_{r}^0)^n\\p(\omega_{r}^1)^n\\
p(\omega_{r}^2)^n\\ \vdots
\\p(\omega_{r}^{r-1})^n\end{array}\right)\\
&=&\frac{1}{r}\mathbf{F}_{r}\left(\begin{array}{c}(\omega^0+\omega^{0.(r-1)})^n\\(\omega^1+\omega^{1.(r-1)})^n \\
(\omega^2+\omega^{2.(r-1)})^n\\ \vdots
\\(\omega^{r-1}+\omega^{(r-1).(r-1)})^n\end{array}\right)\\
&=&\frac{1}{r}\mathbf{F}_{r}\left(\begin{array}{c}(\omega^0+\omega^{-0})^n\\(\omega^1+\omega^{-1})^n \\
(\omega^2+\omega^{-2})^n\\ \vdots
\\(\omega^{r-1}+\omega^{-(r-1)})^n\end{array}\right)\end{eqnarray*}
\begin{eqnarray*}a_{1j}^{(n)}&=&\frac{1}{r}\sum_{l=0}^{r-1}(\omega_{r}^l+\omega_{r}^{-l})^n
\omega_{r}^{(j-1)l}\\
&=&\frac{1}{r}\sum_{l=0}^{r-1}\sum_{k=0}^n \binom{n}{k}
\omega_{r}^{kl} \omega_{r}^{-l(n-k)}
\omega_{r}^{(j-1)l}\\
&=&\sum_{k=0}^n\binom{n}{k}
(\frac{1}{r}\sum_{l=0}^{r-1}\omega_{r}^{kl}\omega_{r}^{-l(n-k)}\omega_{r}^{(j-1)l})\\
&=&\sum_{k=0}^n\binom{n}{k}
(\frac{1}{r}\sum_{l=0}^{r-1}\omega_{r}^{2kl+l(j-1-n)})\\
&=&\sum_{r|2k+(j-1-n)}\binom{n}{k}\\
&=&\sum_{2k\equiv (n+1-j) \bmod r}\binom{n}{k}.\end{eqnarray*} We
thus have $$B_i=[2k \equiv n+1-i \bmod r]\binom{n}{k}.$$
\end{proof}
\begin{corollary} \begin{displaymath}\mathbf{A}^n=\mathrm{circ}\left(\frac{1}{r}\mathbf{F}_r \left(2^n
\cos(\frac{2{\pi}j}{r})^n\right)_{0\le j \le
r-1}\right).\end{displaymath} \end{corollary} \begin{proof} This
comes about since
$(\omega^j+\omega^{-j})=e^{2{\pi}ij/k}+e^{-2{\pi}ij/k}=2\cos(2{\pi}j/r)$.\end{proof}
This verifies the well-known fact that the eigenvalues of $C_{r}$
are given by $2\cos(2{\pi}j/r)$, for $0\le j \le r-1$ \cite{West}.
 It is clear now that if $\sigma_i=i$-th symmetric function in
$2\cos(2{\pi}j/r)$, $0\le j \le r-1$, then the sequences
$a_{1j}^{(n)}$, $1\le j \le r$, satisfy the recurrence
$$a_n=\sigma_2 a_{n-2}-\sigma_3 a_{n-3}+ \cdots
+(-1)^{r-1}\sigma_{r-1} a_{r-1}.$$ We thus have
\begin{corollary}
The sequences $$a_{1j}^{(n)}=\sum_{2k=\equiv n+1-j \bmod
r}\binom{n}{k},$$ which satisfy the recurrence
$$a_n=\sigma_2 a_{n-2}-\sigma_3 a_{n-3}+ \cdots
+(-1)^{r-1}\sigma_{r-1} a_{r-1}$$ count the number of walks of
length $n$ from vertex $1$ to vertex $j$ of the cyclic graph $C_r$.
\end{corollary}

\section{A worked example}
We take the case $r=8$. We wish to characterize the $8$ sequences
$\sum_{8|2k+(j-1-n)}\binom{n}{k}$ for $j=1\ldots8$. We give
details of these sequences in the following table.

\begin{center}
\begin{tabular}{|c|c|c|} \hline sequence&$a_n$&binomial expression\\\hline $1,0,2,0,6,0,20\ldots$ &
$(1+(-1)^n)(0^n+2.2^{n/2}+2^n)/8$&$\sum_{n-2k\equiv0 \bmod
8}\binom{n}{k}$\\\hline
$0,1,0,3,0,10,0\ldots$&$(1-(-1)^n)(2^n+\sqrt{2}(\sqrt{2})^n)/8$&$\sum_{2k-n\equiv1
\bmod 8}\binom{n}{k}$\\\hline
$0,0,1,0,4,0,16,\ldots$&$(1+(-1)^n)2^n/8-0^n/4$&$\sum_{2k-n\equiv2
\bmod 8}\binom{n}{k}$\\\hline
$0,0,0,1,0,6,0\ldots$&$(1-(-1)^n)(2^n-\sqrt{2}(\sqrt{2})^n)/8$&$\sum_{2k-n\equiv3
\bmod 8}\binom{n}{k}$\\\hline
$0,0,0,0,2,0,12,\ldots$&$(1+(-1)^n)(2^n-2(\sqrt{2})^n)/8+0^n/4$&$\sum_{2k-n\equiv4
\bmod 8}\binom{n}{k}$\\\hline
$0,0,0,1,0,6,0\ldots$&$(1-(-1)^n)(2^n-\sqrt{2}(\sqrt{2})^n)/8$&$\sum_{2k-n\equiv5
\bmod 8}\binom{n}{k}$\\\hline
$0,0,1,0,4,0,16,\ldots$&$(1+(-1)^n)2^n/8-0^n/4$&$\sum_{2k-n\equiv6
\bmod 8}\binom{n}{k}$\\\hline
$0,1,0,3,0,10,0\ldots$&$(1-(-1)^n)(2^n+\sqrt{2}(\sqrt{2})^n)/8$&$\sum_{2k-n\equiv7
\bmod 8}\binom{n}{k}$\\\hline\end{tabular}\end{center} In terms of
ordinary generating functions, we have
\begin{eqnarray*}1,0,2,0,6,0,20\ldots &:&
\frac{1-4x+2x^2}{(1-2x^2)(1-4x^2)}\nonumber\\
0,1,0,3,0,10,0\ldots&:&\frac{x(1-3x^2)}{(1-2x^2)(1-4x^2)}\\
0,0,1,0,4,0,16,\ldots&:&\frac{x^2(1-2x^2)}{(1-2x^2)(1-4x^2)}\\
0,0,0,1,0,6,0\ldots&:&\frac{x^3}{(1-2x^2)(1-4x^2)}\\
0,0,0,0,2,0,12,\ldots&:&\frac{2x^4}{(1-2x^2)(1-4x^2)}\\
0,0,0,1,0,6,0\ldots&:&\frac{x^3}{(1-2x^2)(1-4x^2)}\\
0,0,1,0,4,0,16,\ldots&:&\frac{x^2(1-2x^2)}{(1-2x^2)(1-4x^2)}\\
0,1,0,3,0,10,0\ldots&:&\frac{x(1-3x^2)}{(1-2x^2)(1-4x^2)}\end{eqnarray*}
All these sequences satisfy the recurrence
\begin{displaymath}a_{n}=6a_{n-2}-8a_{n-4}\end{displaymath} with
suitable initial conditions. In particular, the sequence
$1,0,2,0,6,\ldots$ has general term
\begin{displaymath}a_{11}^{(n)}=\frac{0^n}{4}+(1+(-1)^n)(\frac{2^n}{8}+\frac{(\sqrt{2})^n}{4})\end{displaymath}
This counts the number of closed walks at a vertex of an octagon.

The sequences are essentially \seqnum{A112798}, \seqnum{A007582},
\seqnum{A000302}, \seqnum{A006516}, \seqnum{A020522}, with
interpolated zeros.
\section{The case $n\to\infty$}
We recall that the modified Bessel function of the first kind
\cite{Bessel}, \cite{WB} is defined by the integral
\begin{displaymath}I_{k}(z)=\int_{0}^{\pi}e^{z\cos(t)}\cos(kt)dt.\end{displaymath}
$I_{n}(z)$ has the following generating function
\begin{displaymath}e^{z(t+1/t)/2}=\sum_{k=-\infty}^{\infty}I_{k}(z)t^k.\end{displaymath}
Letting $z=2x$ and $t=1$, we get
\begin{displaymath}e^{2x}=\sum_{k=-\infty}^{\infty}I_{k}(2x)=I_{0}(2x)+2\sum_{k=1}^{\infty}I_{k}(2x).\end{displaymath}
The functions $I_{k}(2x)$ are the exponential generating functions
for the columns of Pascal's matrix (including `interpolated'
zeros). For instance, $I_{0}(2x)$ generates the sequence of
central binomial coefficients $1,0,2,0,6,0,20,0,70,\ldots$ with
formula $\binom{n}{n/2}(1+(-1)^n)/2$. This gives us the limit case
of the decompositions of Pascal's triangle - in essence, each of
the infinite matrices that sum to $\mathbf{B}_{\infty}$
corresponds to a matrix with only non-zero entries in a single
column.

The
matrix\begin{displaymath}\mathbf{A}_{\infty}=\left(\begin{array}{cccccc}0&1&0&0&0&\cdots\\
1&0&1&0&0&\cdots\\0&1&0&1&0&\cdots\\0&0&1&0&1&\cdots\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right)\end{displaymath}
corresponds to the limit cyclic graph $C_{\infty}$. We can
characterize the (infinite) set of sequences that correspond to
the row elements of the powers $\mathbf{A}_{\infty}^n$ as those
sequences with exponential generating functions given by the
family $I_{k}(2x)$. We also obtain that
trace$(\mathbf{A}_{\infty}^n)$ is the set of central binomial
numbers (with interpolated zeros) generated by $I_{0}(2x)$.
\section{Sequences associated with $K_{r}$}
By way of example for what follows, we look at the adjacency matrix
$\mathbf{A}$ for $K_4$. We note that $K_4$ is $3$-regular.
$\mathbf{A}$ is given by
\begin{displaymath}\mathbf{A}=\left(\begin{array}{cccc} 0 & 1 & 1 & 1
 \\1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\1 & 1 & 1 & 0\end{array}\right)\end{displaymath}
 Again, this matrix is circulant, with defining polynomial
 $p(x)=x+x^2+x^3=x(1+x+x^2)$. Using $\mathbf{F}$ to diagonalize
 it, we obtain \begin{displaymath}\mathbf{\Lambda}=\left(\begin{array}{cccc} 3 & 0 & 0 &
 0
 \\0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\0 & 0 & 0 & -1\end{array}\right)\end{displaymath}
 This leads us to the sequence
 $\frac{1}{4}\textrm{trace}(\mathbf{A}^n)=(3^n+3(-1)^n)/4=1, 0, 3, 6, 21,
 60,\ldots$, which is \seqnum{A054878}.
 Comparing this result with the expression $P(C_{n},
 4)=3^n+3(-1)^n$ we see that $\textrm{trace}(\mathbf{A}^n)=P(C_{n},
 4)$.
 \begin{proposition}\begin{eqnarray}a_{11}^{(n)}&=&(3^n+3(-1)^n)/4=1, 0, 3, 6, 21, 60,\ldots\nonumber\\\
 a_{12}^{(n)}&=&(3^n-(-1)^n)/4=0, 1, 2, 7, 20, 61,\ldots\nonumber\\\
  a_{13}^{(n)}&=&(3^n-(-1)^n)/4=0, 1, 2, 7, 20, 61,\ldots\nonumber\\\
   a_{14}^{(n)}&=&(3^n-(-1)^n)/4=0, 1, 2, 7, 20, 61,\ldots\nonumber\nonumber\end{eqnarray}\end{proposition}
\begin{proof} Using \begin{displaymath}(a_{1j}^{(n)})_{1\le j \le
n}=\frac{1}{n}\mathbf{F}(\lambda_{1}^n,\lambda_{2}^n,\ldots,\lambda_{n}^n)'\end{displaymath}
we obtain, for instance,
\begin{eqnarray*}a_{12}^{(n)}&=&(3^n+\omega(-1)^n+\omega^2(-1)^n+\omega^3(-1)^n)/4\\
&=&(3^n+(-1)^n(\omega+\omega^2+\omega^3))/4=(3^n-(-1)^n)/4\end{eqnarray*}\end{proof}
We note that $a_{11}^{(n)}$ is \seqnum{A054878}, while
$a_{12}^{(n)}=a_{13}^{(n)}=a_{14}^{(n)}$ are all equal to
\seqnum{A015518}.
\begin{corollary}\begin{displaymath}3^n=\mathbf{a}_{11}^{(n)}+\mathbf{a}_{12}^{(n)}+\mathbf{a}_{13}^{(n)}+\mathbf{a}_{14}^{(n)}.\end{displaymath}
\end{corollary}
\begin{corollary} The sequences $a_{1j}^{(n)}$ satisfy the
linear recurrence
\begin{displaymath}a_{n}=2a_{n-1}+3a_{n-2}\end{displaymath} with
initial conditions \begin{eqnarray}a_{0}=1,\textrm{
}a_{1}=0,\textrm{ }j=0\nonumber\\
a_{0}=0,\textrm{ }a_{1}=1,\textrm{ }j=2\ldots
4.\nonumber\end{eqnarray}\end{corollary} This result is typical of
the general case, which we now address. Thus we let $\mathbf{A}$
by the adjacency matrix of the complete graph $K_r$ on $r$
vertices.
\begin{lemma} The eigenvalues of $\mathbf{A}$ are
$r-1,-1,\ldots,-1$.\end{lemma} \begin{proof} We have
$\mathbf{A}=p(\mathbf{\pi})$, where $p(x)=x+x^2+\ldots+x^{r-1}$. The
eigenvalues of $\mathbf{A}$ are $p(1), p(\omega),
p(\omega^2),\ldots,p(\omega^{r-1})$, where $\omega^r=1$. Then
$p(1)=1+\ldots+1=r-1$.
Now\begin{displaymath}p(x)=x+\ldots+x^{r-1}=1+x+\ldots+x^{r-1}-1=\frac{1-x^r}{1-x}-1.\end{displaymath}
Then
\begin{displaymath}p(\omega^j)=\frac{1-\omega^{rj}}{1-\omega^j}-1=-1\end{displaymath}
since $\omega^{rj}=1$ for $j\ge 1$. \end{proof}
\begin{theorem} Let $\mathbf{A}$ be the adjacency matrix of the
complete graph $K_{r}$ on $r$ vertices. Then the $r$ sequences
$\mathbf{a}_{1j}^{(n)}$ defined by the first row of $\mathbf{A}^n$
satisfy the recurrence
\begin{displaymath}a_{n}=(r-2)a_{n-1}+(r-1)a_{n-2}\end{displaymath} with
initial conditions \begin{eqnarray}a_{0}=1,\textrm{
}a_{1}=0,\textrm{ }j=1\nonumber\\
a_{0}=0,\textrm{ }a_{1}=1,\textrm{ }j=2\ldots
r.\nonumber\end{eqnarray} In addition, we have
\begin{displaymath}(r-1)^n=\sum_{j=1}^r a_{1j}^{(n)}.\end{displaymath}\end{theorem}
\begin{proof} We have
\begin{eqnarray*}\left(\begin{array}{c}a_{11}^{(n)}\\a_{12}^{(n)}\\\vdots\\a_{1r}^{(n)}\end{array}\right)
&=&\frac{1}{r}\mathbf{F}_{r}\left(\begin{array}{c}\lambda_{1}^{n}\\\lambda_{2}^{n}\\\vdots\\\lambda_{r}^{n}\end{array}\right)\\
&=&\frac{1}{r}\mathbf{F}_{r}\left(\begin{array}{c}p(1)^n\\p(\omega_{r}^2)^n\\\vdots\\p(\omega_{r}^{r-1})^{n}\end{array}\right)\\
&=&\frac{1}{r}\mathbf{F}_{r}\left(\begin{array}{c}(r-1)^n\\(-1)^n\\\vdots\\(-1)^n\end{array}\right)\end{eqnarray*}
Hence
\begin{eqnarray*}a_{11}^{(n)}&=&\frac{1}{r}((r-1)^n+(-1)^n+\ldots+(-1)^n)\\
&=&\frac{1}{r}((r-1)^n+(r-1)(-1)^n).\end{eqnarray*} It is now easy
to show that $a_{11}^{(n)}$ satisfies the recurrence
\begin{displaymath}a_{n}=(r-2)a_{n-1}+(r-1)a_{n-2}\end{displaymath}
with $a_{0}=1$ and $a_{1}=0$.

For $j>1$, we
have\begin{eqnarray*}a_{1j}^{(n)}&=&\frac{1}{r}((r-1)^n+(-1)^n\omega^j+\dots+(-1)^n\omega^{j(k-1)})\\
&=&\frac{1}{r}((r-1)^n+(-1)^n(\omega^j+\ldots+\omega^{j(k-1)})\\
&=&\frac{1}{r}((r-1)^n+(-1)^n(\frac{1-\omega^{jk}}{1-\omega^j}-1)\\
&=&\frac{1}{r}((r-1)^n-(-1)^n).\end{eqnarray*} This is the
solution of the recurrence
\begin{displaymath}a_{n}=(r-2)a_{n-1}+(r-1)a_{n-2}\end{displaymath}
with $a_{0}=0$ and $a_{1}=1$ as required. To prove the final
assertion, we note that
\begin{eqnarray*}\sum_{j=1}^r
a_{1j}{(n)}&=&a_{11}{(n)}+(r-1)a_{12}^{(n)}\\
&=&\frac{(r-1)^n}{r}+\frac{(-1)^n(r-1)}{r}+(r-1)\left(\frac{(r-1)^n}{r}-\frac{(-1)^n}{r}\right)\\
&=&\frac{(r-1)^n}{r}(1+r-1)+\frac{(-1)^n(r-1)}{r}-\frac{(r-1)(-1)^n}{r}\\
&=&\frac{(r-1)^n}{r}r=(r-1)^n.\end{eqnarray*} \end{proof} Thus the
recurrences have solutions
\begin{displaymath}a_{n}=\frac{(r-1)^n}{r}+\frac{(-1)^n(r-1)}{r}\end{displaymath}
when \begin{displaymath}a_{0}=1,\textrm{
}a_{1}=0,\end{displaymath} and
\begin{displaymath}a_{n}'=\frac{(r-1)^n}{r}-\frac{(-1)^n}{r}\end{displaymath}
for \begin{displaymath}a_{0}'=0,\textrm{
}a_{1}'=1.\end{displaymath} We recognize in the first expression
above the formula for the chromatic polynomial $P(C_n,r)$, divided
by the factor $r$. Hence we have
\begin{corollary}$\frac{1}{r}\mathrm{trace}(\mathbf{A}^n)=a_{11}^{(n)}=\frac{1}{r}P(C_{n},r)$.\end{corollary}
We list below the first few of these sequences, which count walks of
length $n$ on the complete graph $K_{r}$. Note that we give the
sequences in pairs, as for each value of $r$, there are only two
distinct sequences. The first sequence of each pair counts the
number of closed walks from a vertex on $K_{r}$.
In addition, it counts $r$-colourings on $C_n$ (when multiplied by $r$). \begin{eqnarray*}r&=&3\\
(2^n+2(-1)^n)/3&:&1,0,2,2,6,10,22,\ldots\\
(2^n-(-1)^n)/3&:&0,1,1,3,5,11,21,\ldots\\
r&=&4\\
(3^n+3(-1)^n)/4&:&1,0,3,6,21,60,183,\ldots\\
(3^n-(-1)^n)/4&:&0,1,2,7,20,61,182,\ldots\\
r&=&5\\
(4^n+4(-1)^n)/5&:&1,0,4,12,52,204,820,\ldots\\
(4^n-(-1)^n)/5&:&0,1,3,13,51,205,819,\ldots\\
r&=&6\\
(5^n+5(-1)^n)/6&:&1,0,5,20,105,520,2605,\ldots\\
(5^n-(-1)^n)/6&:&0,1,4,21,104,521,2604,\ldots\end{eqnarray*} We
have encountered the first four sequences already. The last four
sequences are \seqnum{A109499}, \seqnum{A015521}, \seqnum{A109500}
and \seqnum{A015531}.

\begin{thebibliography}{9}

\bibitem{Barry}
 P. Barry, Triangle geometry and Jacobsthal Numbers,
\emph{Irish Math. Soc. Bulletin} \textbf{51} (2003), 45--57.

\bibitem{Davis}
P. J. Davis, \emph{Circulant Matrices}, John Wiley, New York, 1979.

\bibitem{EightyFive} T. Fink, Y. Mao, \emph{The $85$ ways to tie a
tie}, Fourth Estate, London, 2001.

\bibitem{FreySellers} D. D. Frey and J. A. Sellers, 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL3/SELLERS/sellers.html}{Jacobsthal Numbers and Alternating Sign Matrices}, \emph{J. Integer Sequences},
Vol.\ 3 (2000), Article 00.2.3.

\bibitem{Concrete} I. Graham, D. E. Knuth \& O. Patashnik, \emph{Concrete
Mathematics}, Addison--Wesley, Reading, MA, 1995.

\bibitem{Grimaldi}
R. P. Grimaldi, \emph{Discrete and Combinatorial Mathematics}, 4th
ed, Addison-Wesley, Reading, MA, 2000.

\bibitem{Sloane1}
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
Published electronically at
\href{http://www.research.att.com/~njas/sequences/}{http://www.research.att.com/\char'176njas/sequences/}, 2007.

\bibitem{Sloane2}
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,
\emph{Notices of the AMS}, \textbf{50} (2003), 912--915.

\bibitem{Bin}
E. W. Weisstein,
\href{http://mathworld.wolfram.com/BinomialTransform.html/}{\tt http://mathworld.wolfram.com/BinomialTransform.html/}, 2007.

\bibitem{Jac}
E. W. Weisstein,
\href{http://mathworld.wolfram.com/JacobsthalNumber.html/}{\tt 
http://mathworld.wolfram.com/JacobsthalNumber.html/}, 2007.

\bibitem{Bessel}
E. W. Weisstein, \\
\href{http://mathworld.wolfram.com/ModifiedBesselFunctionoftheFirstKind.html/}{\tt http://mathworld.wolfram.com/ModifiedBesselFunctionoftheFirstKind.html/}, 
2007.

\bibitem{West}
D. B. West, \emph{Introduction to Graph Theory}, Prentice0Hall,
New Jersey, 2001.

\bibitem{WB}
R. C. White and L. C. Barrett, \emph{Advanced Engineering
Mathematics}, McGraw-Hill, New York, 1982.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B83; Secondary 11Y55, 05T50, 65T50.

\noindent \emph{Keywords:}  Integer sequences, Jacobsthal numbers,
Pascal's triangle, cyclic graphs, circulant matrices, discrete
Fourier transform.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000302},
\seqnum{A001045}, \seqnum{A001145}, \seqnum{A006516},
\seqnum{A007582}, \seqnum{A015518}, \seqnum{A015521},
\seqnum{A015531}, \seqnum{A020522}, \seqnum{A052964},
\seqnum{A054878}, \seqnum{A078008}, \seqnum{A084179},
\seqnum{A109499}, \seqnum{A109500}, \seqnum{A112798}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in} \noindent
Received September 19 2005;
revised version received April 26 2007.
Published in {\it Journal of Integer Sequences}, May 4 2007.



\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in

\end{document}

.