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