On Integer Sequences Associated With the Cyclic and Complete Graphs

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

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.

1 Preliminaries

In [1] 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) [7, 8].

We begin with a brief recall of the relevant results of [1]. For this, we let the sequence of numbers J(n), be the solution of the recurrence

a_{n} = a_{n−1} + 2a_{n−2}, a_{0} = 0, a_{1} = 1,

with

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & … \\ J(n) & 0 & 1 & 1 & 3 & 5 & 11 & 21 & … \end{matrix}

J(n) = \frac{2^{n}}{3} − \frac{(−1)^{n}}{3} .  (1.1)

These are the Jacobsthal numbers [10]. 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 [3] and [4]. They appear in the OEIS as \underline{A001045}. When we change the initial conditions to a_{0} = 1, a_{1} = 0, we get a sequence which we will denote by J_{1}(n), \underline{A078008}, given by

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & … \\ J_{1}(n) & 1 & 0 & 2 & 2 & 6 & 10 & 22 & … \end{matrix}

J_{1}(n) = \frac{2^{n}}{3} + \frac{2(−1)^{n}}{3} .  (1.2)

We see that

2^{n} = 2J(n) + J_{1}(n).  (1.3)

What is less obvious is that the Jacobsthal numbers are sums of binomial coefficients. In fact, we have

J_{1}(n) = ∑_{(n+k) mod 3=0} \binom{n}{k}

J(n) = ∑_{(n+k) mod 3=1} \binom{n}{k}

J(n) = ∑_{(n+k) mod 3=2} \binom{n}{k}.

In [1], 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

∑_{k≡l( mod m)} \binom{n}{k} = \frac{1}{m} ∑_{j=0}^{m−1}(1 + ω^{j})^{n}ω^{−lj}  (1.4)

where ω = e^{2πi/m}. We then have, for m = 3,

∑_{k≡−n( mod 3)} \binom{n}{k} = \frac{1}{3} ∑_{j=0}^{2}(1 + ω^{j})^{n}ω^{nj}

= \frac{1}{3}(2^{n} + (1 + ω)^{n}ω^{n} + (1 + ω^{2})^{n}ω^{2n})
= \frac{1}{3}(2^{n} + (−ω^{2})^{n}ω^{n} + (−ω)^{n}ω^{2n})
= \frac{1}{3}(2^{n} + (−1)^{n}ω^{2n}ω^{n} + (−1)^{n}ω^{n}ω^{2n})
= \frac{1}{3}(2^{n} + (−1)^{n}(ω^{3n} + ω^{3n}))
= \frac{1}{3}(2^{n} + 2(−1)^{n}) = J_{1}(n).

In like manner, we have

∑_{k≡(−n+1)( mod 3)} \binom{n}{k} = \frac{1}{3} ∑_{j=0}^{2}(1 + ω^{j})^{n}ω^{(n−1)j}

= \frac{1}{3}(2^{n} + (1 + ω)^{n}ω^{n−1} + (1 + ω^{2})^{n}ω^{2(n−1)})
= \frac{1}{3}(2^{n} + (−ω^{2})^{n}ω^{n−1} + (−ω)^{n}ω^{2(n−1)})
= \frac{1}{3}(2^{n} + (−1)^{n}ω^{2n}ω^{n−1} + (−1)^{n}ω^{n}ω^{2(n−1)})
= \frac{1}{3}(2^{n} + (−1)^{n}(ω^{3n−1} + ω^{3n−2}))
= \frac{1}{3}(2^{n} + (−1)^{n}(ω^{−1} + ω^{−2}))
= \frac{1}{3}(2^{n} + (−1)^{n}(ω^{2} + ω^{1}))
= \frac{1}{3}(2^{n} − (−1)^{n}) = J(n).

The third identity is proven in similar fashion.

Since

2^{n} = ∑_{k=0}^{n} \binom{n}{k}

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 B whose (n, k)-th element is equal to \binom{n}{k}:

B = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & … \\ 1 & 4 & 6 & 4 & 1 & 0 & … \\ 1 & 5 & 10 & 10 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

We shall call a lower-triangular matrix a zero-binomial matrix if its elements are either 0 or binomial coefficients. We can then state the relevant result of [1] as follows.

Theorem 1.1. There exists a partition

B = B_{0} + B_{1} + B_{2}

where the B_{i} are zero-binomial matrices with row sums equal to J_{1}(n), J(n), J(n) respectively for i = 0, …, 2.

We have

B_{i} = ([n + k ≡ i mod 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 [5].

We can see this decomposition in the following coloured rendering of B.

B = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & … \\ 1 & 4 & 6 & 4 & 1 & 0 & … \\ 1 & 5 & 10 & 10 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 2 & 1 & 1 \\ 2 & 3 & 3 \\ 6 & 5 & 5 \\ 10 & 11 & 11 \\ . & . & . \end{matrix}

2 Graphs

We now wish to draw a link between the foregoing and graph theory. To this end, we recall a number of relevant definitions [6, 12]. 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 loop is an edge whose endpoints are equal. To any graph, we may associate the adjacency matrix, which is an n × 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 simple graphs, with no loops or multiple edges.

The 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-regular graph will then have row sums and column sums equal to k.

If x, y ∈ V then an x-y walk in X is a (loop-free) finite alternating sequence

x = x_{0}, e_{1}, x_{1}, e_{2}, x_{2}, e_{3}, …, e_{r−1}, x_{r−1}, e_{r}, x_{r} = y

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 ≤ i ≤ r. The length of this walk is r. If x = y, the walk is closed, otherwise it is open. If no edge in the x-y walk is repeated, then the walk is called an x-y trail. A closed x-x trail is called a circuit. If no vertex of the x-y walk is repeated, then the walk is called an x-y path. When x = y, a closed path is called a cycle. The number of walks from x to y of length n is given by the x, y-th entry of A^{n}, where A is the adjacency matrix of the graph X.

The cyclic graph C_{r} on r vertices is the graph with r vertices and r edges such that if we number the vertices 0, 1, …, r − 1, then vertex i is connected to the two adjacent vertices i + 1 and i − 1(modr). The complete graph K_{r} on r vertices is the loop-free graph where for all x, y ∈ V, x ≠ 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 chromatic polynomial of a graph. If X = (V, E) is an undirected graph, a 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 chromatic number of X and is written χ(X). For k ∈ 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,

P (K_{r}, k) = k(k − 1) … (k − r + 1)  (2.1)

and

P (C_{r}, k) = (k − 1)^{r} + (−1)^{r}(k − 1).  (2.2)

3 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 × 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 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, . . ..

Note that the Binomial matrix B and the Fourier matrix 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πink}{r}} respectively).

The adjacency matrix of a graph, normally denoted by A, will be indexed as usual from (1, 1). Similarly the eigenvalues of the adjacency matrix will be labelled λ_{1}, λ_{2}, …, λ_{r}.

4 Circulant matrices

We now provide a quick overview of the theory of circulant matrices [2], as these will be encountered shortly. An r × r circulant matrix 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}, …, c_{r}) then

c_{jk} = c_{k−j+1}

where subscripts are taken modulo n. Circulant matrices are diagonalized by the discrete Fourier transform, whose matrix F_{r} is defined as follows : let ω(r) = e^{−2πi/r} where i = \sqrt{−1}. Then F_{r} has i, j-th element ω^{i·j}, 0 ≤ i, j ≤ r − 1.

We can write the above matrix as C = circ(c_{1}, …, c_{r}). The permutation matrix π = circ(0, 1, 0, …, 0) plays a special role. If we let p be the polynomial p(x) = c_{1} + c_{2}x + … + c_{r}x^{r−1}, then C = p(π).

We have, for C a circulant matrix,

C = F^{−1}ΛF,
Λ = diag(p(1), p(ω), …, p(ω^{r−1})).

The i-th eigenvalue of C is λ_{i} = p(ω^{i}), 1 ≤ i ≤ r.

5 The graph C_{3} and Jacobsthal numbers

We let A be the adjacency matrix of the cyclic graph C_{3}. We have

A = ( \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} )

We note that this matrix is circulant. We shall be interested both in the powers A^{n} of A and its eigenvalues. There is the following connection between these entities:

trace(A^{n}) = ∑_{j=1}^{r} λ_{j}^{n}

where λ_{1}, …, λ_{r} are the eigenvalues of A. Here, r = 3. In order to obtain the eigenvalues of A, we use F_{3} to diagonalize it. We obtain

F_{3}^{−1}AF_{3} = ( \begin{matrix}2 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & −1 \end{matrix} )

We immediately have

trace(A^{n}) = 2^{n} + 2(−1)^{n}

Comparing with (1.2), we have

Proposition 5.1. J_{1}(n) = \frac{1}{3}trace(A^{n})

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

Proposition 5.2. J_{1}(r) = \frac{1}{3}P (C_{r}, 3).

Since A is circulant, it and its powers 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 A^{n} - that is, we shall look at the sequences a_{1j}^{(n)}, for j = 1, 2, 3.

Theorem 5.1.

a_{11}^{(n)} = J_{1}(n), a_{12}^{(n)} = J(n), a_{13}^{(n)} = J(n)

Proof. We use the fact that

A^{n} = F^{−1} ( \begin{matrix}2^{n} & 0 & 0 \\ 0 & (−1)^{n} & 0 \\ 0 & 0 & (−1)^{n} \end{matrix} ) F  (5.1)

Then

A^{n} = \frac{1}{3} ( \begin{matrix}1 & 1 & 1 \\ 1 & ω & ω^{2} \\ 1 & ω^{2} & ω^{4} \end{matrix} ) ( \begin{matrix}2^{n} & 0 & 0 \\ 0 & (−1)^{n} & 0 \\ 0 & 0 & (−1)^{n} \end{matrix} ) ( \begin{matrix}1 & 1 & 1 \\ 1 & ω & ω^{2} \\ 1 & ω^{2} & ω^{4} \end{matrix} )

= \frac{1}{3} ( \begin{matrix}2^{n} & (−1)^{n} & (−1)^{n} \\ ⋮ & ⋮ & ⋮ \end{matrix} ) ( \begin{matrix}1 & 1 & 1 \\ 1 & ω & ω^{2} \\ 1 & ω^{2} & ω^{4} \end{matrix} )

= \frac{1}{3} ( \begin{matrix}2^{n} + 2(−1)^{n} & (2^{n} + (−1)^{n}ω_{3} + (−1)^{n}ω_{3}^{2}) & (2^{n} + (−1)^{n}ω_{3}^{2} + (−1)^{n}ω_{3}^{4}) \\ ⋮ & ⋮ & ⋮ \end{matrix} )

Thus we obtain

a_{11}^{(n)} = (2^{n} + 2(−1)^{n})/3
a_{12}^{(n)} = (2^{n} + (−1)^{n}ω_{3} + (−1)^{n}ω_{3}^{2})/3
a_{13}^{(n)} = (2^{n} + (−1)^{n}ω_{3}^{2} + (−1)^{n}ω_{3}^{4})/3.

The result now follows from the fact that

1 + ω_{3} + ω_{3}^{2} = 1 + ω_{3}^{2} + ω_{3}^{4} = 0.

Corollary 5.1. 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.

An immediate calculation gives

Corollary 5.2.

2^{n} = a_{11}^{(n)} + a_{13}^{(n)} + a_{13}^{(n)}.

The identity

2^{n} = 2J(n) + J_{1}(n)

now becomes a consequence of the identity

2^{n} = a_{11}^{(n)} + a_{13}^{(n)} + a_{13}^{(n)}.

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

\frac{1}{1 − 2x} = \frac{1 − x}{(1 + x)(1 − 2x)} + \frac{x}{(1 + x)(1 − 2x)} + \frac{x}{(1 + x)(1 − 2x)}

and in terms of exponential generating functions, we have

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

or more simply,

exp(2x) = \frac{1}{3}(exp(2x) + 2 exp(−x)) + 2\frac{1}{3}(exp(2x) − exp(−x)).

An examination of the calculations above and the fact that F is symmetric allows us to state Corollary 5.3.

( \begin{matrix}a_{11}^{(n)} \\ a_{12}^{(n)} \\ a_{13}^{(n)} \end{matrix} ) = \frac{1}{3} ( \begin{matrix}1 & 1 & 1 \\ 1 & ω & ω^{2} \\ 1 & ω^{2} & ω^{4} \end{matrix} ) ( \begin{matrix}2^{n} \\ (−1)^{n} \\ (−1)^{n} \end{matrix} )

In fact, this result can be easily generalized to give the following

( a_{11}^{(n)} ; a_{12}^{(n)} ; ⋮ ; a_{1r}^{(n)} ) = \frac{1}{r}F_{r} ( λ_{1}^{n} ; λ_{2}^{n} ; ⋮ ; λ_{r}^{n} )  (5.2)

so that

A^{n} = circ(a_{11}^{(n)}, a_{12}^{(n)}, …, a_{1r}^{(n)}) = circ(\frac{1}{r}F_{r}(λ_{1}^{n}, …, λ_{r}^{n})′).

It is instructive to work out the generating function of these sequences. For instance, we have

a_{12}^{(n)} = 1.2^{n} + ω.(−1)^{n} + ω^{2}.(−1)^{n}.

This implies that a_{12}^{(n)} has generating function

g_{12}(x) = \frac{1}{1 − 2x} + \frac{ω}{1 + x} + \frac{ω^{2}}{1 + x}
= \frac{(1 + x)^{2} + ω(1 + x)(1 − 2x) + ω^{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}} .

This is as expected, but it also highlights the importance of (1 − 2x)(1 + x)(1 + x) = (1 − λ_{1}x)(1 − λ_{2}x)(1 − λ_{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(ω_{3}^{0})x)(1 − p(ω_{3}^{1})x)(1 − p(ω_{3}^{2})x)

where p(x) = x + x^{2}.

6 The case of C_{4}

For the cyclic graph on four vertices C_{4} we have the following adjacency matrix

A = ( \begin{matrix}0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix} )  (6.1)

We can carry out a similar analysis as for the case n = 3. Using F to diagonalize A, we obtain

F^{−1}AF = ( \begin{matrix}2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & −2 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} )

From this, we can immediately deduce the following result. Theorem 6.1.

\frac{1}{4}traceA^{n} = \frac{1}{4}(2^{n} + (−2)^{n} + 2.0^{n}) = 1, 0, 2, 0, 8, 0, 32, …

Theorem 6.2.

a_{11}^{(n)} = (2^{n} + (−2)^{n} + 2.0^{n})/4 = 1, 0, 2, 0, 8, 0, 32, …
a_{12}^{(n)} = (2^{n} − (−2)^{n})/4 = 0, 1, 0, 4, 0, 16, 0 …
a_{13}^{(n)} = (2^{n} + (−2)^{n} − 2.0^{n})/4 = 0, 0, 2, 0, 8, 0, 32, …
a_{14}^{(n)} = (2^{n} − (−2)^{n})/4 = 0, 1, 0, 4, 0, 16, 0, …

Proof. We have

A^{n} = \frac{1}{4} ( \begin{matrix}1 & 1 & 1 & 1 \\ 1 & −i & −1 & i \\ 1 & −1 & 1 & −1 \\ 1 & i & −1 & −i \end{matrix} ) ( \begin{matrix}2^{n} & 0 & 0 & 0 \\ 0 & 0^{n} & 0 & 0 \\ 0 & 0 & (−2)^{n} & 0 \\ 0 & 0 & 0 & 0^{n} \end{matrix} ) ( \begin{matrix}1 & 1 & 1 & 1 \\ 1 & i & −1 & −i \\ 1 & −1 & 1 & −1 \\ 1 & −i & −1 & i \end{matrix} )

From this we obtain

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.

Corollary 6.1. 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.

An easy calculation also gives us the important

Corollary 6.2.

2^{n} = a_{11}^{(n)} + a_{12}^{(n)} + a_{13}^{(n)} + a_{14}^{(n)}.

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

\frac{1}{1 − 2x} = \frac{1}{1 − 2x} (\frac{1 − 2x^{2}}{1 + 2x} + \frac{x}{1 + 2x} + \frac{2x^{2}}{1 + 2x} + \frac{x}{1 + 2x}) .

Anticipating the general case, we can state

Theorem 6.3. There exists a partition

B = B_{0} + B_{1} + B_{2} + B_{3}

where the 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 … 3.

In fact, we have

a_{11}^{(n)} = ∑_{2k−n≡0 mod 4} \binom{n}{k}

a_{12}^{(n)} = ∑_{2k−n≡1 mod 4} \binom{n}{k}

a_{13}^{(n)} = ∑_{2k−n≡2 mod 4} \binom{n}{k}

a_{14}^{(n)} = ∑_{2k−n≡3 mod 4} \binom{n}{k}.

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

B = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 4 & 6 & 4 & 1 & 0 & 0 & … \\ 1 & 5 & 10 & 10 & 5 & 1 & 0 & … \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 2 & 0 & 2 & 0 \\ 0 & 4 & 0 & 4 \\ 8 & 0 & 8 & 0 \\ 0 & 16 & 0 & 16 \\ 32 & 0 & 32 & 0 \\ . & . & . & . \end{matrix}

7 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

A = ( \begin{matrix}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{matrix} )  (7.1)

Diagonalizing with F, we obtain

Λ = ( \begin{matrix}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{matrix} )

Proposition 7.1. \frac{1}{5}trace(A^{n}) = (2^{n} + 2(−1)^{n}(F (n + 1) + F (n − 1)))/5.

Proof. We have \frac{1}{5}trace(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.

This sequence is \underline{A054877}.

Theorem 7.1.

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.

Proof. The result follows from the fact that the first row of A^{n} is given by \frac{1}{5}F(λ_{1}^{n}, λ_{2}^{n}, λ_{3}^{n}, λ_{4}^{n}, λ_{5}^{n})′.

Corollary 7.1. The sequences in Theorem 7.1 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.

We note that a_{12}^{(n)} = a_{15}^{(n)}. This is \underline{A052964}. Similarly a_{13}^{(n)} = a_{14}^{(n)}. This is (the absolute value of) \underline{A084179}.

An easy calculation gives us the important result

Corollary 7.2.

2^{n} = a_{11}^{(n)} + a_{12}^{(n)} + a_{13}^{(n)} + a_{14}^{(n)} + a_{15}^{(n)}.

In terms of the ordinary generating functions for these sequences, we obtain the following algebraic identity

\frac{1}{1 − 2x} = \frac{1}{1 − 2x} (\frac{1 − x − x^{2}}{1 + x − x^{2}} + \frac{2x(1 − x)}{1 + x − x^{2}} + \frac{2x^{2}}{1 + x − x^{2}} .)

Anticipating the general case, we can state the

Theorem 7.2. There exists a partition

B = B_{0} + B_{1} + B_{2} + B_{3} + B_{4}

where the 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 … 4.

In fact, we have

a_{11}^{(n)} = ∑_{2k−n≡0 mod 5} \binom{n}{k}
a_{12}^{(n)} = ∑_{2k−n≡1 mod 5} \binom{n}{k}
a_{13}^{(n)} = ∑_{2k−n≡2 mod 5} \binom{n}{k}
a_{14}^{(n)} = ∑_{2l−n≡3 mod 5} \binom{n}{k}
a_{15}^{(n)} = ∑_{2k−n≡4 mod 5} \binom{n}{k}.

We note that

(1 − p(ω_{5}^{0})x)(1 − p(ω_{5}^{1})x)(1 − p(ω_{5}^{2})x)(1 − p(ω_{5}^{3})x)(1 − p(ω_{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}.

8 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 A denote the adjacency matrix of C_{r}. We have A = p(π) where p(x) = x+x^{r−1}, so A = circ(0, 1, 0, …, 0, 1). Theorem 8.1.

2^{n} = ∑_{j=1}^{r} a_{1j}^{(n)}

where a_{1j}^{(n)} is the j-th element of the first row of A^{n}. Proof. We have

(a_{1j}^{(n)})_{1≤j≤r} = \frac{1}{r}F(λ_{1}^{n}, λ_{2}^{n}, …, λ_{r}^{n})′
= \frac{1}{r}(∑_{k=1}^{r} λ_{k}^{n}ω^{(j−1)(k−1)}).

Hence we have

∑_{j=1}^{r} a_{1j}^{(n)} = \frac{1}{n} ∑_{j=1}^{r} ∑_{k=1}^{r} λ_{k}^{n}ω^{(j−1)(k−1)}

= \frac{1}{r} ∑_{k=1}^{r} λ_{k}^{n} ∑_{j=1}^{r} ω^{(j−1)(k−1)}

= \frac{1}{r}rλ_{1}^{n} = \frac{1}{r}r2^{n} = 2^{n}.

We can now state the main result of this section.

Theorem 8.2. Let 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 A^{n}. There exists a partition

B = B_{0} + B_{1} + … + B_{r−1}

where the B_{i} are zero-binomial matrices with row sums equal to the sequences a_{1,i+1}^{(n)}, respectively, for i = 0 … r − 1.

Proof. We have already shown that

2^{n} = ∑_{i=0}^{n} \binom{n}{i} = ∑_{j=1}^{r} a_{1j}^{(n)}.

We shall now exhibit a partition of this sum which will complete the proof. For this, we recall that A = p(π), where p(x) = x + x^{r−1}. Then

(a_{1j}^{(n)})_{1≤j≤r} = \frac{1}{r}F_{r} ( p(ω_{r}^{0})^{n} ; p(ω_{r}^{1})^{n} ; p(ω_{r}^{2})^{n} ; ⋮ ; p(ω_{r}^{r−1})^{n} )

= \frac{1}{r}F_{r} ( (ω^{0} + ω^{0.(r−1)})^{n} ; (ω^{1} + ω^{1.(r−1)})^{n} ; (ω^{2} + ω^{2.(r−1)})^{n} ; ⋮ ; (ω^{r−1} + ω^{(r−1).(r−1)})^{n} )

= \frac{1}{r}F_{r} ( (ω^{0} + ω^{−0})^{n} ; (ω^{1} + ω^{−1})^{n} ; (ω^{2} + ω^{−2})^{n} ; ⋮ ; (ω^{r−1} + ω^{−(r−1)})^{n} )

a_{1j}^{(n)} = \frac{1}{r} ∑_{l=0}^{r−1}(ω_{r}^{l} + ω_{r}^{−l})^{n}ω_{r}^{(j−1)l}
= \frac{1}{r} ∑_{l=0}^{r−1} ∑_{k=0}^{n} \binom{n}{k}ω_{r}^{kl}ω_{r}^{−l(n−k)}ω_{r}^{(j−1)l}
= ∑_{k=0}^{n} \binom{n}{k}(\frac{1}{r} ∑_{l=0}^{r−1} ω_{r}^{kl}ω_{r}^{−l(n−k)}ω_{r}^{(j−1)l})
= ∑_{k=0}^{n} \binom{n}{k}(\frac{1}{r} ∑_{l=0}^{r−1} ω_{r}^{2kl+l(j−1−n)})
= ∑_{r|2k+(j−1−n)} \binom{n}{k}
= ∑_{2k≡(n+1−j) mod r} \binom{n}{k}.

We thus have

B_{i} = [2k ≡ n + 1 − i mod r]\binom{n}{k}.

Corollary 8.1.

A^{n} = circ (\frac{1}{r}F_{r} (2^{n} cos(\frac{2πj}{r})^{n})_{0≤j≤r−1}) .

Proof. This comes about since (ω^{j} + ω^{−j}) = e^{2πij/k} + e^{−2πij/k} = 2 cos(2πj/r).

This verifies the well-known fact that the eigenvalues of C_{r} are given by 2 cos(2πj/r), for 0 ≤ j ≤ r − 1 [12]. It is clear now that if σ_{i} = i-th symmetric function in 2 cos(2πj/r), 0 ≤ j ≤ r − 1, then the sequences a_{1j}^{(n)}, 1 ≤ j ≤ r, satisfy the recurrence

a_{n} = σ_{2}a_{n−2} − σ_{3}a_{n−3} + ⋯ + (−1)^{r−1}σ_{r−1}a_{r−1}.

We thus have Corollary 8.2. The sequences

a_{1j}^{(n)} = ∑_{2k=≡n+1−j mod r} \binom{n}{k},

which satisfy the recurrence

a_{n} = σ_{2}a_{n−2} − σ_{3}a_{n−3} + ⋯ + (−1)^{r−1}σ_{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}.

9 A worked example

We take the case r = 8. We wish to characterize the 8 sequences ∑_{8|2k+(j−1−n)} \binom{n}{k} for j = 1 … 8. We give details of these sequences in the following table.

sequence  a_{n}  binomial expression
1, 0, 2, 0, 6, 0, 20 … (1 + (−1)^{n})(0^{n} + 2.2^{n/2} + 2^{n})/8  ∑_{n−2k≡0 mod 8} \binom{n}{k}
0, 1, 0, 3, 0, 10, 0 …  (1 − (−1)^{n})(2^{n} + \sqrt{2}(\sqrt{2})^{n})/8  ∑_{2k−n≡1 mod 8} \binom{n}{k}
0, 0, 1, 0, 4, 0, 16, …  (1 + (−1)^{n})2^{n}/8 − 0^{n}/4  ∑_{2k−n≡2 mod 8} \binom{n}{k}
0, 0, 0, 1, 0, 6, 0 …  (1 − (−1)^{n})(2^{n} − \sqrt{2}(\sqrt{2})^{n})/8  ∑_{2k−n≡3 mod 8} \binom{n}{k}
0, 0, 0, 0, 2, 0, 12, … (1 + (−1)^{n})(2^{n} − 2(\sqrt{2})^{n})/8 + 0^{n}/4 ∑_{2k−n≡4 mod 8} \binom{n}{k}
0, 0, 0, 1, 0, 6, 0 …  (1 − (−1)^{n})(2^{n} − \sqrt{2}(\sqrt{2})^{n})/8  ∑_{2k−n≡5 mod 8} \binom{n}{k}
0, 0, 1, 0, 4, 0, 16, …  (1 + (−1)^{n})2^{n}/8 − 0^{n}/4  ∑_{2k−n≡6 mod 8} \binom{n}{k}
0, 1, 0, 3, 0, 10, 0 …  (1 − (−1)^{n})(2^{n} + \sqrt{2}(\sqrt{2})^{n})/8  ∑_{2k−n≡7 mod 8} \binom{n}{k}

In terms of ordinary generating functions, we have

1, 0, 2, 0, 6, 0, 20 …: \frac{1 − 4x + 2x^{2}}{(1 − 2x^{2})(1 − 4x^{2})}
0, 1, 0, 3, 0, 10, 0 …: \frac{x(1 − 3x^{2})}{(1 − 2x^{2})(1 − 4x^{2})}
0, 0, 1, 0, 4, 0, 16, …: \frac{x^{2}(1 − 2x^{2})}{(1 − 2x^{2})(1 − 4x^{2})}
0, 0, 0, 1, 0, 6, 0 …: \frac{x^{3}}{(1 − 2x^{2})(1 − 4x^{2})}
0, 0, 0, 0, 2, 0, 12, …: \frac{2x^{4}}{(1 − 2x^{2})(1 − 4x^{2})}
0, 0, 0, 1, 0, 6, 0 …: \frac{x^{3}}{(1 − 2x^{2})(1 − 4x^{2})}
0, 0, 1, 0, 4, 0, 16, …: \frac{x^{2}(1 − 2x^{2})}{(1 − 2x^{2})(1 − 4x^{2})}
0, 1, 0, 3, 0, 10, 0 …: \frac{x(1 − 3x^{2})}{(1 − 2x^{2})(1 − 4x^{2})}

All these sequences satisfy the recurrence

a_{n} = 6a_{n−2} − 8a_{n−4}

with suitable initial conditions. In particular, the sequence 1, 0, 2, 0, 6, … has general term

a_{11}^{(n)} = \frac{0^{n}}{4} + (1 + (−1)^{n})(\frac{2^{n}}{8} + \frac{(\sqrt{2})^{n}}{4} )

This counts the number of closed walks at a vertex of an octagon.

The sequences are essentially \underline{A112798}, \underline{A007582}, \underline{A000302}, \underline{A006516}, \underline{A020522}, with interpolated zeros.

10 The case n → ∞

We recall that the modified Bessel function of the first kind [11], [13] is defined by the integral

I_{k}(z) = ∫_{0}^{π} e^{z cos(t)} cos(kt)dt.

I_{n}(z) has the following generating function

e^{z(t+1/t)/2} = ∑_{k=−∞}^{∞} I_{k}(z)t^{k}.

Letting z = 2x and t = 1, we get

e^{2x} = ∑_{k=−∞}^{∞} I_{k}(2x) = I_{0}(2x) + 2 ∑_{k=1}^{∞} I_{k}(2x).

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, … 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 B_{∞} corresponds to a matrix with only non-zero entries in a single column.

The matrix

A_{∞} = ( \begin{matrix}0 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 0 & 1 & 0 & 0 & ⋯ \\ 0 & 1 & 0 & 1 & 0 & ⋯ \\ 0 & 0 & 1 & 0 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

corresponds to the limit cyclic graph C_{∞}. We can characterize the (infinite) set of sequences that correspond to the row elements of the powers A_{∞}^{n} as those sequences with exponential generating functions given by the family I_{k}(2x). We also obtain that trace(A_{∞}^{n}) is the set of central binomial numbers (with interpolated zeros) generated by I_{0}(2x).

11 Sequences associated with K_{r}

By way of example for what follows, we look at the adjacency matrix A for K_{4}. We note that K_{4} is 3-regular. A is given by

A = ( \begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix} )

Again, this matrix is circulant, with defining polynomial p(x) = x + x^{2} + x^{3} = x(1 + x + x^{2}). Using F to diagonalize it, we obtain

Λ = ( \begin{matrix}3 & 0 & 0 & 0 \\ 0 & −1 & 0 & 0 \\ 0 & 0 & −1 & 0 \\ 0 & 0 & 0 & −1 \end{matrix} )

This leads us to the sequence \frac{1}{4}trace(A^{n}) = (3^{n} + 3(−1)^{n})/4 = 1, 0, 3, 6, 21, 60, …, which is \underline{A054878}. Comparing this result with the expression P (C_{n}, 4) = 3^{n} + 3(−1)^{n} we see that trace(A^{n}) = P (C_{n}, 4).

Proposition 11.1.

a_{11}^{(n)} = (3^{n} + 3(−1)^{n})/4 = 1, 0, 3, 6, 21, 60, …
a_{12}^{(n)} = (3^{n} − (−1)^{n})/4 = 0, 1, 2, 7, 20, 61, …
a_{13}^{(n)} = (3^{n} − (−1)^{n})/4 = 0, 1, 2, 7, 20, 61, …
a_{14}^{(n)} = (3^{n} − (−1)^{n})/4 = 0, 1, 2, 7, 20, 61, …

Proof. Using

(a_{1j}^{(n)})_{1≤j≤n} = \frac{1}{n}F(λ_{1}^{n}, λ_{2}^{n}, …, λ_{n}^{n})′

we obtain, for instance,

a_{12}^{(n)} = (3^{n} + ω(−1)^{n} + ω^{2}(−1)^{n} + ω^{3}(−1)^{n})/4
= (3^{n} + (−1)^{n}(ω + ω^{2} + ω^{3}))/4 = (3^{n} − (−1)^{n})/4

We note that a_{11}^{(n)} is \underline{A054878}, while a_{12}^{(n)} = a_{13}^{(n)} = a_{14}^{(n)} are all equal to \underline{A015518}.

Corollary 11.1.

3^{n} = a_{11}^{(n)} + a_{12}^{(n)} + a_{13}^{(n)} + a_{14}^{(n)}.

Corollary 11.2. The sequences a_{1j}^{(n)} satisfy the linear recurrence

a_{n} = 2a_{n−1} + 3a_{n−2}

with initial conditions

a_{0} = 1, a_{1} = 0, j = 0
a_{0} = 0, a_{1} = 1, j = 2 … 4.

This result is typical of the general case, which we now address. Thus we let A by the adjacency matrix of the complete graph K_{r} on r vertices.

Lemma 11.1. The eigenvalues of A are r − 1, −1, …, −1.

Proof. We have A = p(π), where p(x) = x + x^{2} + … + x^{r−1}. The eigenvalues of A are p(1), p(ω), p(ω^{2}), …, p(ω^{r−1}), where ω^{r} = 1. Then p(1) = 1 + … + 1 = r − 1. Now

p(x) = x + … + x^{r−1} = 1 + x + … + x^{r−1} − 1 = \frac{1 − x^{r}}{1 − x} − 1.

Then

p(ω^{j}) = \frac{1 − ω^{rj}}{1 − ω^{j}} − 1 = −1

since ω^{rj} = 1 for j ≥ 1.

Theorem 11.1. Let A be the adjacency matrix of the complete graph K_{r} on r vertices. Then the r sequences a_{1j}^{(n)} defined by the first row of A^{n} satisfy the recurrence

a_{n} = (r − 2)a_{n−1} + (r − 1)a_{n−2}

with initial conditions

a_{0} = 1, a_{1} = 0, j = 1
a_{0} = 0, a_{1} = 1, j = 2 … r.

In addition, we have

(r − 1)^{n} = ∑_{j=1}^{r} a_{1j}^{(n)}.

Proof. We have

( a_{11}^{(n)} ; a_{12}^{(n)} ; ⋮ ; a_{1r}^{(n)} ) = \frac{1}{r}F_{r} ( λ_{1}^{n} ; λ_{2}^{n} ; ⋮ ; λ_{r}^{n} )

= \frac{1}{r}F_{r} ( p(1)^{n} ; p(ω_{r}^{2})^{n} ; ⋮ ; p(ω_{r}^{r−1})^{n} )

= \frac{1}{r}F_{r} ( (r − 1)^{n} ; (−1)^{n} ; ⋮ ; (−1)^{n} )

Hence

a_{11}^{(n)} = \frac{1}{r}((r − 1)^{n} + (−1)^{n} + … + (−1)^{n})
= \frac{1}{r}((r − 1)^{n} + (r − 1)(−1)^{n}).

It is now easy to show that a_{11}^{(n)} satisfies the recurrence

a_{n} = (r − 2)a_{n−1} + (r − 1)a_{n−2}

with a_{0} = 1 and a_{1} = 0.

For j > 1, we have

a_{1j}^{(n)} = \frac{1}{r}((r − 1)^{n} + (−1)^{n}ω^{j} + ⋯ + (−1)^{n}ω^{j(k−1)})
= \frac{1}{r}((r − 1)^{n} + (−1)^{n}(ω^{j} + … + ω^{j(k−1)})
= \frac{1}{r}((r − 1)^{n} + (−1)^{n}(\frac{1 − ω^{jk}}{1 − ω^{j}} − 1)
= \frac{1}{r}((r − 1)^{n} − (−1)^{n}).

This is the solution of the recurrence

a_{n} = (r − 2)a_{n−1} + (r − 1)a_{n−2}

with a_{0} = 0 and a_{1} = 1 as required. To prove the final assertion, we note that

∑_{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) (\frac{(r − 1)^{n}}{r} − \frac{(−1)^{n}}{r} )
= \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}.

Thus the recurrences have solutions

a_{n} = \frac{(r − 1)^{n}}{r} + \frac{(−1)^{n}(r − 1)}{r}

when

a_{0} = 1, a_{1} = 0,

and

a′_{n} = \frac{(r − 1)^{n}}{r} − \frac{(−1)^{n}}{r}

for

a′_{0} = 0, a′_{1} = 1.

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 Corollary 11.3. \frac{1}{r}trace(A^{n}) = a_{11}^{(n)} = \frac{1}{r}P (C_{n}, r).

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

r = 3
(2^{n} + 2(−1)^{n})/3 : 1, 0, 2, 2, 6, 10, 22, …
(2^{n} − (−1)^{n})/3 : 0, 1, 1, 3, 5, 11, 21, …
r = 4
(3^{n} + 3(−1)^{n})/4 : 1, 0, 3, 6, 21, 60, 183, …
(3^{n} − (−1)^{n})/4 : 0, 1, 2, 7, 20, 61, 182, …
r = 5
(4^{n} + 4(−1)^{n})/5 : 1, 0, 4, 12, 52, 204, 820, …
(4^{n} − (−1)^{n})/5 : 0, 1, 3, 13, 51, 205, 819, …
r = 6
(5^{n} + 5(−1)^{n})/6 : 1, 0, 5, 20, 105, 520, 2605, …
(5^{n} − (−1)^{n})/6 : 0, 1, 4, 21, 104, 521, 2604, …

We have encountered the first four sequences already. The last four sequences are \underline{A109499}, \underline{A015521}, \underline{A109500} and \underline{A015531}.

References

[1] P. Barry, Triangle geometry and Jacobsthal Numbers, Irish Math. Soc. Bulletin 51 (2003), 45–57.

[2] P. J. Davis, Circulant Matrices, John Wiley, New York, 1979.

[3] T. Fink, Y. Mao, The 85 ways to tie a tie, Fourth Estate, London, 2001.

[4] D. D. Frey and J. A. Sellers, Jacobsthal Numbers and Alternating Sign Matrices, J. Integer Sequences, Vol. 3 (2000), Article 00.2.3.

[5] I. Graham, D. E. Knuth & O. Patashnik, Concrete Mathematics, Addison–Wesley, Reading, MA, 1995.

[6] R. P. Grimaldi, Discrete and Combinatorial Mathematics, 4th ed, Addison-Wesley, Reading, MA, 2000.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/˜ njas/sequences/, 2007.

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices of the AMS, 50 (2003), 912–915.

[9] E. W. Weisstein, http://mathworld.wolfram.com/BinomialTransform.html/, 2007.
[10] E. W. Weisstein, http://mathworld.wolfram.com/JacobsthalNumber.html/, 2007.

[11] E. W. Weisstein,

   http://mathworld.wolfram.com/ModifiedBesselFunctionoftheFirstKind.html/,

2007.

[12] D. B. West, Introduction to Graph Theory, Prentice0Hall, New Jersey, 2001.

[13] R. C. White and L. C. Barrett, Advanced Engineering Mathematics, McGraw-Hill, New York, 1982.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 11Y55, 05T50, 65T50. Keywords: Integer sequences, Jacobsthal numbers, Pascal’s triangle, cyclic graphs, circulant matrices, discrete Fourier transform.

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

Received September 19 2005; revised version received April 26 2007. Published in Journal of Integer Sequences, May 4 2007.

Return to Journal of Integer Sequences home page.