\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}{\rm \underline{#1}}}

\usepackage{tikz}
\allowdisplaybreaks
\DeclareMathOperator{\CCo}{CC}
\DeclareMathOperator{\cco}{cc}
\DeclareMathOperator{\PCo}{PC}

\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 Allowing or Prohibiting Two Consecutive\\
\vskip .1in
Colors in $n$-Color Compositions
}
\vskip 1cm
\large
Brian Hopkins \\
Department of Mathematics and Statistics \\
Saint Peter's University \\
Jersey City, NJ 07306 \\USA\\
\href{mailto:bhopkins@saintpeters.edu}{\tt bhopkins@saintpeters.edu} \\
\ \\
Hua Wang \\
Department of Mathematical Sciences \\ 
Georgia Southern University \\
Statesboro, GA 30460 \\ 
USA \\ 
\href{mailto:hwang@georgiasouthern.edu}{\tt hwang@georgiasouthern.edu}
\end{center}

\vskip .2 in
\begin{abstract}
Agarwal introduced $n$-color compositions in 2000 and subsequent
research has considered both restricting which parts are allowed and, more recently, which colors are allowed.
Here we consider allowing or prohibiting two consecutive colors, focusing on several cases that connect with other types of compositions.  We also prove several identities for certain tribonacci numbers.  Most proofs are combinatorial, several using the notion of spotted tilings
introduced by the first named author in 2012.
\end{abstract}

\section{Introduction and Background}

A composition of a given positive integer $n$ is an ordered sequence of positive
integers with sum $n$. The summands are called parts of the composition.  Write $C(n)$ for the set of compositions of $n$ with $c(n) = |C(n)|$.  For example, 
\[C(3) = \{(3),(2,1),(1,2),(1,1,1)\}.\]

We can represent a composition of $n$ as a tiling of a $1 \times n$ board where, in order from left to right, each part $k$ corresponds to a $1 \times k$ block.  MacMahon \cite{m} established that $c(n)=2^{n-1}$ by a combinatorial argument equivalent to the cut-join sequence: Working from left to right, each of the $n-1$ junctures between the $n$ cells is assigned \texttt{C} for cut if a new part starts with the next cell or \texttt{J} for join if the current part continues.  Each possibility of $n-1$ binary choices corresponds to a composition of $n$.  See Figure \ref{fig:cj} for an example of both the visual representation of a composition and its cut-join sequence.

\begin{figure}[ht]
\centering
\setlength{\unitlength}{.5cm}
\begin{picture}(10,4)
\thicklines

\put(0,1){\line(0,1){2}}
\multiput(2,1)(0,0.4){5}{\line(0,1){0.2}}
\multiput(4,1)(0,0.4){5}{\line(0,1){0.2}}
\put(6,1){\line(0,1){2}}
\multiput(8,1)(0,0.4){5}{\line(0,1){0.2}}
\put(10,1){\line(0,1){2}}

\put(0,1){\line(1,0){10}}
\put(0,3){\line(1,0){10}}

\put(1.8,0){$\texttt{J}$}
\put(3.8,0){$\texttt{J}$}
\put(5.8,0){$\texttt{C}$}
\put(7.8,0){$\texttt{J}$}
\end{picture}
\caption{The composition $(3,2)$ is shown as a $1 \times 3$ block followed by a $1 \times 2$ block.  The cut-join sequence for $(3,2)$ is \texttt{JJCJ}.} \label{fig:cj}
\end{figure}

Agarwal \cite{a} introduced the concept of $n$-color compositions, where a part
$k$ has one of $k$ possible colors, denoted by a subscript $1,\ldots,k$.  Write $\CCo(n)$ for the set of $n$-color compositions of $n$ (this is the standard terminology even though $n$ is being used in two different ways).  For example, 
\[\CCo(3) =  \{(3_1), (3_2), (3_3), (2_1, 1_1), (2_2, 1_1), (1_1, 2_1), (1_1, 2_2), (1_1, 1_1, 1_1)\}.\]

The first named author developed the following representation of $n$-color compositions \cite{h}: In the tiling of a $1 \times n$ board described above, the part $k_i$ corresponds to a $1 \times k$ block with a spot in position $i$.  Here we modify the cut-join sequence to record the color by writing $\mathtt{J}_i$ for each join inside the block corresponding to $k_i$.  (Compare this to a different modification used by Hopkins and Ouvry \cite{ho} where the cuts have subscripts.)  See Figure \ref{fig:spotcj} for an example of both notions.

\begin{figure}[ht]
\centering
\setlength{\unitlength}{.5cm}
\begin{picture}(10,4)
\thicklines

\put(0,1){\line(0,1){2}}
\multiput(2,1)(0,0.4){5}{\line(0,1){0.2}}
\multiput(4,1)(0,0.4){5}{\line(0,1){0.2}}
\put(6,1){\line(0,1){2}}
\multiput(8,1)(0,0.4){5}{\line(0,1){0.2}}
\put(10,1){\line(0,1){2}}

\put(0,1){\line(1,0){10}}
\put(0,3){\line(1,0){10}}

\put(5,2){\circle*{1}}
\put(7,2){\circle*{1}}

\put(1.8,0){$\mathtt{J}_3$}
\put(3.8,0){$\mathtt{J}_3$}
\put(5.8,0){$\mathtt{C}$}
\put(7.8,0){$\mathtt{J}_1$}
\end{picture}
\caption{The $n$-color composition $(3_3,2_1)$ is shown as a $1 \times 3$ block with a spot in its third cell followed by a $1 \times 2$ block with a spot in its first cell.  The modified cut-join sequence for $(3_3,2_1)$ is $\mathtt{J_3 J_3 C J_1}$.} \label{fig:spotcj}
\end{figure}

There is additional terminology that will be helpful in the combinatorial arguments \cite[Definition 3.1]{hw}: Given the $1 \times k$ block corresponding to a part $k_c$ of an $n$-color composition, the $c$-block consists of the first $c$ cells (which includes the spotted cell) and the tail consists of any remaining cells.  For instance, $3_3$ consists of a 3-block and an empty tail while $2_1$ consists of a 1-block and a length 1 tail.

The current authors recently made a thorough study of $n$-color compositions under various restrictions on  colors \cite{hw}.  In this work, we provide additional examples of results concerning consecutive colors $b$ and $b+1$.  

In the next section, we cite general results for allowing two consecutive colors along with a new combinatorial interpretation in addition to several new particular results for small colors.  In Section 3, we cite a general result for prohibiting two consecutive colors along with three new results for compositions prohibiting colors 1 and 2.  (Below, propositions have been established before and are cited here for background or given new combinatorial proofs.  Theorems are, we believe, results new with this work.)

\section{Allowing two consecutive colors}

In this section, we consider $n$-color compositions where, for some positive integer $b \ge 1$, only colors $b$ and $b+1$ are allowed.  Note that this precludes parts less than $b$ from these compositions.  We write $\CCo_{b,b+1}(n)$ for the set of these compositions and $\cco_{b,b+1}(n)$ for their count.

\begin{proposition} 
Given positive integers $b$ and $n$, the number $\cco_{b,b+1}(n)$ of $n$-color compositions of $n$ with only colors $b$ and $b+1$ allowed satisfies the recurrence
\begin{equation}
\label{eq:ar}
\cco_{b,b+1}(n) = \cco_{b,b+1}(n-1) + \cco_{b,b+1}(n-b) + \cco_{b,b+1}(n-b-1). 
\end{equation}
A direct formula for the number of $n$-color compositions of $n$ with only colors $b$ and $b+1$ allowed is
\begin{equation}
\label{eq:ad}
\cco_{b,b+1}(n) = \sum_{m=1}^n \sum_{i=0}^{n-bm}  {i+m-1 \choose m-1} {m \choose n-bm-i}.
\end{equation}
\end{proposition}

These are special cases of \cite[Theorem 2.1]{hw} and \cite[Proposition 3.4]{hw}, respectively.

Next, we establish a new combinatorial result connecting certain ternary stings and $n$-color compositions of $n$ with only colors $b$ and $b+1$ allowed.

\begin{theorem} \label{thmternary}
Given positive integers $b$ and $n$, there is a bijection between $\CCo_{b,b+1}(n)$, the $n$-color compositions of $n$ with only colors $b$ and $b+1$ allowed, and length $n-1$ ternary strings satisfying the following conditions.
\begin{itemize}
\item There are no 12 or 21 subwords,
\item runs of 1's have length at least $b-1$,
\item runs of 2's have length at least $b$, and
\item successive 0's are separated by at least $b-1$ digits.
\end{itemize}
\end{theorem}

The constraints of such ternary strings can be viewed as walks on a state diagram of the kind used in symbolic dynamics; see Figure \ref{fig:symb}.

\begin{figure}[ht]
\centering      
 \begin{tikzpicture}[shorten >=1pt,auto]
   \tikzstyle{place}=[circle,thick,draw=black!75,fill=blue!0,minimum size=8mm]									
	\node[place] (foo) [] at (0,0) {$1$};
	\node[place] (poo) [] at (2,0) {$0$};
	\node[place] (goo) [] at (4,0) {$2$};
   \path[->] (foo) edge  [loop left] node {$(b-1)+$} ();
	\path[->] (goo) edge  [loop right] node {$b+$} ();
	\draw [<->] (.5,0)--(1.5,0);
	\draw [<->] (2.5,0)--(3.5,0);
  \end{tikzpicture}
 \caption{A representation of the ternary words of Theorem \ref{thmternary}.  The $b+$ label on a loop, for instance, indicates that if a walk uses that edge, it must use it at least $b$ times in a row.} \label{fig:symb}
\end{figure} 

\begin{proof}
Given a composition in $\CCo_{b,b+1}(n)$, its modified cut-join sequence consists of $n-1$ total symbols among $\mathtt{C}$, $\mathtt{J}_b$, and $\mathtt{J}_{b+1}$.  Create a length $n-1$ ternary word via $\mathtt{C} \mapsto 0$, $\mathtt{J}_b \mapsto 1$, and $\mathtt{J}_{b+1} \mapsto 2$.

The resulting ternary word avoids 12 and 21 since adjacent parts (corresponding to runs of 1's or 2's) are separated by a cut corresponding to 0.  A run of 1's corresponds to a part with color $b$ which has length at least $b$ and thus at least $b-1$ consecutive joins $\mathtt{J}_b$, so the run of 1's has length at least $b-1$.  Similarly, a run of 2's corresponds to a part with color $b+1$ so the run of 2's has length at least $b$.  Since the minimum part size is $b$, successive 0's are separated by a run of 1's (or 2's) of length at least $b-1$ (or $b$).

Given a ternary string satisfying the constraints, applying $0 \mapsto \mathtt{C}$, $1 \mapsto \mathtt{J}_b$, and $2 \mapsto \mathtt{J}_{b+1}$ gives the modified cut-join sequence of an $n$-color composition in $\CCo_{b,b+1}(n)$ by the previous reasoning.
\end{proof}

See Figure \ref{fig:tern} for an example of the bijection.

\begin{figure}[ht]
\centering
\setlength{\unitlength}{.5cm}
\begin{picture}(15,3)
\thicklines

\put(0,1){\line(1,0){16}}
\put(0,2){\line(1,0){16}}
\put(0,1){\line(0,1){1}}
\put(5,1){\line(0,1){1}}
\put(3.5,1.5){\circle*{.5}}
\put(8,2){\line(0,-1){1}}
\put(12,2){\line(0,-1){1}}
\put(16,2){\line(0,-1){1}}
\put(7.5,1.5){\circle*{.5}}
\put(11.5,1.5){\circle*{.5}}
\put(14.5,1.5){\circle*{.5}}

\put(0.8,0){2}
\put(1.8,0){2}
\put(2.8,0){2}
\put(3.8,0){2}
\put(4.8,0){0}
\put(5.8,0){1}
\put(6.8,0){1}
\put(7.8,0){0}
\put(8.8,0){2}
\put(9.8,0){2}
\put(10.8,0){2}
\put(11.8,0){0}
\put(12.8,0){1}
\put(13.8,0){1}
\put(14.8,0){1}
\end{picture}
\caption{The correspondence between $(5_4, 3_3, 4_4, 4_3) \in \CCo_{3,4}(16)$ and the length 15 ternary string $222201102220111$.} \label{fig:tern}
\end{figure}

In the remainder of this section, we give further particular results for $n$-color compositions with only colors 1 and 2 allowed, with only colors 2 and 3 allowed, and with only colors 3 and 4 allowed.

\subsection{Allowing colors 1 and 2}
The recurrence for the number of $n$-color compositions of $n$ with only colors 1 and 2 allowed is, by \eqref{eq:ar}, 
\[ \cco_{1,2}(n) = 2\cco_{1,2}(n-1) + \cco_{1,2}(n-2), \] 
\seqnum{A001333}.  In the OEIS \cite{o} entry for this sequence, Paul Barry stated a direct formula simpler than applying our general formula \eqref{eq:ad}.
Next, we provide a combinatorial argument using $n$-color compositions for his formula.

\begin{theorem} \label{pbarry}
Given a positive integer $n$,
\[\cco_{1,2}(n) = \sum_{m=0}^{\lfloor \frac{n}{2} \rfloor} 2^m {n \choose 2m}.\]
\end{theorem}

\begin{proof}
We show that the summation counts the number of ways to build a composition in $\CCo_{1,2}(n)$.
Let $m$ satisfying $0\leq m \leq \lfloor \frac{n}{2} \rfloor$ be the number of parts of size at least 2. There are ${n \choose 2m}$ ways to choose a sequence of cells $a_1, a_2, \ldots, a_{2m}$ from a $1\times n$ board. Let $a_{2i+1}$ and $a_{2i+2}$ mark the starting and ending cells of a part of size at least 2 for $0 \leq i \leq m-1$.  The remaining cells between these parts (i.e., not between $a_{2i+1}$ and $a_{2i+2}$ for any $i$) are parts of size 1 which must have color 1. Each of the $m$ larger parts has two choices of color, giving the factor $2^m$. 
\end{proof}

Figure \ref{fig:thm4} shows an example of the procedure.

\begin{figure}[ht]
\centering
\setlength{\unitlength}{.5cm}
\begin{picture}(13,4)(0,0.5)
\thicklines

\put(0,3){\line(1,0){13}}
\put(0,4){\line(1,0){13}}
\put(1.1,3.3){$a_1$}
\put(0,4){\line(0,-1){1}}
\put(13,4){\line(0,-1){1}}
\put(2.1,3.3){$a_2$}
\put(3.1,3.3){$a_3$}
\put(7.1,3.3){$a_4$}
\put(10.1,3.3){$a_5$}
\put(12.1,3.3){$a_6$}

\put(0,1){\line(1,0){13}}
\put(0,2){\line(1,0){13}}
\put(1,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(0,1){\line(0,1){1}}
\put(8,1){\line(0,1){1}}
\put(9,1){\line(0,1){1}}
\put(10,1){\line(0,1){1}}
\put(13,1){\line(0,1){1}}

\thinlines
\put(1,4){\line(0,-1){1}}
\put(2,4){\line(0,-1){1}}
\put(3,4){\line(0,-1){1}}
\put(4,4){\line(0,-1){1}}
\put(5,4){\line(0,-1){1}}
\put(6,4){\line(0,-1){1}}
\put(7,4){\line(0,-1){1}}
\put(8,4){\line(0,-1){1}}
\put(9,4){\line(0,-1){1}}
\put(10,4){\line(0,-1){1}}
\put(11,4){\line(0,-1){1}}
\put(12,4){\line(0,-1){1}}
\end{picture}
\caption{The selection of $2,3,4,8,11,13$ for the $a_i$ when $m=3$ gives the composition $(1,2,5,1,1,3) \in C(13)$ which has $2^3=8$ possible ways to color the parts at least 2 to determine an element of $\CCo_{1,2}(13)$.}\label{fig:thm4}
\end{figure}

\subsection{Allowing colors 2 and 3}
Our greatest number of new results concerns the number of $n$-color compositions of $n$ with only colors 2 and 3 allowed.  By \eqref{eq:ar} the recurrence is 
\[\cco_{2,3}(n) = \cco_{2,3}(n-1) + \cco_{2,3}(n-2) + \cco_{2,3}(n-3)\]
and this is (one version of) tribonacci numbers, \seqnum{A001590}.  This sequence is known to count regular compositions restricted to parts congruent to 1 or 2 modulo 3 \cite{br,hb}.  Next we establish a bijection between $\CCo_{2,3}(n+1)$ and these restricted compositions which we denote by $C_{1,2m3}(n)$.

\begin{theorem} \label{blocktail}
For each positive integer $n$, there is a bijection between $n$-color compositions of $n+1$ with only colors 2 and 3 allowed and compositions of $n$ with all parts congruent to 1 and 2 modulo 3.  I.e.,
\[\CCo_{2,3}(n+1) \cong C_{1,2m3}(n).\]
\end{theorem}

\begin{proof}
Given the spotted tiling of a composition in $\CCo_{2,3}(n+1)$, we construct a composition in $C_{1,2m3}(n)$ as follows.
\begin{itemize}
\item For each part of the $n$-color composition of $n+1$, convert the $c$-block into a part $c$ and each cell of the tail into a part 1.
\item Decrease the first part (which is 2 or 3) by 1.
\item We now have a composition of $n$ restricted to parts 1, 2, or 3 with first part 1 or 2.  Combine runs of parts 3 with the part preceding the run.
\end{itemize}
Since all parts 3 have been combined into greater parts merged with a part 1 or 2, this gives a composition in $C_{1,2m3}(n)$.

The reverse map is clear: Given a composition in $C_{1,2m3}(n)$, we construct an element of $\CCo_{2,3}(n+1)$ as follows.
\begin{itemize}
\item Replace each part $k > 3$ with the part $k \bmod 3$ followed by $\lfloor k/3 \rfloor$ parts 3.
\item Increase the first part by 1 (so that it is now 2 or 3).
\item Convert each part 2 or 3 followed by a length $j \ge 0$ run of parts 1 into a part of an $n$-color composition consisting of a 2- or 3-block, respectively, and length $j$ tail, i.e., the part $(j+2)_2$ or $(j+3)_3$.
\end{itemize}
This gives an $n$-color composition of $n+1$ with each part colored 2 or 3 as desired.
\end{proof}

See Figure \ref{fig:bij7} for an example of the bijection.

\begin{figure}[ht]
\centering
\setlength{\unitlength}{.5cm}
\begin{picture}(12,4)(0,0.5)
\thicklines

\put(0,3){\line(1,0){12}}
\put(0,4){\line(1,0){12}}
\put(0,3){\line(0,1){1}}
\put(5,3){\line(0,1){1}}
\put(2.5,3.5){\circle*{.5}}
\put(8,4){\line(0,-1){1}}
\put(12,4){\line(0,-1){1}}
\put(6.5,3.5){\circle*{.5}}
\put(10.5,3.5){\circle*{.5}}

\put(1,1){\line(1,0){11}}
\put(1,2){\line(1,0){11}}
\put(1,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(4,1){\line(0,1){1}}
\put(5,1){\line(0,1){1}}
\put(7,1){\line(0,1){1}}
\put(11,1){\line(0,1){1}}
\put(12,1){\line(0,1){1}}

\end{picture}
\caption{The correspondence between $(5_3,3_2,4_3) \in C_{2,3}(12)$ and $(2,1,1,2,4,1) \in C_{1,2m3}(11)$.}\label{fig:bij7}
\end{figure}

The $n$-color compositions with only colors 2 and 3 allowed match a particular type of ``restricted tiling'' studied by Barry Balof \cite[Example 4]{b}, namely, tilings of a board using two types of $1\times 1$ blocks and a single type of $1\times 2$ blocks, such that no adjacent $1\times 1$ blocks have the same type.  Equivalently, let $C^*_{1,2}(n)$ be the compositions of $n$ restricted to parts $1_1, 1_2, 2$ with no adjacent parts 1 having the same color.

\begin{theorem}
There is a bijection between $n$-color compositions of $n+2$ with only colors 2 and 3 allowed and compositions of $n$ with parts 2, two types of parts 1, with no adjacent parts 1 of the same type.  I.e.,
\[\CCo_{2,3}(n+2) \cong C^*_{1,2}(n).\]
\end{theorem}

\begin{proof}
Given a composition in $C^*_{1,2}(n)$, we construct a composition in $\CCo_{2,3}(n+2)$.  Following Balof, we write $a$ and $b$ for the two types of parts 1.

First, replace each part 2 with two symbols $c$ and add an additional symbol $c$ at the beginning and end.  This gives a length $n+2$ string of symbols $a, b, c$ with an even number of symbols $c$, beginning and ending with $c$, and with no $aa$ or $bb$ subsequences.

Similar to the proof of Theorem \ref{pbarry}, supposing there are $2m$ symbols $c$, we consider the $(2i+1)$st and $(2i+2)$nd successive symbols $c$ for each $0 \le i \le m-1$.
\begin{itemize}
\item If the two symbols $c$ are adjacent, then map them to a part $2_2$.
\item If the two symbols $c$ are separated by a string $aba\ldots$ of length $k$, then map the string $caba\ldots c$ to a part $(k+2)_2$.
\item If the two symbols $c$ are separated by a string $bab\ldots$ of length $k$, then map the string $cbab\ldots c$ to a part $(k+2)_3$.
\end{itemize}
Since the string had $n+2$ symbols, this produces an $n$-color composition in $\CCo_{2,3}(n+2)$.

The reverse map is clear: Given an element of $\CCo_{2,3}(n+2)$, make the substitutions $2_2 \mapsto cc$ and, for $k > 2$, $k_2 \mapsto caba\ldots c$ and $k_3 \mapsto cbab\ldots c$ each consisting of $k$ symbols.  Removing the first and last symbol $c$ leaves a string of symbols $a,b,c$ where all symbols $c$ occur in pairs.  The substitution $cc \mapsto 2$ gives a tiling equivalent to a composition in $C^*_{1,2}(n)$.
\end{proof}

See Figure \ref{Balofex} for an example of the bijection.

\begin{figure}
\centering
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{c}
$(1_1, 2, 2, 1_2, 1_1, 1_2, 2)$ \\
$a \; c \; c \; c \; c \; b \; a \; b \; c \; c$ \\
$c \; a \; c \mid c \; c \mid c \; b \; a \; b \; c \mid c \; c$ \\
$(3_2, 2_2, 5_3, 2_2)$
\end{tabular}
\caption{The correspondence between $(1_1, 2, 2, 1_2, 1_1, 1_2, 2) \in C^*_{1,2}(10)$ and $(3_2, 2_2, 5_3, 2_2) \in \CCo_{2,3}(12)$.} \label{Balofex}
\end{figure}


The remaining results of this subsection are combinatorial proofs of identities involving certain tribonacci numbers, some known and some new.  Since this sequence is of broader interest, we state the identities in terms of the sequence $t(n)$ defined by 
\[t(n) = t(n-1) + t(n-2) + t(n-3)\]
with $t(0) = 1$, $t(1) = 0$, and $t(2)=1$ (\seqnum{A001590}).  The proofs make use of the fact $\cco_{2,3}(n) = t(n)$.

The first identity (in an equivalent form and starting from our $t(2)$) was used by Erd\H{o}s, Sz\'ekely, etc., in their study of ``tribonacci graphs'' \cite{ceess}.  
It is also a special case of Identity 77 in the book of Benjamin and Quinn \cite{bq}.

\begin{proposition} \label{trib1}
For each integer $n \ge 3$,
\[t(n) = t(n-2) + 2 \sum_{i=3}^n t(n-i).\]
\end{proposition}

\begin{proof}
We establish a bijection
\[\CCo_{2,3}(n) \cong \CCo_{2,3}(n-2) \cup \bigcup_{i=3}^n 2 \CCo_{2,3}(n-i)\]
where $2\CCo_{2,3}(k)$ denotes two copies of $\CCo_{2,3}(k)$.

Given a composition in $\CCo_{2,3}(n)$, consider its last part.
\begin{itemize}
\item If the last part is $2_2$, then removing that part leaves a composition in $\CCo_{2,3}(n-2)$.
\item If the last part is $k_2$ for some $k \ge 3$, then removing that part leaves a composition in one copy of $\CCo_{2,3}(n-k)$.
\item If the last part is $k_3$ for some $k \ge 3$, then removing that part leaves a composition in the other copy of $\CCo_{2,3}(n-k)$.
\end{itemize}

The reverse map is clear: Given a composition in $\CCo_{2,3}(n-2)$, add a part $2_2$ at the end.  Given a composition in one set of $\bigcup \CCo_{2,3}(n-k)$ for $k \ge 3$, add a part $k_2$ at the end.  Given a composition from the other $\bigcup \CCo_{2,3}(n-k)$ for $k \ge 3$, add a part $k_3$ at the end.  By construction, the images are distinct.
\end{proof}

Proposition \ref{trib1} involves the sum of consecutive $t(i)$ terms. The identity in the following result, which combines cases of Identities 104 and 105 in Benjamin and Quinn \cite{bq}, involves the sum of every other $t(i)$ term.

\begin{proposition} \label{trib2}
For each integer $n \ge 3$,
\[ t(n) = t(n-1) + 1 + 2\sum_{i=1}^{\lfloor n/2 \rfloor - 1} t(n - 2i - 1).\]
\end{proposition}
 
\begin{proof}
We establish a bijection
\[\CCo_{2,3}(n) \cong \CCo_{2,3}(n-1) \cup \{h\} \cup \bigcup_{i=1}^{\lfloor n/2 \rfloor - 1} 2 \CCo_{2,3}(n-2i-1)\]
where $h = h_e := ((2_2)^{n/2})$ if $n$ is even (where the exponent designates repetition), $h = h_o := (3_3, (2_2)^{(n-3)/2})$ if $n$ is odd, and $2\CCo_{2,3}(k)$ denotes two copies of $\CCo_{2,3}(k)$.

Write a composition in $\CCo_{2,3}(n)$ as the concatenation of $b \in \CCo_{2,3}(n-2k)$ and $k$ parts $2_2$ where the final part $b_c$ of $b$ is not $2_2$, i.e., the maximal terminal run of parts $2_2$ has length $k$.  

If $b$ is empty, then $n$ is even and we have the composition $h_e = ((2_2)^{n/2})$.  If $b = 3_3$, then $n$ is odd and we have the composition $h_o = (3_3, (2_2)^{(n-3)/2})$.  Otherwise, consider $b_c$, the last part of $b$.
\begin{itemize}
\item If $b_c \ne 3_3$, then applying $b_c \mapsto (b-1)_c$ and removing the $k$ terminal parts $2_2$ leaves a composition in $\CCo_{2,3}(n-2k-1)$.
\item If $b_c = 3_3$, then removing that $3_3$ and the $k$ terminal parts $2_2$ leaves a composition in $\CCo_{2,3}(n-2k-3)$.
\end{itemize}

As $k$ ranges from 0 to $\lfloor n/2 \rfloor - 1$ (since $h_e$ and $h_o$ are excluded), together we have
\[ (\CCo_{2,3}(n-1) \cup \CCo_{2,3}(n-3)) \cup (\CCo_{2,3}(n-3) \cup \CCo_{2,3}(n-5)) \cup \cdots \]
ending with $(\CCo_{2,3}(5) \cup \CCo_{2,3}(3)) \cup \CCo_{2,3}(3)$ if $n$ is even (recall that $\CCo_{2,3}(1) = 0$) and $(\CCo_{2,3}(6) \cup \CCo_{2,3}(4)) \cup \CCo_{2,3}(4)$ if $n$ is odd.

The reverse map is clear: For a composition in $\CCo_{2,3}(n-1)$ or one $\bigcup \CCo_{2,3}(n-2i-1)$, apply $k_c \mapsto (k+1)_c$ to the last part of the composition and append the appropriate number of parts $2_2$ to make a composition in $\CCo_{2,3}(n)$.  For a composition in the other set $\bigcup \CCo_{2,3}(n-2i-1)$, add a part $3_3$ and then the appropriate number of parts $2_2$ to make a composition in $\CCo_{2,3}(n)$.  Carry over the composition $h_e$ or $h_o$ depending on whether $n$ is even or odd, respectively.  By construction, the images are distinct.
\end{proof}

In addition to the above identities on $t(n)$ that can be found in the existing literature, with $n$-color compositions and spotted tilings we can also prove some new identities. 

First, we establish a combinatorial proof of a general recursion on $t(n)$.  We use the convention that $t(n) = 0$ for $n < 0$.

\begin{theorem} \label{tribrecur}
For each integer $n \ge 0$,
\[ t(n) = \begin{cases}
   \displaystyle 1 + \sum_{i=0}^k (t(n-3i-1)+t(n-3i-2)), & \text{if $n = 3k$;} \\[3ex]
   \displaystyle -1 + \sum_{i=0}^k (t(n-3i-1)+t(n-3i-2)), & \text{if $n = 3k + 1$;} \\[3ex]
   \displaystyle \sum_{i=0}^k (t(n-3i-1)+t(n-3i-2)), & \text{if $n = 3k + 2$.}
\end{cases}\]
\end{theorem}

\begin{proof}
We consider the case $n = 3k+2$ in detail and then explain the modifications for the other cases.
We establish a bijection
\[\CCo_{2,3}(n) \cong \bigcup_{i=0}^k (\CCo_{2,3}(n-3i-1) \cup \CCo_{2,3}(n-3i-2)).\]

Write a composition $c \in \CCo_{2,3}(n)$ as the concatenation of $b \in \CCo_{2,3}(n-3k)$ and $k$ parts $3_3$ where the final part $b_c$ of $b$ is not $3_3$, i.e., the maximal terminal run of parts $3_3$ has length $k$.  We know $b$ is nonempty since $n = 3k+2$.  Consider $b_c$, the last part of $b$.
\begin{itemize}
\item If $b_c \ne 2_2$, then applying $b_c \mapsto (b-1)_c$ and removing the $k$ terminal parts $3_3$ leaves a composition in $\CCo_{2,3}(n-3k-1)$.
\item If $b_c = 2_2$, then removing that $2_2$ and the $k$ terminal parts $3_3$ leaves a composition in $\CCo_{2,3}(n-3k-2)$.
\end{itemize}

The reverse map is clear: For a composition in $\bigcup \CCo_{2,3}(n-3i-1)$, apply $k_c \mapsto (k+1)_c$ to the last part of the composition and append the appropriate number of parts $3_3$ to make a composition in $\CCo_{2,3}(n)$. For a composition in $\bigcup \CCo_{2,3}(n-3i-2)$, add a part $2_2$ and then the appropriate number of parts $3_3$ to make a composition in $\CCo_{2,3}(n)$.

In the case $n = 3k$, there is also the composition $((3_3)^k)$ (for which $b$ used above is empty) that contributes one to the sum.  In the case $n = 3k+1$, the first part of the reverse map references the last part of the empty composition of zero, so the count is decreased by one.
\end{proof}

Now we prove an analogue of Proposition \ref{trib1} involving consecutive $t(i)$ terms and Proposition \ref{trib2} involving every other $t(i)$ term.  Our last result for this subsection uses Theorem \ref{tribrecur} to establish an identity involving every third $t(i)$ term.  The proof is algebraic but relies on the combinatorial proof of the previous theorem.

\begin{theorem}
For $n \ge 3$,
\[ t(n) + t(n-2) = \begin{cases}
   \displaystyle 2\sum_{i=0}^{k-1}t(n-3i-1), & \text{if $n = 3k$ or $n = 3k+1$;} \\[3ex]
   \displaystyle 2 + 2\sum_{i=0}^{k-1} t(n-3i-1), & \text{if $n = 3k + 2$.} 
\end{cases}\]
\end{theorem}

\begin{proof}
We consider the case $n = 3k+1$.  Applying Theorem \ref{tribrecur} to $t(n) = t(3k+1)$ and $t(n-2) = t(3(k-1)+2)$
gives
\begin{align*}
&t(n) + t(n-2) \\
& = -1 + \sum_{i=0}^k (t(3k-3i) + t(3k-3i-1)) + \sum_{i=0}^{k-1} (t(3k-3i-2) + t(3k-3i-3)) \\
& = -1 + \sum_{i=0}^k t(3k-3i) + \left(\sum_{i=0}^k (t(3k-3i-1) +t(3k-3i-2))\right) + \sum_{i=1}^k t(3k-3i) \\
& = -1 + \sum_{i=0}^k t(3k-3i) + [t(3k) - 1] + \sum_{i=1}^k t(3k-3i)\\
& = -2 + 2 \sum_{i=0}^k t(3k-3i) \\
& = -2 + 2t(0) + 2 \sum_{i=1}^k t(3k-3i)
\end{align*}
where the second equality uses $t(-2) = 0$ and the third equality invokes Theorem \ref{tribrecur} again, here the $n = 3k$ case.  From the final line, the result follows since $t(0) = 1$.

The other two cases are similar (and slightly easier).
\end{proof}

\subsection{Allowing colors 3 and 4}
The recurrence for the number of $n$-color compositions of $n$ with only colors 3 and 4 allowed is, by \eqref{eq:ar}, 
\[ \cco_{3,4}(n) = \cco_{3,4}(n-1) + \cco_{3,4}(n-3) + \cco_{3,4}(n-4), \] 
\seqnum{A070550}.  Our last result for this section establishes a result mentioned in the OEIS connecting this sequence with the Fibonacci numbers  (\seqnum{A000045}) defined by $f(0) = 0$, $f(1) = 1$, and $f(n) = f(n-1)+f(n-2)$ for $n \ge 2$.

For the following combinatorial proof, we use compositions of $n$ with no parts 1, denoted $C_{\hat{1}}(n)$.  
Cayley found that $c_{\hat{1}}(n) = f(n-1)$ \cite{c}.

\begin{proposition}
For $n \ge 3$, 
\[\cco_{3,4}(n)+\cco_{3,4}(n-2)=f(n-1).\]
\end{proposition}

\begin{proof}
We establish a bijection 
\[\CCo_{3,4}(n) \cup \CCo_{3,4}(n-2) \cong C_{\hat{1}}(n).\]  

For a composition in $\CCo_{3,4}(n)$, working from left to right, apply the substitutions $k_3 \mapsto k$ and $k_4 \mapsto (2, k-2)$.  For a composition in $\CCo_{3,4}(n-2)$, use the same substitutions and add a part 2 at the end.  This produces distinct compositions in $C_{\hat{1}}(n)$.

For the inverse map, for a composition in $C_{\hat{1}}(n)$, let $j \ge 0$ be the length of the terminal run of parts 2.  If $j$ is odd, remove a part 2 from the end, giving a composition of $n-2$ with an even length terminal run of parts 2.  
Working from left to right, map each part $k \ge 3$ to $k_3$ and, for each part 2, combine it with the following part $k$ and map the pair $(2,k)$ to $(k+2)_4$.  This produces distinct compositions in $\CCo_{3,4}(n) \cup \CCo_{3,4}(n-2)$.
\end{proof}

See Figure \ref{fig:bij34} for an example of the bijection.

\begin{figure}[ht]
\begin{align*}
    (7_3) & \longleftrightarrow (7) \\
    (7_4) & \longleftrightarrow (2,5) \\
    (4_3,3_3) & \longleftrightarrow (4,3) \\
    (4_4,3_3) & \longleftrightarrow (2,2,3) \\
    (3_3,4_3) & \longleftrightarrow (3,4) \\
    (3_3,4_4) & \longleftrightarrow (3,2,2) \\
    (5_3) & \longleftrightarrow (5,2) \\
    (5_4) & \longleftrightarrow (2,3,2)
\end{align*}
\vspace{-20pt}
\caption{The correspondence between $\CCo_{3,4}(7) \cup \CCo_{3,4}(5)$ and $C_{\hat{1}}(7)$, each with $f(6) = 8$ elements.} \label{fig:bij34}
\end{figure}

\section{Prohibiting two consecutive colors}

In this section, we consider $n$-color compositions where, for some integer $b \ge 1$, the colors $b$ and $b+1$ are prohibited.  We write $\CCo_{\widehat{b,b+1}}(n)$ for the set of these compositions and $\cco_{\widehat{b,b+1}}(n)$ for their count.

\begin{proposition} \label{propp}
Given an integer $b \ge 1$, the number of $n$-color compositions of $n$ with colors $b$ and $b+1$ prohibited satisfies the recurrence
\[\cco_{\widehat{b,b+1}}(n) = 3\cco_{\widehat{b,b+1}}(n-1) - \cco_{\widehat{b,b+1}}(n-2) - \cco_{\widehat{b,b+1}}(n-b) + \cco_{\widehat{b,b+1}}(n-b-2). \]
\end{proposition}

This is a special case of \cite[Theorem 2.2]{hw}.

\subsection{Prohibiting colors 1 and 2}
We give three results for $n$-color compositions where the colors 1 and 2 are prohibited.  Note that this means there cannot be parts of size 1 or 2.  By Proposition \ref{propp} we have the recurrence
\begin{equation} \label{eq:p12}
\cco_{\widehat{1,2}}(n) = 2\cco_{\widehat{1,2}}(n-1) - \cco_{\widehat{1,2}}(n-2) + \cco_{\widehat{1,2}}(n-3),
\end{equation}
\seqnum{A005314}, which also has a direct formula,
\[\cco_{\widehat{1,2}}(n) = \sum_{m=1}^{\lfloor n/3 \rfloor} {n-m-1 \choose 2m-1}, \]
a special case of \cite[Proposition 3.8]{hw}.

Our first result of this section connects $n$-color compositions with colors 1 and 2 prohibited and regular compositions restricted to parts congruent to 1 or 2 modulo 4.  Write $C_{1,2m4}(n)$ for these compositions of $n$.  Recall the notion of $c$-block and tail given in the introduction and used in Theorem \ref{blocktail}.

\begin{theorem}
There is a bijection between $n$-color compositions of $n+2$ with colors 1 and 2 prohibited and compositions of $n$ restricted to parts congruent to 1 or 2 modulo 4.  I.e.,
\[\CCo_{\widehat{1,2}}(n+2) \cong C_{1,2m4}(n).\]
\end{theorem}

\begin{proof}
Given the spotted tiling of a composition in $\CCo_{\widehat{1,2}}(n+2)$, we construct a composition in $C_{1,2m4}(n)$ as follows.
\begin{itemize}
\item Remove the first two cells (which cannot contain a spot).
\item For each part of the $n$-color composition of $n$, convert the $c$-block into a part $c$ and each cell of the tail into a part 1.
\item In the composition of $n$, replace each part $k$ with $k \equiv 3, 4 \bmod 4$ with the pair $(k-2,2)$.
\end{itemize}
Since all parts congruent to 3 or 4 modulo 4 have been replaced by parts congruent to 1 or 2 modulo 4, this gives a composition in $C_{1,2m4}(n)$.

For the reverse map, given a composition in $C_{1,2m4}(n)$, we construct an element of $\CCo_{\widehat{1,2}}(n+2)$ as follows.
\begin{itemize}
\item Increase the first part by 2 making it at least 3.
\item Working from right to left, replace each pair $(k,2)$ by $k+2$.  This gives a composition with no parts 2.
\item Working left to right, convert each part $c \ge 3$ followed by a length $j \ge 0$ run of parts 1 into a part of an $n$-color composition consisting of a $c$-block and length $j$ tail, i.e., the part $(c+j)_c$.
\end{itemize}
This gives an $n$-color composition of $n+2$ with no part colored 1 or 2 as desired.
\end{proof}

See Figure \ref{fig:bij8} for an example of the bijection.

\begin{figure}[ht]
\centering
\setlength{\unitlength}{.5cm}
\begin{picture}(12,4)(0,0.5)
\thicklines

\put(0,3){\line(1,0){12}}
\put(0,4){\line(1,0){12}}
\put(0,3){\line(0,1){1}}
\put(5,3){\line(0,1){1}}
\put(3.5,3.5){\circle*{.5}}
\put(8,4){\line(0,-1){1}}
\put(12,4){\line(0,-1){1}}
\put(7.5,3.5){\circle*{.5}}
\put(11.5,3.5){\circle*{.5}}

\put(2,1){\line(1,0){10}}
\put(2,2){\line(1,0){10}}
\put(2,1){\line(0,1){1}}
\put(4,1){\line(0,1){1}}
\put(5,1){\line(0,1){1}}
\put(6,1){\line(0,1){1}}
\put(8,1){\line(0,1){1}}
\put(10,1){\line(0,1){1}}
\put(12,1){\line(0,1){1}}
\end{picture}
\caption{The correspondence between $(5_4,3_3,4_4) \in \CCo_{\widehat{1,2}}(12)$ and $(2,1,1,2,2,2) \in C_{1,2m4}(10).$} \label{fig:bij8}
\end{figure}

Our next result involves palindromic compositions, those that read the same from left to right as from right to left.  These have been studied since at least 1975 \cite{hb}.  Among these, we consider palindromic compositions $\PCo_{\hat{2}}^o(n)$ that have no parts 2 and an odd number of parts which were studied by Chinn and Heubach \cite{ch}.

\begin{theorem}
There is a bijection between $n$-color compositions of $n$ with colors 1 and 2 prohibited and palindromic compositions of $2n-5$ with no parts 2 and an odd number of parts.  I.e.,
\[\CCo_{\widehat{1,2}}(n) \cong \PCo_{\hat{2}}^o(2n-5).\]
\end{theorem}

\begin{proof}
Given a composition in $\CCo_{\widehat{1,2}}(n)$, first build a regular composition of $n$ by converting each $c$-block into a part $c$ and each cell of the tail into a part 1.  Let $\ell$ be the length of this composition $d$ and note that its first part $d_1$ is at least 3 and that it has no part 2.  Now prepend the reverse of $d$ in front of $d$ making a palindromic composition of $2n$ with $2\ell$ parts including two parts $d_1$ in the middle.  Replace that pair $(d_1, d_1)$ with a single part $2d_1 - 5$.  This gives a palindromic composition of $2n-5$ with $2\ell-1$ parts having no parts 2, i.e., an element of $\PCo_{\hat{2}}^o(2n-5)$.

For the reverse map, given a composition in $\PCo_{\hat{2}}^o(2n-5)$, it has a well-defined middle part $m$ since its length is odd.  Because every other part of the palindromic composition is doubled and the sum is odd, we know $m$ is odd.  Replace $m$ with the pair $((m+5)/2, (m+5)/2)$ giving a palindromic composition of $2n$ with an even number of parts.  Now consider just the second half, a composition of $n$ with first part $(m+5)/2$ which is at least 3.  To make an $n$-color composition, convert each part $c$ with $c \ge 3$ followed by a length $j \ge 0$ run of parts 1 into a part of an $n$-color composition consisting of a $c$-block and length $j$ tail.  This produces an element of $\CCo_{\widehat{1,2}}(n)$.
\end{proof}

See Figure \ref{fig:pal} for an example of the bijection.

\begin{figure}[ht]
\centering
\setlength{\unitlength}{.4cm}
\begin{picture}(22,6)(-11,0.75)
\thicklines

\put(0,5){\line(1,0){13}}
\put(0,6){\line(1,0){13}}
\put(0,5){\line(0,1){1}}
\put(5,5){\line(0,1){1}}
\put(3.5,5.5){\circle*{.5}}
\put(11,6){\line(0,-1){1}}
\put(12,5.5){$\ldots$}
\put(7.5,5.5){\circle*{.5}}

\put(0,3){\line(1,0){13}}
\put(0,4){\line(1,0){13}}
\put(0,3){\line(0,1){1}}
\put(4,3){\line(0,1){1}}
\put(5,3){\line(0,1){1}}
\put(11,3){\line(0,1){1}}
\put(8,3){\line(0,1){1}}
\put(9,3){\line(0,1){1}}
\put(10,3){\line(0,1){1}}
\put(12,3.5){$\ldots$}

\put(0,3){\line(-1,0){13}}
\put(0,4){\line(-1,0){13}}
\put(0,3){\line(0,1){1}}
\put(-4,3){\line(0,1){1}}
\put(-5,3){\line(0,1){1}}
\put(-11,3){\line(0,1){1}}
\put(-8,3){\line(0,1){1}}
\put(-9,3){\line(0,1){1}}
\put(-10,3){\line(0,1){1}}
\put(-13,3.5){$\ldots$}

\put(0,1){\line(1,0){10.5}}
\put(0,2){\line(1,0){10.5}}
\put(1.5,1){\line(0,1){1}}
\put(2.5,1){\line(0,1){1}}
\put(8.5,1){\line(0,1){1}}
\put(5.5,1){\line(0,1){1}}
\put(6.5,1){\line(0,1){1}}
\put(7.5,1){\line(0,1){1}}
\put(9.5,1.5){$\ldots$}

\put(0,1){\line(-1,0){10.5}}
\put(0,2){\line(-1,0){10.5}}
\put(-1.5,1){\line(0,1){1}}
\put(-2.5,1){\line(0,1){1}}
\put(-8.5,1){\line(0,1){1}}
\put(-5.5,1){\line(0,1){1}}
\put(-6.5,1){\line(0,1){1}}
\put(-7.5,1){\line(0,1){1}}
\put(-10.5,1.5){$\ldots$}

\end{picture}
\caption{The connection between an $n$-color composition $(5_4, 6_3, \ldots)$ and a palindromic composition of the form $(\ldots, 1,1,1,3,1,3,1,3,1,1,1, \ldots)$.}\label{fig:pal}
\end{figure}

Our last result connects two types of $n$-color compositions, those prohibiting colors 1 and 2 and those prohibiting the color 2 (counted by \seqnum{A034943}; see \cite[\S3.2.2]{hw}).

\begin{theorem}
For $k$ a positive integer, the number of $n$-color compositions of $3k$ with colors 1 and 2 prohibited equals the number of $n$-color compositions of $2k-1$ prohibiting the color 2.  I.e.,
\[\cco_{\widehat{1,2}}(3k) = \cco_{\hat{2}}(2k-1).\]
\end{theorem}

In other words, there is a trisection of \seqnum{A005314} that matches a bisection of \seqnum{A034943}.

\begin{proof}
Let $a(k) = \cco_{\widehat{1,2}}(3k)$.  Repeated algebraic manipulation of  
\[\cco_{\widehat{1,2}}(3k) = 2\cco_{\widehat{1,2}}(3k-1) - \cco_{\widehat{1,2}}(3k-2) + \cco_{\widehat{1,2}}(3k-3)\]
from \eqref{eq:p12} into an expression in terms of $\cco_{\widehat{1,2}}(3k-3)$, $\cco_{\widehat{1,2}}(3k-6)$, and $\cco_{\widehat{1,2}}(3k-9)$ gives
\[a(k) = 5a(k-1)+2a(k-2)+a(k-3)\]
with initial values $a(1) = 1$, $a(2) = 5$, $a(3) = 28$.
The recurrence for $a(k)$ can also be determined by using the generating function for $\cco_{\widehat{1,2}}(k)$, namely 
\[F(x)= \frac{x^3}{1 - 2 x + x^2 - x^3},\] and determining the trisection of the series by 
\[\frac{F(\sqrt[3]{x}) + F(\omega \sqrt[3]{x}) + F(\omega^2 \sqrt[3]{x})}{3}\]
where $\omega$ is a primitive third root of unity.

Let $b(k) = \cco_{\hat{2}}(2k-1)$.  By \cite[Theorem 2.2]{hw} we have
\[\cco_{\hat{2}}(2k-1) = 3\cco_{\hat{2}}(2k-2) - 2\cco_{\hat{2}}(2k-3) + \cco_{\hat{2}}(2k-4).\]
Either approach mentioned above leads to
\[b(k) = 5b(k-1)+2b(k-2)+b(k-3)\]
with initial values $b(1) = 1$, $b(2) = 5$, $b(3) = 28$.  Thus the sequences are equal.
\end{proof}

Of course, in the spirit of this paper, we would prefer a combinatorial proof using a bijection $\CCo_{\widehat{1,2}}(3k) \cong \CCo_{\hat{2}}(2k-1)$; we invite the reader to find one.

\section{Acknowledgments}
We appreciate the anonymous referee for careful reading and helpful suggestions.

\begin{thebibliography}{9}

\bibitem{a}
A.\ K.\ Agarwal, $n$-colour compositions, {\it Indian J.\ Pure Appl.\ Math.} \textbf{31} (2000) 1421--1437.

\bibitem{b} B.\ Balof, Restricted tilings and bijections, {\it J.\ Integer Sequences} {\bf 15} (2012), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Balof/balof19.html}{Article 12.2.3}.

\bibitem{br} M.\ Beck and N.\ Robbins, Variations on a generating-function theme:\ enumerating compositions with parts avoiding an arithmetic sequence, {\it Amer.\ Math.\ Monthly} {\bf 122} (2015), 256--263.

\bibitem{bq}
A.\ T.\ Benjamin and J.\ J.\ Quinn, {\it Proofs that Really Count:\ The Art of Combinatorial Proof}. Mathematical Association of America, 2003.

\bibitem{c}
A.\ Cayley, Theorem on partitions, {\it Messenger Math.} {\bf 5} (1876) 188.

\bibitem{ch}
P.\ Chinn and S.\ Heubach, Integer sequences related to compositions without $2$'s, {\it J.\ Integer Sequences} {\bf 6} (2003),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.html}{Article 03.2.3}.

\bibitem{ceess} L.\ Clark, R.\ Entringer, P.\ Erd\H{o}s, H.\ Sun, and L.\ Sz\'ekely, Extremal problems for the Bondy-Chv\'{a}tal closure of a graph, in {\it Graphs, Matrices, and Designs}, ed.\ R.\ S.\ Rees, Marcel Dekker, 1993, pp.\ 73--83.

\bibitem{hb}
V.\ E.\ Hoggatt, Jr., and M.\ Bicknell, Palindromic compositions, {\it Fibonacci Quart.} {\bf 13} (1975) 350--356.

\bibitem{h}
B.\ Hopkins, Spotted tilings and $n$-color compositions, {\it Integers} {\bf 12B} (2012), Article A6.

\bibitem{ho}
B.\ Hopkins and S.\ Ouvry, Combinatorics of multicompositions, in {\it Combinatorial and Additive Number Theory IV}, ed.\ M.\ Nathanson, Springer, 2021, pp.\ 307--321.

\bibitem{hw}
B.\ Hopkins and H.\ Wang, Restricted color $n$-color compositions, {\it J.\ Comb.} {\bf 12} (2021) 355--377.

\bibitem{m}
P.\ MacMahon, {\it Combinatory Analysis}, Vol.\ 1, Cambridge University Press, 1915.

\bibitem{o}
OEIS Foundation Inc., {\it The On-Line Encyclopedia of Integer Sequences}, \url{https://oeis.org}, 2024.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A17; Secondary 05A15, 05A19, 11P81.

\noindent \emph{Keywords: } integer composition, $n$-color composition, recurrence relation, exact enumeration, bijective combinatorics.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A001333},
\seqnum{A001590}, 
\seqnum{A005314},
\seqnum{A034943}, and
\seqnum{A070550}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 26 2024; 
revised version received  October 9 2024.
Published in {\it Journal of Integer Sequences}, October 16 2024.

\bigskip
\hrule
\bigskip

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


\end{document}
