\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
Some Identities For Palindromic \\
\vskip .1in
Compositions
}
\vskip 1cm
\large
Yu-hong Guo\footnote{This work was supported by the National Natural Science Foundation of China (Grant No.\ 11461020).}\\
School of Mathematics and Statistics\\
Hexi University\\
Zhangye, Gansu, 734000\\
P. R. China \\
\href{mailto:gyh7001@163.com}{\tt gyh7001@163.com}
\end{center}
\vskip .2 in
\begin{abstract}
This paper considers self-inverse or palindromic compositions of
positive integers into parts $\leq 3$. First we obtain two classes of
such compositions that are enumerated by the Fibonacci numbers. Then
we provide combinatorial identities between palindromic compositions
and compositions into $1$'s and $2$'s, compositions into odd parts,
and compositions into parts greater than $1$.
\end{abstract}
\section{Introduction}
A composition of a positive integer $n$ is a representation of $n$ as a sequence of positive integers called parts which sum to $n$. For example,
the compositions of $4$ are
$$(4), ~(3,1), ~(1,3), ~(2,2), ~(2,1,1), ~(1,2,1),
~(1,1,2), ~(1,1,1,1).$$
A palindromic or self-inverse composition of $n$ is one that remains unchanged when the order of its parts is reversed. For example, there are four palindromic compositions of $4$, namely, $(4), (1,2,1), (2,2), (1,1,1,1).$
It is well known that there are $2^{n-1}$ unrestricted compositions of $n$ \cite{G1,G2,PA,RP}. A composition may be represented graphically by means of the MacMahon \emph{zig-zag graph} \cite{PA}. It is similar to the partition Ferrers graph except that the first dot of each part is aligned with the last part of its predecessor. For instance the zig-zag graph of the composition $(6,3,1,2,2)$ is shown in Figure 1.
\vskip 8pt
\begin{center}
\scriptsize \begin{tabular}{cccccccccc}
$\bullet$ & $\bullet$ & $\bullet$ & $\bullet$ & $\bullet$ & $\bullet$ & & & & \\[.8mm]
& & & & & $\bullet$ & $\bullet$ & $\bullet$ & &\\[.8mm]
& & & & & & & $\bullet$ & &\\[.8mm]
& & & & & & & $\bullet$ & $\bullet$ &\\[.8mm]
& & & & & & & &$\bullet$ & $\bullet$
\end{tabular}
\medskip
{\small Figure 1. zig-zag graph}
\end{center}
The conjugate of a composition is obtained by reading its graph by
columns from left to right. We see that
the figure demonstrates that the conjugate of the
composition $(6,3,1,2,2)$ is $(1,1,1,1,1,2,1,3,2,1)$.
Munagi \cite{A} presented five methods to obtain the conjugate of a composition, including the zig-zag graph. He also carried out a classification of the set of all compositions into certain classes based on some primary criteria.
We recall essential terms and definitions for a composition of $n$ into $k$ parts, say $c=(c_{1},c_{2},\ldots,c_{k})$. The conjugate of $c$ is usually denoted by $c'$, while the inverse of $c$, denoted by $\overline{c}$, is defined by $\overline{c}=(c_{k},c_{k-1},\ldots,c_{1})$. Thus $c$ is self-inverse or palindromic if $c=\overline{c}$.
In 1975, Hoggatt and Bicknell studied standard compositions having parts of size $\leq3$, and found the following relation.
\begin{theorem}$\cite{V}$
Let $C_{3}(n)$ be the number of compositions of a positive integer $n$ using only the parts $1,2$ and $3$. Then
\[
C_{3}(n)=T_{n+1},
\]
where $T_{n}$ is the $n$th Tribonacci number, where $T_{1}=1, T_{2}=1, T_{3}=2$, and $T_{n}=T_{n-1}+T_{n-2}+T_{n-3},\, n>3$.
\end{theorem}
Hoggatt and Bicknell also determined that
the generating function for the number of palindromic compositions of
$n$ with $1,2$ and $3$ is
$$\frac{1+x+x^2+x^3}{1-x^2-x^4-x^6};$$ the sequence of coefficients
consists of two copies of the modified Tribonacci sequence interleaved:
$1,1,2,2,3,3,6,6,11,11,20,20,\ldots.$
In this paper, we consider palindromic compositions of positive
integers when only parts of size $\leq 3$ are allowed in {\it both\/} a
composition and its conjugate. For example, $c=(1,3,1)$ is a relevant
composition, since $c' =(2,1,2)$ and the parts of both compositions do
not exceed 3; but $(1,1,1,1,1)$ is forbidden because the conjugate
$(5)$ contains a part greater than 3. In Section~\ref{mainre} we
establish some properties of palindromic compositions. We also obtain
two combinatorial relations between the number of palindromic
compositions and the Fibonacci numbers. Consequently, we give several
identities between these palindromic compositions of $n$ and
compositions of $n$ into $1$'s and $2$'s, compositions of $n$ into
odd parts, and compositions of $n$ into parts greater than $1$.
\section{Main results}\label{mainre}
We first obtain two fundamental recurrence relations for compositions of odd and even weights separately.
Let $P_{3}(N)$ be the number of palindromic compositions $c$ of $N$ into parts $\leq 3$ such that the parts $c'$ also consists of parts $\leq 3$.
\begin{theorem}\label{th1} Let $n$ be an integer. Then
\[\label{pc1}
P_{3}(2n+1)=P_{3}(2n-1)+P_{3}(2n-3),\, n>2,
\]
with $P_{3}(1)=1, ~~P_{3}(3)=2,~~P_{3}(5)=2$.
\end{theorem}
\begin{proof}
We give a combinatorial proof. If $c$ is any palindromic composition,
then it is clear that $c'$ is also palindromic. Because $c$ has a first
part $1$ if and only $c'$ has a first part greater than $1$, it will
suffice to prove the recurrence for only compositions with first part
$1$. We split the relevant palindromic compositions $c$ of $2n+1$ into
two classes as follows:
\medskip
\noindent $(A)$:~~the first or last part of $c$ is 1;
\medskip
\noindent $(B)$:~~the first two parts, or the last two parts, of $c$, are $``1,1"$.
\medskip
In class $(A)$ we delete the first and last $1$'s from $c$ to get a composition $\beta$. Then we derive the conjugate $\beta'$ which is a relevant palindromic composition of $2n-1$ with first part $1$.
In class $(B)$, we delete the first and last two copies of 1 from $c$ to obtain a composition $\gamma$. The conjugate $\gamma'$ then gives a relevant palindromic composition of $2n-3$ with first part $1$.
Both transformations are clearly reversible.
For example, the only relevant composition of $1$ is $(1)$, for $2n+1=3$ the relevant compositions are $(1,1,1)$ and $(3)$, and for $2n+1=5$ they are $(1,3,1)$ and $(2,1,2)$.
\end{proof}
\bigskip
Similarly, we also obtain the following recurrence relation for the number of palindromic compositions of even integers.
\begin{theorem}\label{th2}
\[
P_{3}(2n)=P_{3}(2n-2)+P_{3}(2n-4), ~n>2,
\]
with $P_{3}(2)=2, ~~P_{3}(4)=2$.
\end{theorem}
The proof of Theorem \ref{th2} is similar to the proof of Theorem \ref{th1}, so we omit the details.
The following table gives some values of $P_{3}(N)$:
\begin{table}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$N$& 1 & 2 & 3 & 4 & 5 & 6 & 7& 8 & 9& 10 & 11 &12 & 13 &14 & 15& 16 &17\\
\hline
$P_{3}(N)$ & 1 & 2 & 2 & 2& 2 & 4& 4& 6& 6 &10 &10 & 16 &16 &26 &26 &42 &42\\
\hline
\end{tabular}
\caption{The number of palindromic compositions of $N$ with parts $\leq 3$}\label{tab1}
\end{center}
\end{table}
We find that $P_{3}(N)$ forms a sequence of twice the Fibonacci numbers repeated, for all $N>1$. The sequence $P_{3}(2n+1)$ appears as $A055389$, except for $n=0$, in Sloane's On-Line Encyclopedia of Integer Sequences \cite{NJ}. Note that if the Fibonacci sequence is shifted so that $F_{0}=1$, then $A055389$ becomes the sequence of twice the Fibonacci numbers. On the other hand $P_{3}(2n)$ agrees at once with the sequence of twice the Fibonacci numbers.
Consequently we obtain the following corollaries.
\begin{corollary}\label{co1}
\[\label{pc2}
P_{3}(2n+1)=2F_{n}, n>0,
\]
where $F_n$ is the $n^{th}$ Fibonacci number with $F_1=F_2=1, and ~ F_n=F_{n-1}+F_{n-2}.$
\end{corollary}
\begin{corollary}\label{co2}
\[
P_{3}(2n)=2F_{n}, n>0.
\]
\end{corollary}
\begin{corollary}\label{co3}
\[
P_{3}(2n)=P_{3}(2n+1), n>0.
\]
\end{corollary}
We also give the following generating functions:
\begin{corollary}\label{co4}
\begin{eqnarray*}
\sum_{n=0}P_{3}(2n+1)x^n&=&\frac{1+x+x^2}{1-x-x^2}.\\
\sum_{n=1}P_{3}(2n)x^n&=&\frac{2x}{1-x-x^2}.\\
\sum_{n=2}P_{3}(n)x^n&=&\frac{2x^2(x+1)}{1-x^2-x^4}.
\end{eqnarray*}
\end{corollary}
It is well-known that the number of compositions of a positive integer $n$ into odd parts is $F_{n}$, the number of compositions of $n$ into parts of size $1$ and $2$ is equal to $F_{n+1}$ and the number of compositions of $n$ into parts greater than $1$ is $F_{n-1}$. Consequently, we present the following identities for compositions of odd integers in line with Corollary \ref{co1}.
\begin{theorem}\label{thmxy}
The number of compositions $\alpha$ of $N$ with first part 1 such that the parts of $\alpha$ and $\alpha'$ are $\leq 3$ is equal to the number of compositions of $N$ into odd parts.
\end{theorem}
\begin{proof} We give a bijective proof.
Denote the enumerated sets of compositions by $CC(N)_1$ and $\{C_{\rm odd}(N)\}$ respectively.
Let $c\in CC(N)_1$ have the first part equal to 1. Then $c$ may contain at most two initial 1's.
We define a bijection $\Upsilon: CC(N)_1\rightarrow \{C_{\rm odd}(N)\}$ below.
Thus if $c$ starts with one 1, then $c\mapsto \Upsilon(c)\in \{C_{\rm odd}(N)\} $; otherwise the first part of the conjugate $c'$ is 3 and we have $c\mapsto \Upsilon(c')\in \{C_{\rm odd}(N)\}$.
Correspondingly if $\lambda\in \{C_{\rm odd}(N)\}$, then $\lambda\mapsto\Upsilon^{-1}(\lambda)\in CC(N)_1$ or $\lambda\mapsto\Upsilon^{-1}(\lambda)$ with $\Upsilon^{-1}(\lambda)'\in CC(N)_1$.
We now describe the function $\Upsilon: CC(N)_1\rightarrow C_{\rm odd}(N)$. Let $c\in CC(N)_1$.
Then if $2\notin c$, we set $\Upsilon(c)=c\in \{C_{\rm odd}(N)\}$.
Otherwise let $\gamma$ be the composition obtained from $c$ by replacing every instance of the string ``1,2" by ``1,1,1". Then replace each maximal string of the form $1,2,2,\dots$ or $3,2,2,\dots$ in $\gamma$ by the sum of its parts. Set the resulting composition equal to $\Upsilon(c)$. Clearly $\Upsilon(c)$ belongs to $\{C_{\rm odd}(N)\}$ and has first part 1.
Conversely we obtain $\Upsilon^{-1}$ using the following algorithm.
Consider any $\lambda\in \{C_{\rm odd}(N)\}$.
\medskip
\noindent (i) Replace every string of $r\geq 3$ ones by $1,2,1,2,\ldots$ from left to right, to produce a composition $\delta$ which has at most two 1's immediately before an odd part.
\medskip
\noindent (ii) Let $h>1$ be an odd part of $\delta$. If the string $``1,1,h"$ occurs, then replace $h$ with its composition of the form $``1,2,\ldots,2"$, otherwise replace $h$ with its composition of the form $3,2,\ldots,2$, to obtain a composition $\beta$.
\medskip
\noindent (iii) Lastly, replace every occurrence of the string $``1,1,1"$ by $``1,2"$ to obtain $\Upsilon^{-1}(\lambda)\in CC(N)_1$.
(Note that this step ensures that the conjugate of $\Upsilon^{-1}(\lambda)$ has parts $\leq 3$). Equivalently, apply steps (i) and (ii) to $\beta$ until we obtain a relevant palindromic composition of $N$.
\medskip
\noindent This shows that $\Upsilon$ is a bijection.
\end{proof}
\medskip
We give the following example to illustrate the bijection $\Upsilon$ in the proof of Theorem \ref{thmxy}.
\begin{example}
If $N=10$, then $\Upsilon$ maps $(1,2,2,3,2),(1,3,2,1,2,1), (1,1,3,2,1,2)\in CC(10)_1$ to $(1,1,3,5),(1,5,1,1,1,1),(3,1,1,1,3,1)\in \{C_{\rm odd}(10)\}$ respectively, as follows:
\begin{eqnarray*}
&&(1,2,2,3,2)\longrightarrow (1,1,1,2,3,2)\longrightarrow (1,1,3,5),\\
&&(1,3,2,1,2,1)\longrightarrow (1,3,2,1,1,1,1)\longrightarrow (1,5,1,1,1,1),\\
&&(1,1,3,2,1,2)\longrightarrow (3,1,2,3,1)\longrightarrow (3,1,1,1,3,1).
\end{eqnarray*}
Similarly $\Upsilon$ maps $(1,1,3,3,2,1) \in CC(11)_1$ to $(3,1,1,1,1,1,3)\in \{C_{\rm odd}(11)\}$ as follows:
$$(1,1,3,3,2,1)\longrightarrow (3,1,2,1,2,2)\longrightarrow (3,1,1,1,1,1,1,2)\longrightarrow (3,1,1,1,1,1,3);$$
and conversely,
\begin{eqnarray*}
&&(3,1,1,1,1,1,3)\longrightarrow(3,1,2,1,1,3)\longrightarrow(3,1,2,1,1,1,2)\longrightarrow(3,1,2,1,2,2)\\
&&\longrightarrow(1,1,3,3,2,1).
\end{eqnarray*}
\end{example}
We are now ready to prove the following important combinatorial identity.
\begin{theorem}\label{th3}
Let $C_{\rm odd}(N)$ be the number of compositions of $n$ into odd parts. Then
\begin{equation}\label{pc5}
P_{3}(2n+1)=2C_{\rm odd}(n), ~~~n>0.
\end{equation}
\end{theorem}
\begin{proof} First we show that there is a bijection between compositions enumerated by $P_3(2n+1)$ and compositions $\alpha$ of $n$ such that the parts of $\alpha$ and $\alpha'$ are $\leq 3$. Denote the the enumerated sets by $\{P_3(2n+1)\}$ and $CC(n)$ respectively.
Let $c=(c_1,\ldots,c_{i-1},c_i,c_{i-1},\ldots,c_1)\in \{P_3(2n+1)\}$. Then $c_i=1$ or $c_i=3$. Define a function $\Phi: \{P_3(2n+1)\}\rightarrow CC(n)$ as follows.
If $c_i=1$, then $\Phi(c)=(c_1,\ldots,c_{i-1})\in CC(n)$, and if $c_i=3$, then $\Phi(c)=(c_1,\ldots,c_{i-1},1)\in CC(n)$. Due to the inherited parts, we see that $\Phi(c)$ as well as $\Phi(c)'$ are compositions of $n$ with parts $\leq 3$.
Conversely, let $\alpha=(\alpha_1,\ldots,\alpha_k)\in CC(n)$. Then we obtain that $\Phi^{-1}(\alpha)$ is given by $c=(\alpha_1,\ldots,\alpha_k,1,\alpha_{k},\ldots,\alpha_{1})$ if $\alpha_k>1$ or by $c=(\alpha_1,\ldots,\alpha_{k-1},3,\alpha_{k-1},\ldots,\alpha_{1})$ if $\alpha_k=1$. Hence $\Phi$ is a bijection.
Note that $\Phi$ maps a composition with first part $1$ to a composition with first part 1 and vice-versa. So by Theorem \ref{thmxy} there is a bijection between the set of compositions in $\{P_3(2n+1)\}$ with first part $1$ and $\{C_{\rm odd}(n)\}$.
Since the conjugate of a composition with first part $>1$ has first part 1, it also follows that the set of compositions in $\{P_3(2n+1)\}$ with first part $>1$ is in bijection with $\{C_{\rm odd}(n)\}$. In other words, we have proved that $|\{P_3(2n+1)\}|=2|\{C_{\rm odd}(n)\}|$ which is (\ref{pc5}).
This completes the proof.
\end{proof}
We cite an example to illustrate Theorem \ref{th3}.
\begin{example}
Let $n=6$, the corresponding relations between the relevant palindromic compositions of $13$ and compositions of $6$ into odd parts are as follows.
\begin{eqnarray*}
&&(1,2,3,1,3,2,1)\longleftrightarrow(1,1,1,3)\longleftrightarrow (2,2,1,3,1,2,2),\\
&&(1,3,2,1,2,3,1)\longleftrightarrow (1,5)\longleftrightarrow(2,1,2,3,2,1,2),\\
&&(1,3,1,3,1,3,1)\longleftrightarrow (1,3,1,1)\longleftrightarrow(2,1,3,1,3,1,2),\\
&&(1,2,2,3,2,2,1)\longleftrightarrow (1,1,3,1)\longleftrightarrow(2,2,2,1,2,2,2),\\
&&(1,2,1,2,1,2,1,2,1)\longleftrightarrow (1,1,1,1,1,1)\longleftrightarrow(2,3,3,3,2), \\
&&(1,1,3,3,3,1,1)\longleftrightarrow (3,1,1,1)\longleftrightarrow(3,1,2,1,2,1,3),\\
&&(1,1,2,1,3,1,2,1,1)\longleftrightarrow(3,3)\longleftrightarrow(3,3,1,3,3),\\
&&(1,1,2,2,1,2,2,1,1)\longleftrightarrow(5,1)\longleftrightarrow(3,2,3,2,3).
\end{eqnarray*}
\end{example}
\medskip
\begin{theorem}\label{th4}
Let $C_{2}(N)$ be the number of compositions of $N$ into parts of size $1,2$. Then
\begin{equation}\label{pc6}
P_{3}(2n+1)=2C_{2}(n-1), ~~~n>1.
\end{equation}
\end{theorem}
\begin{proof} Given a composition $\alpha$ enumerated by $P_{3}(2n+1)$ with first and last parts equal to 1, we first use Theorem \ref{th3} to obtain a composition $\beta$ of $n$ into odd parts. Next, we replace each odd part $h>1$ by $1,2,\ldots,2$ to obtain a composition $\gamma$ of $n$ into $1$'s and $2$'s with first part $1$. Finally, a composition enumerated by $C_{2}(n-1)$ is obtained by deleting the first part $1$.
Obviously, this correspondence is one-to-one. This completes the proof.
\end{proof}
\begin{theorem}\label{th5}
Let $C_{>1}(N)$ be the number of compositions of $N$ into parts greater than $1$. Then
\begin{equation}\label{pc7}
P_{3}^{'}(2n+1)=2C_{>1}(n+1), ~~~n\geq1.
\end{equation}
\end{theorem}
\begin{proof} Given a composition $\alpha$ enumerated by $P_{3}(2n+1)$ with first and last parts equal to 1, we use Theorem \ref{th3} to obtain a composition $\beta$ of $n$ into odd parts. Then we replace each odd part $h>1$ by $1,2,\ldots,2$ to obtain a composition $\gamma$ of $n$ into $1$'s and $2$'s with first part $1$.
Next we append $1$ to the right end of $\gamma$ to obtain a composition $\lambda$ of $n+1$ into $1$'s and $2$'s having first and last parts equal to 1. Finally we take the conjugate $\lambda^{'}$ which is a composition of $n+1$ into parts greater than $1$.
This correspondence is clearly one-to-one. The proof is complete.
\end{proof}
We cite an example to illustrate Theorem \ref{th5}.
\begin{example}
Let $n=6$, the corresponding relations between the relevant palindromic compositions of $13$ and compositions of $7$ into parts greater than $1$ are as follows.
\begin{eqnarray*}
&&(1,2,3,1,3,2,1)\longleftrightarrow(5,2)\longleftrightarrow (2,2,1,3,1,2,2), \\
&&(1,3,2,1,2,3,1)\longleftrightarrow (3,2,2)\longleftrightarrow(2,1,2,3,2,1,2),\\
&&(1,3,1,3,1,3,1)\longleftrightarrow (3,4)\longleftrightarrow(2,1,3,1,3,1,2), \\
&&(1,2,2,3,2,2,1)\longleftrightarrow (4,3)\longleftrightarrow(2,2,2,1,2,2,2),\\
&&(1,2,1,2,1,2,1,2,1)\longleftrightarrow (7)\longleftrightarrow(2,3,3,3,2), \\
&&(1,1,3,3,3,1,1)\longleftrightarrow (2,5)\longleftrightarrow(3,1,2,1,2,1,3),\\
&&(1,1,2,1,3,1,2,1,1)\longleftrightarrow(2,3,2)\longleftrightarrow(3,3,1,3,3),\\
&&(1,1,2,2,1,2,2,1,1)\longleftrightarrow(2,2,3)\longleftrightarrow(3,2,3,2,3).
\end{eqnarray*}
\end{example}
We state analogous identities for the number $P_{3}(2n)$ of palindromic compositions of even integers $2n$ when only parts of size $\leq 3$ are allowed in both a composition and its conjugate.
\begin{theorem}\label{th6}
\begin{equation}\label{pc8}
P_{3}(2n)=2C_{\rm odd}(n), ~~~n>0.
\end{equation}
\end{theorem}
\begin{theorem}\label{th7}
\begin{equation}\label{pc9}
P_{3}(2n)=2C_{2}(n-1), ~~~n>1.
\end{equation}
\end{theorem}
\begin{theorem}\label{th8}
\begin{equation}\label{pc10}
P_{3}(2n)=2C_{>1}(n+1), ~~~n\geq 1.
\end{equation}
\end{theorem}
The proofs of Theorems \ref{th6} to \ref{th8} are similar to the proofs of the foregoing identities for $P_{3}(2n+1)$. So we omit the details. We only cite an example below to illustrate Theorem \ref{th8}.
\begin{example}
Let $n=6$, the corresponding relations between the relevant palindromic compositions of $12$ and compositions of $7$ into parts greater than $1$ are as follows.
\begin{eqnarray*}
&&(1,2,3,3,2,1)\longleftrightarrow(5,2)\longleftrightarrow (2,2,1,2,1,2,2), \\
&&(1,3,2,2,3,1)\longleftrightarrow (3,2,2)\longleftrightarrow(2,1,2,2,2,1,2),\\
&&(1,3,1,2,1,3,1)\longleftrightarrow (3,4)\longleftrightarrow(2,1,3,3,1,2), \\
&&(1,2,2,2,2,2,1)\longleftrightarrow (4,3)\longleftrightarrow(2,2,2,2,2,2),\\
&&(1,2,1,2,2,1,2,1)\longleftrightarrow (7)\longleftrightarrow(2,3,2,3,2), \\
&&(1,1,3,2,3,1,1)\longleftrightarrow (2,5)\longleftrightarrow(3,1,2,2,1,3),\\
&&(1,1,2,1,2,1,2,1,1)\longleftrightarrow(2,3,2)\longleftrightarrow(3,3,3,3),\\
&&(1,1,2,2,2,2,1,1)\longleftrightarrow(2,2,3)\longleftrightarrow(3,2,2,2,3).
\end{eqnarray*}
\end{example}
\section{Acknowledgments}
The author would like to thank the referees for their valuable comments
and corrections which have improved the quality of this paper. Special
thanks also to Professor Augustine Munagi for his revision of this
paper.
\begin{thebibliography}{9}
\bibitem{G2} G. E. Andrews,
{\it The Theory of Partitions}, Cambridge University Press, 1984.
\bibitem{G1} G. E. Andrews and K. Eriksson, {\it Integer Partitions},
Cambridge University Press, 2004.
\bibitem{PC} P. Chinn and S. Heubach, Integer sequences related to
compositions without 2's, \emph{J. Integer Sequences} {\bf 6}
(2003), \href{https://cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.html}{Article 03.2.3}.
\bibitem{V} V. E. Hoggatt, Jr., and M. Bicknell, Palindromic
compositions, \emph{Fibonacci Q.} {\bf 13} (1975), 350--356.
\bibitem{PA} P. A. MacMahon, {\it Combinatory Analysis},
Vol.~I, Cambridge University Press, 1995.
\bibitem{A} A. O. Munagi, Primary classes of compositions of numbers,
\emph{Ann. Math. Inform.}, {\bf 41} (2013), 193--204.
\bibitem{NJ} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,
\url{https://oeis.org}.
\bibitem{RP} R. P. Stanley, {\it Enumerative Combinatorics},
Vol.~I, Cambridge University Press, 1997.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A17, 05A19.
\noindent \emph{Keywords: }
palindromic composition, Fibonacci number, identity, combinatorial proof.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A055389}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received October 11 2017;
revised versions received October 14 2017; October 24 2017;
May 12 2018; June 9 2018; June 11 2018.
Published in {\it Journal of Integer Sequences}, August 22 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}