\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

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

\newcommand{\seqnum}[1]{\href{https://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 The Number of Designated Parts\\
\vskip .05in
in Compositions with Restricted Parts}
\vskip 1cm
\large
Mengmeng Liu and Andrew Yezhou Wang\\
School of Mathematical Sciences \\
University of Electronic Science and Technology of China\\
Chengdu 611731\\
P. R. China\\
\href{mailto:dreamofliu@outlook.com}{\tt dreamofliu@outlook.com}\\
\href{mailto:yzwang@uestc.edu.cn}{\tt yzwang@uestc.edu.cn}
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, we study the number of designated parts in three types of compositions with restricted parts. We find new combinatorial interpretations of some known sequences, and establish two identities concerning these known sequences.
\end{abstract}

\section{Introduction}

A \emph{composition} of an integer $n$ is a way of expressing $n$ as an ordered sum of integers. More precisely, a composition of $n$ is a sequence $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_k)$ of positive integers satisfying $\alpha_1+\alpha_2+\cdots+\alpha_k=n$. The summands $\alpha_i$ are called the \emph{parts} of $\alpha$, and the number of parts is called the \emph{length} of $\alpha$. For example, there are eight compositions of $4$; namely,
\begin{align*}
4,3+1,1+3,2+2,2+1+1,1+2+1,1+1+2,1+1+1+1.
\end{align*}
If $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_k)$ is a composition of $n$ with $k$ parts, then we define a $(k-1)$-subset $S_\alpha$ of $[n-1]:=\{1,2,\ldots,n-1\}$ by
\begin{align*}
S_\alpha=\{\alpha_1,\alpha_1+\alpha_2,\ldots,\alpha_1+\alpha_2+\cdots+\alpha_{k-1}\}.
\end{align*}
The correspondence $\alpha\rightarrow S_\alpha$ gives a bijection from all compositions of $n$ with $k$ parts to all $(k-1)$-subsets of $[n-1]$. Thus, there are ${n-1}\choose {k-1}$ compositions of $n$ with $k$ parts and $2^{n-1}$ compositions of $n$. Furthermore, a subset $S\subseteq[n-1]$ can be encoded by a binary sequence of length $n-1$ whose $i$th component is $1$ if $i\in S$ and $0$ otherwise. Therefore, we have a bijection between compositions of $n$ and binary sequences of length $n-1$.

In this paper, we consider the following three types of compositions with restricted parts. Let $\mathcal{A}(n)$, $\mathcal{B}(n)$, and $\mathcal{C}(n)$ denote, respectively, the set of compositions of $n$ in which only the last part may be equal to $1$, compositions of $n$ into parts greater than $1$, and compositions of $n$ with only odd parts. There is a trivial bijection from the set $\mathcal{A}(n)$ to $\mathcal{B}(n+1)$. More precisely, given a composition $\alpha\in\mathcal{A}(n)$, increasing the last part of $\alpha$ by one, then we obtain a composition $\beta$ in $\mathcal{B}(n+1)$. We can uniquely recover $\alpha$ from $\beta$ by decreasing the last part of $\beta$ by one.

There is a known identity concerning the cardinality of $\mathcal{B}(n)$ and $\mathcal{C}(n)$.
\begin{theorem}\label{Euler1}
For $n\geq 1$, we have $|\mathcal{B}(n+1)|=|\mathcal{C}(n)|$.
\end{theorem}
Both numbers in Theorem \ref{Euler1} are equal to the $n$th Fibonacci number $F_n$, defined by $F_0=0$, $F_1=1$, and for $n\geq2$,
\[F_n=F_{n-1}+F_{n-2}.\]
See Cayley \cite{Cay76} and Stanley \cite[Exercise 1.35]{Stan12} for more details. Sills \cite{Sills13} provided a bijective proof of Theorem \ref{Euler1} relying on the binary sequence encoding of compositions. Recently, Li and Wang \cite{LW19} found a simple bijection defined directly on the parts to prove Theorem \ref{Euler1}.

In this paper, we study the number of designated parts among all compositions in $\mathcal{A}(n)$, $\mathcal{B}(n+1)$, and $\mathcal{C}(n)$ respectively. In Section \ref{s2}, we find a simple combinatorial interpretation of the sequence \seqnum{A102702} in the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{OEIS00}. The sequence \seqnum{A102702} was proposed in 2005 by Creighton Dement, stated as a floretion-generated sequence. But there are no further clues about the floretion definition.
In Section \ref{s3}, we give a new combinatorial object counted by the sequence \seqnum{A006367} and establish an identity relating the sequences \seqnum{A006367} and \seqnum{A010049}. In Section \ref{s4}, we present a relationship concerning the number of three types of designated parts in compositions.

\section{Compositions in which only the last part may be one}\label{s2}

In this section, we mainly focus on the number of parts not greater than $2$ among all compositions in $\mathcal{A}(n)$, denoted by $\overline{A}_n$.

It is easy to see that $\overline{A}_0=0$, $\overline{A}_1=1$, $\overline{A}_2=1$, and $\overline{A}_3=2$. We now present a recurrence relation for $\overline{A}_n$.
\begin{theorem}\label{recc}
For $n\geq 4$, we have
\begin{align}\label{crec}
\overline{A}_n=\overline{A}_{n-1}+\overline{A}_{n-2}+F_{n-4}.
\end{align}
\end{theorem}
\begin{proof}
Given a composition $\alpha$, let $\ell_{\leq 2}(\alpha)$ count the number of parts less than or equal to $2$ of $\alpha$. Then,
\begin{align*}
\overline{A}_n=\sum\limits_{\alpha\in\mathcal{A}(n)}\ell_{\leq2}(\alpha).
\end{align*}
Define $\mathcal{A}_1(n)$ and $\mathcal{A}_2(n)$ to be the subset of $\mathcal{A}(n)$ consisting of the compositions with the first part equal to $2$ and greater than $2$ respectively. It is clear that
\begin{align*}
\mathcal{A}(n)=\mathcal{A}_1(n)\cup\mathcal{A}_2(n)
\end{align*}
is a disjoint set theoretic partitioning of $\mathcal{A}(n)$.

For any composition $\alpha\in\mathcal{A}_1(n)$, deleting the first part of $\alpha$ produces a composition in $\mathcal{A}(n-2)$, which gives a bijection $\rho$ between $\mathcal{A}_1(n)$ and $\mathcal{A}(n-2)$ such that \[\ell_{\leq2}(\alpha)=\ell_{\leq2}(\rho(\alpha))+1.\]

Given a composition $\beta\in\mathcal{A}_2(n)$, we decrease the first part of $\beta$ by $1$ to obtain a composition in $\mathcal{A}(n-1)$, and vice versa. Hence, there is a bijection $\tau$ between $\mathcal{A}_2(n)$ and $\mathcal{A}(n-1)$. Moreover, $\ell_{\leq2}(\beta)=\ell_{\leq2}(\tau(\beta))$ if and only if the first part of $\beta$ is greater than $3$. If $\beta$ has its first part equal to $3$, then $\ell_{\leq2}(\beta)=\ell_{\leq2}(\tau(\beta))-1$. Similarly to the above bijection $\rho$, we know that such compositions correspond to those in $\mathcal{A}(n-3)$.

Recall that $|\mathcal{A}(n)|=F_n$ for $n\geq 0$. Therefore, we have
\begin{align*}
\sum\limits_{\alpha\in\mathcal{A}(n)}\ell_{\leq2}(\alpha)&=\sum\limits_{\alpha\in\mathcal{A}_1(n)}\ell_{\leq2}(\alpha)+
\sum\limits_{\alpha\in\mathcal{A}_2(n)}\ell_{\leq2}(\alpha)\\
&=\sum\limits_{\alpha\in\mathcal{A}(n-2)}(\ell_{\leq2}(\alpha)+1)+
\left(\sum\limits_{\alpha\in\mathcal{A}(n-1)}\ell_{\leq2}(\alpha)-\sum\limits_{\alpha\in\mathcal{A}(n-3)}1\right)\\
&=\sum\limits_{\alpha\in\mathcal{A}(n-2)}\ell_{\leq2}(\alpha)+F_{n-2}+
\sum\limits_{\alpha\in\mathcal{A}(n-1)}\ell_{\leq2}(\alpha)-F_{n-3}\\
&=\sum\limits_{\alpha\in\mathcal{A}(n-2)}\ell_{\leq2}(\alpha)+
\sum\limits_{\alpha\in\mathcal{A}(n-1)}\ell_{\leq2}(\alpha)+F_{n-4},
\end{align*}
which yields the desired result.
\end{proof}

We now establish the generating function of $\overline{A}_n$.
\begin{theorem}\label{gfoc}
The generating function of $\overline{A}_n$ is given by
\begin{align}\label{genc}
\overline{A}(x):=\sum\limits_{n\geq0}\overline{A}_nx^n=\frac{x-x^2-x^3+x^5}{(1-x-x^2)^2}.
\end{align}
\end{theorem}
\begin{proof}
To find $\overline{A}(x)$, multiply both sides of the recurrence relation \eqref{crec} by $x^n$ and sum over $n\geq 4$. Then try to relate these sums to the unknown generating function $\overline{A}(x)$. If we do this first to the left side of \eqref{crec}, we have
\begin{align*}
\sum\limits_{n\geq4}\overline{A}_nx^n=\overline{A}(x)-x-x^2-2x^3.
\end{align*}
We next deal with the right side of \eqref{crec}. The result is
\begin{align*}
\sum\limits_{n\geq4}\left(\overline{A}_{n-1}+\overline{A}_{n-2}+F_{n-4}\right)x^n
&=\sum\limits_{n\geq4}\overline{A}_{n-1}x^n+\sum\limits_{n\geq4}\overline{A}_{n-2}x^n
+\sum\limits_{n\geq4}F_{n-4}x^n\\
&=x\left(\overline{A}(x)-x-x^2\right)+x^2\left(\overline{A}(x)-x\right)+\frac{x^5}{1-x-x^2},
\end{align*}
wherein we have used the familiar generating function for the Fibonacci numbers
\begin{align}\label{recFibo}
\sum\limits_{n\geq0}F_nx^n=\frac{x}{1-x-x^2}.
\end{align}

If we equate the results of operating on the two sides of \eqref{crec}, we find that
\begin{align*}
\overline{A}(x)-x-x^2-2x^3=x\left(\overline{A}(x)-x-x^2\right)+x^2\left(\overline{A}(x)-x\right)+\frac{x^5}{1-x-x^2},
\end{align*}
which is trivial to solve for the unknown generating function $\overline{A}(x)$, in the form
\begin{align*}
\overline{A}(x)=\frac{x-x^2-x^3+x^5}{(1-x-x^2)^2}.
\end{align*}
The proof is complete.
\end{proof}

We now seek the relationship between the sequence $(\overline{A}_n)_{n\geq0}$ and the sequence $\left(a_n\right)_{n\geq0}$ in OEIS \cite[\seqnum{A102702}]{OEIS00}. It is routine to check that
\begin{align*}
\overline{A}(x)-x-x^2&=\frac{x-x^2-x^3+x^5}{(1-x-x^2)^2}-x-x^2\\
&=x^3\cdot\frac{2-x-2x^2-x^3}{(1-x-x^2)^2},
\end{align*}
where the second factor of the last identity above is the generating function of $a_n$. Therefore, $a_n$ is the total number of parts not greater than $2$ among all compositions of $n+3$ in which only the last part may be equal to $1$. This is a new and simple combinatorial interpretation of the sequence \seqnum{A102702}.

We next derive an explicit formula for $\overline{A}_n$ in terms of the Fibonacci numbers by expanding $\overline{A}(x)$ in a series.
\begin{theorem}
For $n\geq2$, we have
\begin{align}\label{formula}
\overline{A}_n=\frac{(3n-3)F_n-(4n-10)F_{n-1}}{5}.
\end{align}
\end{theorem}
\begin{proof}
It follows from \eqref{recFibo} that
\begin{align*}
\sum\limits_{n\geq0}F_{n+1}x^n=\frac{1}{1-x-x^2}.
\end{align*}
Therefore, the coefficient $P_n$ of $x^n$ in $1/(1-x-x^2)^2$ is
\begin{align*}
F_1F_{n+1}+F_2F_n+\cdots+F_{n+1}F_1.
\end{align*}
By induction on $n$ and using the fact $F_{n}=F_{n-1}+F_{n-2}$, it is easy to see that
\begin{align}\label{coeff}
P_n=F_1F_{n+1}+F_2F_n+\cdots+F_{n+1}F_1=\frac{(n+1)F_{n+2}+(2n+4)F_{n+1}}{5},
\end{align}
which can be found in \cite[Eq.\ (32.13), p.\ 375]{Kos01} or \cite[Nr.\ (98), p.\ 183]{Vaj89}. Combining \eqref{genc} and \eqref{coeff}, we conclude that for $n\geq 5$,
\begin{align*}
\overline{A}_n&=P_{n-1}-P_{n-2}-P_{n-3}+P_{n-5}\\
&=\frac{nF_{n+1}+(2n+2)F_{n}}{5}-\frac{(n-1)F_{n}+2nF_{n-1}}{5}\\
&\quad-\frac{(n-2)F_{n-1}+(2n-2)F_{n-2}}{5}+\frac{(n-4)F_{n-3}+(2n-6)F_{n-4}}{5}\\
&=\frac{(2n+3)F_{n}-(2n-2)F_{n-1}-(2n-2)F_{n-2}+(n-4)F_{n-3}+(2n-6)F_{n-4}}{5}\\
&=\frac{(2n+3)F_{n}-(2n-2)F_{n-1}-4F_{n-2}-(n-2)F_{n-3}}{5}\\
&=\frac{(2n+3)F_{n}-(3n-4)F_{n-1}+(n-6)F_{n-2}}{5}\\
&=\frac{(3n-3)F_{n}-(4n-10)F_{n-1}}{5}.
\end{align*}
One can readily check that $\overline{A}_n$ for each $n=2,3,4$ also satisfies the formula \eqref{formula}.
\end{proof}

As a consequence, we can express $a_n$ in OEIS \cite[\seqnum{A102702}]{OEIS00} as
\begin{align*}
a_n=\frac{(3n+6)F_{n+3}-(4n+2)F_{n+2}}{5}=\frac{(2n+10)F_{n+1}-(n-4)F_{n}}{5}
\end{align*}
for $n\geq0$.

To end this section, we consider the number of parts among all compositions in $\mathcal{A}(n)$, denoted by $A_n$. Obviously, $A_0=0$ and $A_1=1$. Applying arguments similar to those when dealing with $\overline{A}_n$, we can show that for $n\geq2$,
\begin{align*}
A_n=A_{n-1}+A_{n-2}+F_{n-2},
\end{align*}
which implies the generating function
\begin{align*}
A(x):=\sum\limits_{n\geq0}A_nx^n=\frac{x-x^2}{(1-x-x^2)^2}.
\end{align*}
Based on $A(x)$, we derive the following simple formula
\begin{align*}
A_n=\frac{(2n+3)F_n-nF_{n-1}}{5},n\geq1.
\end{align*}
The number $A_n$ appears in OEIS \cite[\seqnum{A010049}]{OEIS00}, which counts the total number of parts in all compositions of $n+1$ with no $1$'s.

\section{Compositions with no ones}\label{s3}
Let $B_n$ be the number of parts among all compositions in $\mathcal{B}(n+1)$. Since the trivial bijection between $\mathcal{A}(n)$ and $\mathcal{B}(n+1)$ preserves the length of compositions, we have $B_n=A_n$.

Define $\overline{B}_n$ to be the number of parts equal to $2$ among all compositions in $\mathcal{B}(n+1)$. It is clear that $\overline{B}_0=0$, $\overline{B}_1=1$, $\overline{B}_2=0$, and $\overline{B}_3=2$. Using the arguments similar to those in the proof of Theorem \ref{recc}, we obtain that for $n\geq4$,
\begin{align*}
\overline{B}_n=\overline{B}_{n-1}+\overline{B}_{n-2}+F_{n-4}.
\end{align*}
The sequence $(\overline{B}_n)_{n\geq0}$ satisfies the same recurrence relation as $(\overline{A}_n)_{n\geq0}$ but with different initial conditions.

Similarly, we can find that
\begin{align*}
\sum\limits_{n\geq0}\overline{B}_nx^n=\frac{x(1-x)^2}{(1-x-x^2)^2},
\end{align*}
and for $ n\geq1$,
\begin{align*}
\overline{B}_n=\frac{(3n+2)F_n-4nF_{n-1}}{5}.
\end{align*}

The number $\overline{B}_n$ relates to the sequence \seqnum{A006367} in OEIS \cite{OEIS00}, which is interpreted as the number of compositions of $n$ containing exactly one $1$. We now give a combinatorial proof of this equality.
\begin{theorem}
The number $\overline{B}_n$ equals the number of compositions of $n$ with exactly one $1$.
\end{theorem}
\begin{proof}
Assume that $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_l)\in\mathcal{B}(n+1)$ have $j$ parts equal to $2$, say
\[\alpha_{i_1}=\alpha_{i_2}=\cdots=\alpha_{i_j}=2,\]
where $1\leq i_1<i_2<\cdots<i_j\leq l$. For each $1\leq r\leq j$, define
\[\alpha^r=(\alpha_1,\alpha_2,\ldots,\alpha_{i_r}-1,\ldots,\alpha_l).\]
It is easy to see that $\alpha^1,\alpha^2,\ldots,\alpha^j$ are $j$ different compositions of $n$ with exactly one $1$.

Conversely, given a composition of $n$ containing only one $1$, we increase the unique part equal to $1$ by one to obtain a composition counted by $\overline{B}_n$.
\end{proof}

We have a new combinatorial interpretation of the sequence $(\overline{B}_n)_{n\geq0}$.
\begin{theorem}\label{thmno1}
The number $\overline{B}_n$ counts the number of parts in all compositions of $n+1$ with no $1$'s and the last part being $2$.
\end{theorem}
\begin{proof}
Let $\alpha\in\mathcal{B}(n+1)$ in which $i$ (for $i\geq 2$) occurs $c_i$ times as a part. Then we define the type of $\alpha$ to be the nonnegative sequence $(c_2,c_3,\ldots,c_{n+1})$. By the standard combinatorial analysis used to enumerate the permutations of a multiset, we know that there are
\[\frac{l!}{c_2!c_3!\cdots c_{n+1}!}\]
compositions in $\mathcal{B}(n+1)$ with length $l$ and type $(c_2,c_3,\ldots,c_{n+1})$. The part $2$ appears
\[\frac{l!}{c_2!c_3!\cdots c_{n+1}!}\cdot c_2=\frac{l!}{(c_2-1)!c_3!\cdots c_{n+1}!}\]
times totally in these compositions.

On the other hand, there are
\[\frac{(l-1)!}{(c_2-1)!c_3!\cdots c_{n+1}!}\]
compositions in $\mathcal{B}(n+1)$ with length $l$, the last part being $2$, and type $(c_2,c_3,\ldots,c_{n+1})$. The total number of parts in these compositions is
\[\frac{(l-1)!}{(c_2-1)!c_3!\cdots c_{n+1}!}\cdot l=\frac{l!}{(c_2-1)!c_3!\cdots c_{n+1}!}.\]

The above combinatorial analysis shows the desired equality.
\end{proof}

\begin{remark}
In fact, we can prove the following more general result. For fixed $k\geq 2$, the number of appearances of $k$ in all compositions of $n$ with no $1$'s is equal to the number of parts in all compositions of $n$ in which each part is at least $2$ and the last part is $k$.
\end{remark}

We now give a relationship between $B_n$ and $\overline{B}_n$.

\begin{theorem}
For $n\geq 1$, we have
\begin{align*}
\overline{B}_n=B_n-B_{n-1}.
\end{align*}
\end{theorem}
\begin{proof}
Let $\alpha\in\mathcal{B}(n+1)$ with the last part greater than $2$. Then we decrease the last part of $\alpha$ by one to produce a composition $\alpha^\prime$ in $\mathcal{B}(n)$. The map $\alpha\to\alpha^\prime$ defines a bijection from the subset of $\mathcal{B}(n+1)$ consisting of compositions with the last part greater than $2$ to $\mathcal{B}(n)$, which preserves the length.

Hence, the remaining compositions in $\mathcal{B}(n+1)$ have their last part equal to $2$. It follows from Theorem \ref{thmno1} that the total number of parts in such compositions is equal to $\overline{B}(n)$.
\end{proof}

\section{Compositions into odd parts}\label{s4}

Let $C_n$ be the number of parts among all compositions in $\mathcal{C}(n)$. By OEIS \cite[\seqnum{A029907}]{OEIS00}, we know that
\begin{itemize}
\item $C_0=0$, $C_1=1$, and $C_{n}=C_{n-1}+C_{n-2}+F_{n-1}$ for $n\geq2$.
\item for $n\geq1$,
\[C_n=\frac{(n+4)F_n+2nF_{n-1}}{5}.\]
\item the number $C_n$ equals the number of compositions of $n+1$ with exactly one even part.
\end{itemize}

Recently, Huang \cite{Huang18} found an identity concerning $C_n$ and $B_n$.
\begin{theorem}
For $n\geq 1$, we have
\begin{align*}
C_n=B_n+B_{n-1}.
\end{align*}
\end{theorem}
\begin{proof}
See \cite[Proposition 6.3]{Huang18} for a proof.
\end{proof}

Let $\overline{C}_n$ denote the number of $1$'s among all compositions in $\mathcal{C}(n)$. The numbers $\overline{C}(n)$ form the sequence \seqnum{A239342} in OEIS \cite{OEIS00}. Applying similar arguments used in Section \ref{s2}, we can obtain the recurrence relation and an explicit formula satisfied by $\overline{C}(n)$. More precisely, we have
\begin{itemize}
\item $\overline{C}_0=0$, $\overline{C}_1=1$, $\overline{C}_2=2$, $\overline{C}_3=3$, and
    $\overline{C}_n=\overline{C}_{n-1}+\overline{C}_{n-2}+F_{n-2}$ for $n\geq 4$.
\item for $n\geq 2$,
\[\overline{C}_n=\frac{(2n-2)F_n-(n-10)F_{n-1}}{5}.\]
\end{itemize}

Finally, we present an identity involving the number of designated parts in the compositions under study in this paper.
\begin{theorem}
The number of parts not greater than $2$ among all compositions in $\mathcal{A}(n)$ equals the difference between the number of parts of compositions in $\mathcal{B}(n+1)$ and the number of parts greater than $1$ among the compositions in $\mathcal{C}(n)$.
\end{theorem}
\begin{proof}
We first recall the bijection $\varphi$ introduced by Li and Wang \cite{LW19} between $\mathcal{B}(n+1)$ and $\mathcal{C}(n)$. Given a composition $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_l)$, define
\[\hat{\alpha}=(\alpha_1,\alpha_2,\ldots,\alpha_{l-1},\alpha_l-1).\]
It is clear that $\hat{\alpha}\in\mathcal{A}(n)$.

For each even part $2k$ of $\hat{\alpha}$, we split it into the pair of parts $1,2k-1$. Let $\varphi(\alpha)$ be the yielded composition. Clearly, $\varphi(\alpha)\in\mathcal{C}(n)$. Moreover, every odd part of $\varphi(\alpha)$ which is at least $3$ either appears as a part of $\hat{\alpha}$ or is produced by splitting an even part of $\hat{\alpha}$. Therefore, every odd part of $\varphi(\alpha)$ which is at least $3$ corresponds to a part of $\hat{\alpha}$ which is at least $3$.

Now we can conclude that the difference between the number of parts of compositions in $\mathcal{B}(n+1)$ and the number of parts greater than $1$ among the compositions in $\mathcal{C}(n)$ is equal to the number of parts not greater than $2$ among all compositions in $\mathcal{A}(n)$.
\end{proof}

\begin{remark}
The statement is equivalent to
\begin{align*}
\overline{A}_n=B_n-(C_n-\overline{C}_n),
\end{align*}
which can be easily proved by employing the formula of $\overline{A}_n$, $B_n$, $C_n$, and $\overline{C}_n$.
\end{remark}

\begin{thebibliography}{9}

\bibitem{Cay76}
A. Cayley, Theorems in trigonometry and on partitions,
{\it Messenger Math.} \textbf{5} (1876), 164--188.

\bibitem{Huang18}
J. Huang, Compositions with restricted parts, preprint, 2018.
Available at \url{https://arxiv.org/abs/1812.11010}.

\bibitem{Kos01}
T. Koshy, {\it Fibonacci and Lucas Numbers with Applications}, Wiley, 2001.

\bibitem{LW19}
R. Q. Li and A. Y. Z. Wang, Composition analogues of Beck's conjectures on partitions,
{\it European J. Combin.} \textbf{81} (2019), 210--220.

\bibitem{Sills13}
A. V. Sills, Compositions, partitions, and Fibonacci numbers,
{\it Fibonacci Quart.} \textbf{49} (2011), 348--354.

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

\bibitem{Stan12}
R. P. Stanley, {\it Enumerative Combinatorics},
Vol.~1, Cambridge University Press, 2012.

\bibitem{Vaj89}
S. Vajda, {\it Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications},
Ellis Horwood Limited, 1989.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A17; Secondary 05A19.

\noindent \emph{Keywords: }
composition, designated part, Fibonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A006367},
\seqnum{A010049},
\seqnum{A029907},
\seqnum{A102702}, and
\seqnum{A239342}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 7 2019;
revised version received December 30 2019.
Published in {\it Journal of Integer Sequences},
December 31 2019.

\bigskip
\hrule
\bigskip

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


\end{document}