\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}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

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

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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

	\begin{center}
		\vskip 1cm{\LARGE\bf
			Jacobsthal Numbers and Associated \\
			\vskip .13in
			Hessenberg Matrices}
		\vskip 1cm
		\large
		Ahmet \"{O}tele\c{s}\\
		Department of Mathematics \\
		Faculty of Education \\
        Dicle University \\
	Diyarbak{\i}r \\
	Turkey \\
		\href{mailto:aoteles85@gmail.com}{\tt aoteles85@gmail.com} \\
			\vskip 1cm
			Zekeriya Y. Karatas\\
      Department of Mathematics, Physics and Computer Science \\
			University of Cincinnati Blue Ash College \\
			Blue Ash, OH 45236 \\
			USA \\
			\href{mailto:zekeriya.karatas@uc.edu}{\tt zekeriya.karatas@uc.edu} \\
            \vskip 1cm
            Diyar O. Mustafa Zangana\\
            Department of Mathematics \\
			Art and Science Faculty \\
			Siirt University \\
			Siirt\\
			Turkey \\
			\href{mailto:diyar.math2@gmail.com}{\tt diyar.math2@gmail.com} \\
				\end{center}
	
	\vskip .2 in
	
	\def\cI{{\mathcal I}}
	\def\cR{{\mathcal R}}
	
	
	\def\a{{\alpha}}
	\def\b{{\beta}}
	\def\g{{\gamma}}
	\def\d{{\delta}}
	\def\l{{\lambda}}
	\def\o{{\omega}}
	\def\e{{\epsilon}}
	\def\ep{{\varepsilon}}
	\def\s{{\sigma}}
	\def\t{{\tau}}
	\def\v{{\nu}}
	\def\th{{\theta}}
	
	
	\def \K{{\bbbk}}
	\def\E{{\mathbf E}}
	\def\G{{\mathcal G}}
	\def\O{{\mathcal O}}
	\def \R{{\bbbr}}
	\def\({\left(}
	\def\){\right)}
	
	\def\lf{\lfloor}
	\def\rf{\rfloor}
	\def\lc{\lceil}
	\def\rc{\rceil}

\vfill\eject
	
\begin{abstract}
In this paper, we define two $n \times n$ Hessenberg matrices, one of
which corresponds to the adjacency matrix of a bipartite graph. We then
investigate the relationships between the Hessenberg matrices and the
Jacobsthal numbers. Moreover, we give Maple algorithms to verify
our results.
\end{abstract}

\section{Introduction}

The famous Fibonacci, Pell, and Jacobsthal integer
sequences, which appear, respectively, in the On-Line
Encyclopedia of Integer Sequences (OEIS) as sequences
\seqnum{A000045}, \seqnum{A000129}, and \seqnum{A001045} \cite{OEIS},
provide invaluable research opportunities for us. These number sequences contribute significantly to mathematics, especially to the field of number theory, as  Koshy observed \cite{koshy,koshy1}. In particular, the Jacobsthal sequence is considered as one of the major sequences among the well-known integer sequences. The Jacobsthal sequence attracts many researchers in number theory.

The \textit{Jacobsthal sequence} $\left(J_{n}\right)_{n\geq0}$ is
defined by the recurrence relation as follows:
\begin{equation}
J_{n}=J_{n-1}+2J_{n-2},  \label{juice}
\end{equation}
with $J_{0}=0$ and $J_{1}=1$, for $n\geq2$ \cite{horadam}. The number $J_{n}$ is called the $n$th \textit{Jacobsthal number}. The list of the first $11$ terms of the sequence is given in Table $1$.

\begin{table}[H]
\centering
\begin{tabular}
 [c]{c|ccccccccccccc}
$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$
& $\cdots$\\\hline
$J_{n}$ & $0$ & $1$ & $1$ & $3$ & $5$ & $11$ & $21$ & $43$ &
$85$ & $171$ & $341$ & $683$ & $\cdots$
\end{tabular}
\caption{Terms of $J_{n}$}
\label{table:1}
\end{table}

We note for further reference that
\begin{equation}
J_{n}=\frac{2^{n}-\left(-1\right)^{n}}{3} \label{cheese}
\end{equation}
is the Binet formula of the Jacobsthal sequence $\left(J_{n}\right)_{n\geq0}$ \cite{horadam}.

Microcontrollers and other computers use conditional instructions to change
the flow of the execution of a program. In addition to branch instructions, some
microcontrollers use skip instructions which conditionally skip to the next
instruction. This winds up being useful for one case out of the four
possibilities on $2$ bits, $3$ cases on $3$ bits, $5 $ cases on $4$ bits, $11$
on $5$ bits, $21$ on $6$ bits, $43$ on $7$ bits, $85$ on $8$ bits, \ldots,
which are exactly the Jacobsthal numbers. 


K\"{o}nig studied the properties of the bipartite graphs in \cite{Konig1,Konig2}. His papers were motivated by an attempt to give a new approach to evaluate the determinants of matrices. In practice, the bipartite graphs form a model of interaction between two different types of objects such as jobs and workers, telephone exchanges and cities \cite{Asratian}. The enumeration or the actual construction of the perfect matchings of the bipartite graphs has many applications,
for example, in maximal flow problems, and assignment and scheduling
problems arising in operational research \cite{minc}. The number of perfect
matchings of bipartite graphs also plays a significant role in organic
chemistry \cite{Wheland}.

A \textit{bipartite graph} $G$ is a graph whose vertex set $V$ can be partitioned into
two subsets $V_{1}$ and $V_{2}$ such that every edge of the bipartite graph $G$ joins a vertex
in $V_{1}$ and a vertex in $V_{2}$. A \textit{perfect matching} (or \textit{1-factor}) of a
graph is a matching in which each vertex has exactly one edge incident on it.
In other words, every vertex in the graph has degree $1$. Let $A(G)$ be the adjacency
matrix of the bipartite graph $G$, and let $\mu(G)$ denote the number of perfect
matchings of the bipartite graph $G$. Then the following fact which states the relation between $\mu(G)$ and $A(G)$ can be found in \cite{minc}:
$\mu(G)=\sqrt{\mathrm{per}\left(A(G)\right)}$.

Let $G$ be a bipartite graph whose vertex set $V$ is partitioned into two
subsets $V_{1}$ and $V_{2}$ such that $\left\vert V_{1}\right\vert =\left\vert
V_{2}\right\vert =n$. Next, we construct the \textit{bipartite adjacent matrix} $B(G)=\left(
b_{ij}\right)$ of the bipartite graph $G$ as follows: $b_{ij}=1$ if and only if the bipartite graph $G$ contains
an edge from $v_{i}\in V_{1}$ to $v_{j}\in V_{2}$, and otherwise $b_{ij}=0$.
Minc stated in \cite{minc} that the number of perfect matchings of the bipartite graph $G$ is equal to the
permanent of its bipartite adjacency matrix.

The \textit{permanent} of an $n \times n$ matrix $A=\left(a_{ij}\right)$ is defined
by
\[
\mathrm{per}\left(A\right) =\sum_{\sigma\epsilon S_{n}}\prod\limits_{i=1}
^{n}a_{i\sigma(i)},
\]
where the summation extends over all permutations $\sigma$ of the symmetric
group $S_{n}$. The permanent of a matrix is analogous to the determinant
in which all of the signs used in the Laplace expansion of minors are positive.


Permanents have many applications in physics, chemistry, electrical engineering, and so on.
Some of the most important applications of permanents are via graph theory.
They essentially involve enumerations of certain subgraphs of a graph or a directed graph.
A more difficult problem with many applications is the enumeration of perfect matchings of a graph \cite{minc}.
Therefore, the counting the number of perfect matchings in bipartite graphs has been a very popular problem.

There are many papers on the relationships between the well-known number sequences and the matrices. \cite{lee1,lee2,Shiu,kilic2,lee3,kilic,oteles,oteles2,sahin,yilmazz,yilmaz,fonseca,kilic3,kilic4,Vasco} are some of these papers.

In this paper, we firstly define an $n \times n$ Hessenberg matrix that
corresponds to the adjacency matrix of a bipartite graph, and we prove that
the number of perfect matchings of the bipartite graph is equal to the
Jacobsthal number. Secondly, we define another 
$n \times n$ Hessenberg matrix, and we prove that the permanent of the Hessenberg matrix is equal to the Jacobsthal
number. Finally, we give the Maple algorithms to verify our results.

\section{Main results}

Let $A=\left[a_{ij}\right]$ be an $m\times n$ real matrix with row vectors
$\alpha_{1},\alpha_{2},\ldots,\alpha_{m}$.  We say that the matrix $A$ is \textit{contractible}
on column (resp. row) $k$ if column (resp. row) $k$ contains exactly two nonzero
entries. Suppose that the matrix $A$ is contractible on column $k$ with $a_{ik}\neq0\neq
a_{jk}$ and $i\neq j$. Then the $(m-1)\times(n-1)$ matrix $A_{ij:k}$ obtained
from the matrix $A$ by replacing row $i$ with $a_{jk}\alpha_{i}+a_{ik}\alpha_{j}$ and
deleting row $j$ and column $k$ is called the \textit{contraction} of the matrix $A$ on
column $k$ relative to rows $i$ and $j$. If the matrix $A$ is contractible on row $k$ with
$a_{ki}\neq0\neq a_{kj}$ and $i\neq j$, then the matrix $A_{k:ij}=\left[
A_{ij:k}^{T}\right]^{T}$ is called the contraction of the matrix $A$ on row $k$
relative to columns $i$ and $j$. We say that the matrix $A$ can be contracted to a matrix
$B$, if either $B=A$ or there exist matrices $A_{0},A_{1},\ldots,A_{t}$ $\left(t\geq
1\right)$ such that $A_{0}=A$, $A_{t}=B$, and $A_{r}$ is a contraction of the matrix $A_{r-1}$
for $r=1,\ldots,t$ \cite{brualdi}.

Brualdi and Gibson \cite{brualdi} proved the following result about the
permanent of a matrix.

\begin{lemma}\label{l1}
Let $A$ be a nonnegative integral matrix of order $n$ for $n>1$, and let $B$ be
a contraction of the matrix $A$. Then
\begin{equation}
\mathrm{per}A=\mathrm{per}B.
\end{equation}
\end{lemma}

Let us define the $n \times n$ $\left(0,1\right)$-Hessenberg matrix $A_{n}$
as follows:
\begin{equation}
A_{n}=\left(
\begin{array}
[c]{cccccccc}
1 & 0 & 1 & 0 & \cdots & 1 & 0 & \cdots\\
1 & 1 & 1 & 1 & \cdots & \cdots & 1 & 1\\
0 & 1 & 1 & 1 & 1 & \cdots & \cdots & 1\\
\vdots & 0 & 1 & \ddots & \ddots & \ddots &  & \vdots\\
\vdots &  & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\
\vdots &  &  & \ddots & \ddots & 1 & 1 & 1\\
\vdots &  &  &  & 0 & 1 & 1 & 1\\
0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 1
\end{array}
\right),  \label{strawberry}
\end{equation}
where
\[
a_{ij}=\begin{cases}
1, & \text{if $i=1$ and $j-1 \equiv 0$ (mod $2$);}\\
1, & \text{if $i>1$ and $j-i \geq -1$;}\\
0, & \text{otherwise.}
\end{cases}
\]

\begin{theorem}\label{t1}
Let $G(A_{n})$ be the bipartite graph with bipartite adjacency matrix $A_{n}$
given by (\ref{strawberry}). Then the number of perfect matchings of the bipartite
graph $G(A_{n})$ is the $n$th Jacobsthal number $J_{n}$.
\end{theorem}

\begin{proof}
If $n=3$, then we have $\mathrm{per}A_{3}=\mathrm{per}\left(
\begin{array}
[c]{ccc}
1 & 0 & 1\\
1 & 1 & 1\\
0 & 1 & 1
\end{array}
\right)=3=J_{3}$.

Let $A_{n}^{k}$ be the $k$th contraction of the matrix $A_{n}$, $1\leq k\leq n-2$. Then by
the definition of  a  contraction, the matrix $A_{n}$ can be contracted on
column $1$ so that we get
\[
A_{n}^{1}=\left(
\begin{array}
[c]{cccccccc}
1 & 2 & 1 & 2 & \cdots & 1 & 2 & \cdots\\
1 & 1 & 1 & 1 & \cdots & \cdots & 1 & 1\\
0 & 1 & 1 & 1 & 1 & \cdots & \cdots & 1\\
\vdots & 0 & 1 & \ddots & \ddots & \ddots &  & \vdots\\
\vdots &  & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\
\vdots &  &  & \ddots & \ddots & 1 & 1 & 1\\
\vdots &  &  &  & 0 & 1 & 1 & 1\\
0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 1
\end{array}
\right)_{(n-1)\times(n-1)}.
\]
After contracting the matrix $A_{n}^{1}$ on column $1$, we have
\[
A_{n}^{2}=\left(
\begin{array}
[c]{cccccccc}
3 & 2 & 3 & 2 & \cdots & 3 & 2 & \cdots\\
1 & 1 & 1 & 1 & \cdots & \cdots & 1 & 1\\
0 & 1 & 1 & 1 & 1 & \cdots & \cdots & 1\\
\vdots & 0 & 1 & \ddots & \ddots & \ddots &  & \vdots\\
\vdots &  & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\
\vdots &  &  & \ddots & \ddots & 1 & 1 & 1\\
\vdots &  &  &  & 0 & 1 & 1 & 1\\
0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 1
\end{array}
\right)_{(n-2)\times(n-2)}.
\]
Since the Jacobsthal number $J_{2}=1$ and the Jacobsthal number $J_{3}=3$, we get
\[
A_{n}^{2}=\left(
\begin{array}
[c]{cccccccc}
J_{3} & 2J_{2} & J_{3} & 2J_{2} & \cdots & J_{3} & 2J_{2} & \cdots\\
1 & 1 & 1 & 1 & \cdots & \cdots & 1 & 1\\
0 & 1 & 1 & 1 & 1 & \cdots & \cdots & 1\\
\vdots & 0 & 1 & \ddots & \ddots & \ddots &  & \vdots\\
\vdots &  & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\
\vdots &  &  & \ddots & \ddots & 1 & 1 & 1\\
\vdots &  &  &  & 0 & 1 & 1 & 1\\
0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 1
\end{array}
\right)  _{(n-2)\times(n-2)}.
\]
Furthermore, the matrix $A_{n}^{2}$ can be contracted on column $1$ and
the Jacobsthal number $J_{4}=5$ so that
\[
A_{n}^{3}=\left(
\begin{array}
[c]{cccccccc}
J_{4} & 2J_{3} & J_{4} & 2J_{3} & \cdots & J_{4} & 2J_{3} & \cdots\\
1 & 1 & 1 & 1 & \cdots & \cdots & 1 & 1\\
0 & 1 & 1 & 1 & 1 & \cdots & \cdots & 1\\
\vdots & 0 & 1 & \ddots & \ddots & \ddots &  & \vdots\\
\vdots &  & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\
\vdots &  &  & \ddots & \ddots & 1 & 1 & 1\\
\vdots &  &  &  & 0 & 1 & 1 & 1\\
0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 1
\end{array}
\right)_{(n-3)\times(n-3)}.
\]
Continuing this process, we get the $k$th contraction of the matrix $A_{n}$ as
\[
A_{n}^{k}=\left(
\begin{array}
[c]{cccccccc}
J_{k+1} & 2J_{k} & \cdots & J_{k+1} & 2J_{k} & \cdots & \cdots & \cdots\\
1 & 1 & 1 & \cdots & 1 & 1 & \cdots & 1\\
0 & 1 & 1 & 1 & \cdots & 1 & 1 & 1\\
\vdots & 0 & 1 & \ddots & \ddots & \ddots &  & \vdots\\
\vdots &  & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\
\vdots &  &  & \ddots & \ddots & 1 & 1 & 1\\
\vdots &  &  &  & 0 & 1 & 1 & 1\\
0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 1
\end{array}
\right)_{(n-k)\times(n-k)}
\]
for $3\leq k\leq n-4$. Hence, the $(n-3)$th contraction of the matrix $A_{n}$ is
\[
A_{n}^{n-3}=\left(
\begin{array}
[c]{ccc}
J_{n-2} & 2J_{n-3} & J_{n-2} \\
1 & 1 & 1\\
0 & 1 & 1
\end{array}
\right)_{3\times3},
\]
which gives
\[
A_{n}^{n-2}=\left(
\begin{array}
[c]{cc}
J_{n-1} & 2J_{n-2} \\
1 & 1
\end{array}
\right)_{2\times2}
\]
by the contraction of the matrix $A_{n}^{n-3}$ on column $1$. From  Lemma \ref{l1}, we get $\mathrm{per}A_{n}=\mathrm{per}A_{n}^{n-2}=J_{n-1}+2J_{n-2}$. Moreover,
we have $J_{n}=J_{n-1}+2J_{n-2}$ from (\ref{juice}). Therefore, $\mathrm{per}A_{n}=J_{n}$, which completes the proof.
\end{proof}

Let $B_{n}$ be an $n \times n$ Hessenberg matrix as follows:
\begin{equation}
B_{n}=\left(
\begin{array}
[c]{cccccccc}
1 & -1 & 1 & -1 & \cdots & 1 & -1 & \cdots\\
1 & 2 & 0 & 0 & \cdots & \cdots & 0 & 0\\
0 & 1 & 2 & 0 & 0 & \cdots & \cdots & 0\\
\vdots & 0 & 1 & \ddots & \ddots & \ddots &  & \vdots\\
\vdots &  & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\
\vdots &  &  & \ddots & \ddots & 2 & 0 & 0\\
\vdots &  &  &  & 0 & 1 & 2 & 0\\
0 & \cdots & \cdots & \cdots & \cdots & 0 & 1 & 2
\end{array}
\right),  \label{honey}
\end{equation}
where
\[
b_{ij}=
\begin{cases}
1, & \text{if $j-i=-1$ or $i=1$ and $j-1 \equiv 0$ (mod $2$);}\\
-1, & \text{if $i=1$ and $j \equiv 0$ (mod $2$);}\\
2, & \text{if $i>1$ and $j-i=0$;}\\
0, & \text{otherwise.}
\end{cases}
\]

Now, let us give the following lemma for the Jacobsthal sequence $\left(J_{n}\right)_{n\geq0}$ which will be used later.

\begin{lemma}\label{l2}
Let $J_{n}$ be the $n$th Jacobsthal number. Then we have
\begin{equation}
J_{n}=2J_{n-1}-\left(-1\right)^{n}.
\label{olive}
\end{equation}

\end{lemma}

\begin{proof}
By using the Binet formula (\ref{cheese}), we obtain
\begin{displaymath}
J_{n} =\frac{2\cdot2^{n-1}+\left(-1\right)^{n-1}}{3}
 =2\left(\frac{2^{n-1}-\left(-1\right)^{n-1}}{3}\right)-\left(-1\right)^{n}.
\end{displaymath}
The proof follows by substituting $J_{n-1}$ for $\frac
{2^{n-1}-\left(-1\right)^{n-1}}{3}$.
\end{proof}

\begin{theorem}\label{t2}
Let $B_{n}$ be the $n \times n$ Hessenberg matrix given by (\ref{honey}). Then the permanent of the matrix $B_{n}$ is equal to the $n$th Jacobsthal number $J_{n}$.
\end{theorem}

\begin{proof}
Let $B_{n}^{k}$ be the $k$th contraction of the matrix $B_{n}$ for $1\leq k\leq n-2$. Then by
applying successive contractions to the matrices $B_{n}^{k}$ on their first columns for $1\leq k\leq
n-3$, we get
\begin{equation}
B_{n}^{n-2} = \begin{cases}
\left(
\begin{array}
{cc}
J_{n-1} & 1\\
1 & 2
\end{array}
\right),  & \text{if $n$ is odd;} \\[0.3in]
\left(
\begin{array}
{cc}
J_{n-1} & -1\\
1 & 2
\end{array}
\right),  & \text{if $n$ is even.}
\end{cases}
\label{cucumber}
\end{equation}
By Lemma \ref{l1} and the equation (\ref{cucumber}), we deduce that $\mathrm{per}B_{n}=\mathrm{per}B_{n}^{n-2}=2J_{n-1}-\left(-1\right)^{n}$.
Moreover, we have $J_{n}=2J_{n-1}-\left(-1\right)^{n}$ from (\ref{olive}), and the result follows.
\end{proof}

\section*{Appendix}

The following Maple program calculates the number of
perfect matchings of the bipartite graph $G(A_{n})$ given in Theorem \ref{t1}.

\bigskip

{\tt 
\ with(LinearAlgebra):

\ permanent:=proc(n)  local i,j,r,f,A;

\ f:=(i,j)-\textgreater piecewise(i=1 and j mod 2=1,1,i\textgreater 1 and j-i\textgreater -2,1,0);

\ A:=Matrix(n,n,f):

\ for r from 0 to n-2 do

\ \quad print(r,A):

\ \quad for j from 2 to n-r do

\ \quad\quad A[1,j]:=A[2,1]*A[1,j]+A[1,1]*A[2,j]:

\ \quad \quad od:

\ \quad A:=DeleteRow(DeleteColumn(Matrix(n-r,n-r,A),1),2):

\ \quad od:

\ print(r,eval(A)):

\ end proc:with(LinearAlgebra):
}

\bigskip

It can be called, for example, with the syntax

\bigskip

\centerline{\tt permanent(8);}

\bigskip

The following Maple algorithm calculates the permanent of
the Hessenberg matrix $B_{n}$ given in Theorem \ref{t2}.

\bigskip

{\tt 
\ with(LinearAlgebra):

\ permanent2:=proc(n) local i,j,r,f,A;

\ f:=(i,j)-\textgreater piecewise(i=1 and j mod 2=0,-1,j-i=-1,1,i=1 and j-1 mod 2=0,1,

\ i\textgreater 1 and j-i=0,2,0);

\ A:=Matrix(n,n,f):

\ for r from 0 to n-2 do

\ \quad print(r,A):

\ \quad for j from 2 to n-r do

\ \quad\quad A[1,j]:=A[2,1]*A[1,j]+A[1,1]*A[2,j]:

\ \quad\quad od:

\ \quad A:=DeleteRow(DeleteColumn(Matrix(n-r,n-r,A),1),2):

\ \quad od:

\ print(r,eval(A)):

\ end proc:with(LinearAlgebra):
}

\bigskip

It can be called with the syntax, for example,

\bigskip

\centerline{\tt permanent2(8);}


\begin{thebibliography}{99}

\bibitem {OEIS}N. J. A. Sloane, The On-Line Encyclopedia of Integer
Sequences, \url{https://oeis.org}, 2016.

\bibitem {koshy}T. Koshy, {\it Fibonacci and Lucas Numbers with
Applications}, Wiley-Interscience, New York, 2001.

\bibitem {koshy1}T. Koshy, Fibonacci, Lucas, and Pell numbers, and
Pascal's triangle, {\it Math. Spectrum} {\bf43} (2011), 125--132.

\bibitem {horadam}A. F. Horadam, Jacobsthal and Pell curves, {\it Fibonacci
Quart.} {\bf26} (1988), 79--83.

\bibitem {Konig1}D. K\"{o}nig, Vonalrendszerek \'{e}s determin\'{a}sok,
{\it Math. Term\'{e}sz. \'{E}rt.} {\bf33} (1915), 221--229.

\bibitem {Konig2}D. K\"{o}nig, \"{U}ber Graphen und ihre Anwendungen,
{\it Math. Annalen} {\bf77} (1916), 453--465.

\bibitem {Asratian}A. S. Asratian, T. M. J. Denley, and R. H\"{a}ggkvist,
{\it Bipartite Graphs and their Applications}, Cambridge University
Press, 1998.

\bibitem {minc}H. Minc, {\it Permanents}, Encyclopedia of Mathematics
and its Applications, Addison-Wesley, 1978.

\bibitem {Wheland}G. W. Wheland, {\it The Theory of Resonant and its
Application to Organic Chemistry}, Wiley, 1953.

\bibitem {brualdi}R. A. Brualdi and P. M. Gibson, Convex polyhedra of
doubly stochastic matrices I: Applications of the permanent function,
{\it J. Combin.  Theory A} {\bf22} (1977), 194--230.

\bibitem {harary}F. Harary, Determinants, permanents and bipartite graphs,
{\it Math. Mag.} {\bf42} (1969), 146--148.

\bibitem {marcus}M. Marcus and H. Minc, Permanents, {\it
Amer. Math. Monthly} {\bf72} (1965), 577--591.

\bibitem {lee1}G. Y. Lee, S. G. Lee, and H. G. Shin, On the $k$-generalized
Fibonacci matrix $Q_{k}$, {\it Lin. Alg. Appl.} {\bf251} (1997), 73--88.

\bibitem {lee2}G. Y. Lee, $k$-Lucas numbers and associated bipartite graphs,
{\it Lin. Alg. Appl.} {\bf320} (2000), 51--61.

\bibitem {Shiu}W. C. Shiu and Peter C. B. Lam, More on the generalized
Fibonacci numbers and associated bipartite graphs, {\it Int. Math. J.}
{\bf3} (2003), 5--9.

\bibitem {kilic2}E. K\i l\i\c{c} and D. Tas\c{c}\i, On families of
bipartite graphs associated with sums of Fibonacci and Lucas numbers,
{\it Ars Combin.} {\bf89} (2008), 31--40.

\bibitem {lee3}G. Y. Lee and S. G. Lee, A note on generalized Fibonacci
numbers, {\it Fibonacci Quart.} {\bf33} (1995), 273--278.

\bibitem {kilic}E. K\i l\i\c{c} and D. Ta\c{s}\c{c}\i, On the permanents
of some tridiagonal matrices with applications to the Fibonacci and
Lucas numbers, {\it Rocky Mt. J. Math.} {\bf37} (2007), 1953--1969.

\bibitem {oteles}M. Akbulak and A. \"{O}tele\c{s}, On the number of
1-factors of bipartite graphs, {\it Math. Sci. Lett.} {\bf2} (2013), 1--7.

\bibitem {oteles2}A. \"{O}tele\c{s}, On the number of perfect matchings
for some certain types of bipartite graphs, {\it Filomat} {\bf31}
(2017), 4809--4818.

\bibitem {sahin}K. Kaygisiz and A. Sahin, Determinants and permanents of
Hessenberg matrices and generalized Lucas polynomials, {\it Bull. Iranian
Math.  Soc.} {\bf39} (2013), 1065--1078.

\bibitem {yilmazz}F. Y\i lmaz and D. Bozkurt, The adjacency matrix
of one type of directed graph and the Jacobsthal numbers and their
determinantal representation, {\it J. Appl. Math.} {\bf2012} (2012),
\href{http://dx.doi.org/10.1155/2012/423163}{Article ID 423163}.

\bibitem {yilmaz}F. Y\i lmaz and D. Bozkurt, Some properties of Padovan
sequence by matrix methods, {\it Ars Combin.} {\bf104} (2012), 149--160.

\bibitem {fonseca}C. M. da Fonseca, T. Sogabe, and F. Y\i lmaz, Lower
k-Hessenberg matrices and $k$-Fibonacci, Fibonacci-$p$ and Pell $(p,i)$
number, {\it Gen. Math. Notes} {\bf31} (2015), 10--17.

\bibitem {kilic3}E. K\i l\i\c{c} and D. Tas\c{c}\i, On families of
bipartite graphs associated with sums of generalized order-$k$ Fibonacci
and Lucas numbers, {\it Ars Combin.} {\bf94} (2008), 13--23.

\bibitem {kilic4}E. K\i l\i\c{c} and A. P. Stakhov, On the Fibonacci and
Lucas p-numbers, their sums, families of bipartite graphs and permanents
of certain matrices, {\it Chaos Solitons Fractals} {\bf40} (2009), 10--21.

\bibitem {Vasco}P. Vasco, P. Catarino, H. Campos, A. P. Aires, and
A. Borges, $k$-Pell, $k$-Pell-Lucas and modified $k$-Pell numbers: Some
identities and norms of Hankel matrices, {\it Int. J. Math. Anal.} {\bf9}
(2015), 31--37.
\end{thebibliography}



	\bigskip \hrule \bigskip

	\noindent 2010 {\it Mathematics Subject Classification}: Primary
	05C50; Secondary 15A15, 11B83.

	\noindent \emph{Keywords: } Bipartite graph, permanent, Hessenberg
	matrix, Jacobsthal number.

	\bigskip \hrule \bigskip

	\noindent (Concerned with sequences 
\seqnum{A000045},
\seqnum{A000129}, and
\seqnum{A001045}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 1 2017;
revised versions received  November 6 2017; 
December 25 2018; February 26 2018; 
March 5 2018.
Published in {\it Journal of Integer Sequences}, March 6 2018.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


.
