<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}}}

\newcommand{\C}{{\mathcal C}}
\newcommand{\A}{{\mathcal A}}
\newcommand{\G}{{\mathcal G}}
\newcommand{\E}{{\mathcal E}}
\newcommand{\Hl}{{\mathcal H}}
\newcommand{\D}{{\mathcal D}}
\newcommand{\T}{{\mathcal T}}

\makeatletter
\let\@@pmod\pmod
\DeclareRobustCommand{\pmod}{\@ifstar\@pmods\@@pmod}
\def\@pmods#1{\mkern4mu({\operator@font mod}\mkern 6mu#1)}
\makeatother

\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 New Restricted \texorpdfstring{$n$}{n}-Color \\
\vskip .1in Composition Functions}
\vskip 1cm
\large

Jarib R. Acosta, Yadira Caicedo, and Juan P. Poveda \\
Departamento de Matem\'aticas y Estad\'istica\\
Universidad del Tolima \\
Tolima  \\
Colombia\\
\href{mailto:jracostac@ut.edu.co}{\tt jracostac@ut.edu.co} \\
\href{mailto:nycaicedob@ut.edu.co}{\tt nycaicedob@ut.edu.co} \\
\href{mailto:jppovedac@ut.edu.co}{\tt jppovedac@ut.edu.co} \\
\ \\
Jos\'e L. Ram\'{\i}rez\\
Departamento de Matem\'aticas\\
 Universidad Nacional de Colombia\\
Bogot\'a\\
Colombia\\
\href{mailto:jlramirezr@unal.edu.co}{\tt jlramirezr@unal.edu.co}\\
\ \\
Mark Shattuck\footnote{Corresponding author.}\\
Institute for Computational Science\\
and\\
Faculty of Mathematics and Statistics\\
Ton Duc Thang University\\
Ho Chi Minh City\\
Vietnam\\
\href{mailto:shattuck@math.utk.edu}{\tt mark.shattuck@tdtu.edu.vn}\\



\end{center}

\vskip .2 in

\begin{abstract}
An $n$-color composition is one in which a part of size $m$ can come in $m$ colors (denoted by subscripts).  Let $\mathcal{C}(\nu)$ denote the set of $n$-color compositions of the positive integer $\nu$.  In this paper, we consider further modular restrictions on the subscripts of the parts within members of $\mathcal{C}(\nu)$.  We first count members of $\mathcal{C}(\nu)$ in which all parts have subscripts of the form $\ell a+b$, where $b$ and $\ell$ are fixed and $a \geq 0$ is arbitrary.  Generating function and explicit formulas are found for general $b$ and $\ell$ which extend earlier results when $\ell=2$ and $b \leq 3$.  We study the case $\ell=b-1$ in further detail and find that the corresponding subset of $\mathcal{C}(\nu)$ is in bijection with various classes of compositions.  Finally, we consider two related problems: one where the subscript restriction applies only to parts within a given modular class and another where the subscript of a part belongs to the same modular class mod $\ell$ as the part where $\ell$ is fixed.
\end{abstract}

\section{Introduction}
	
A \emph{composition} of a positive integer $\nu$ is a sequence of positive integers $\sigma=\{\sigma_1, \sigma_2,\dots, \sigma_r\}$ such that $\sigma_1+\sigma_2+\cdots + \sigma_r=\nu$. The summands $\sigma_i$ are called the \emph{parts} of $\sigma$ and $\nu$ is the \emph{weight} of $\sigma$. For example, the compositions of $4$ are
$$\{\texttt{4}\}, \, \{\texttt{3},\texttt{1}\}, \,\{\texttt{1},\texttt{3}\}, \,\{\texttt{2},\texttt{2}\}, \, \{\texttt{2},\texttt{1},\texttt{1}\}, \, \{\texttt{1},\texttt{2},\texttt{1}\}, \, \{\texttt{1},\texttt{1},\texttt{2}\}, \, \{\texttt{1},\texttt{1},\texttt{1},\texttt{1}\}.$$

Agarwal \cite{Aga} introduced a generalization of the concept of a composition known as an \emph{$n$-color composition} wherein a part of size $m\geq 1$ can come in one of $m$ different colors. The colors of the part $m$ are denoted by subscripts $m_1, m_2, \dots, m_m$. For example, the $n$-color compositions of $4$ are
\begin{align*}
&amp;\{\texttt{4}_\texttt{1}\},\, \{\texttt{4}_\texttt{2}\},\{\texttt{4}_\texttt{3}\},\{\texttt{4}_\texttt{4}\},\{\texttt{3}_\texttt{1},\texttt{1}_\texttt{1}\},\{\texttt{3}_\texttt{2},\texttt{1}_\texttt{1}\},
\{\texttt{3}_\texttt{3}, \texttt{1}_\texttt{1}\},   \{\texttt{1}_\texttt{1},\texttt{3}_\texttt{1}\},\{\texttt{1}_\texttt{1},\texttt{3}_\texttt{2}\},\{\texttt{1}_\texttt{1}, \texttt{3}_\texttt{3}\},\{\texttt{2}_\texttt{1},\texttt{2}_\texttt{1}\},\\
&amp;\{\texttt{2}_\texttt{1}, \texttt{2}_\texttt{2}\},\{\texttt{2}_\texttt{2}, \texttt{2}_\texttt{1}\},\{\texttt{2}_\texttt{2}, \texttt{2}_\texttt{2}\},\{\texttt{2}_\texttt{1},\texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}\},\{\texttt{2}_\texttt{2}, \texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}\}, \{\texttt{1}_\texttt{1},\texttt{2}_\texttt{1}, \texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1}, \texttt{2}_\texttt{2}, \texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}, \texttt{2}_\texttt{1}\},\\
&amp;\{\texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}, \texttt{2}_\texttt{2}\},\{\texttt{1}_\texttt{1},\texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}\}.
\end{align*}
   It is well-known that the total number of $n$-color compositions of $\nu$ is given by the Fibonacci number $F_{2\nu}$. Moreover, the number of $n$-color compositions of $\nu$ with exactly $m$ parts is the binomial coefficient $\binom{\nu+m-1}{2m-1}$. For further results about $n$-color compositions, see, e.g., \cite{Aga, Aga3, Coll, Guo1, Guo2, ManSha, Nar1, Nar3, Sach, Shap1, Shap2}.  In this paper, we study some new restrictions on $n$-color compositions  that generalize  previous results given by Sachdeva and Agarwal \cite{Sach}.

   The organization of this paper is as follows.  In the next section, we count the members of $\mathcal{C}(\nu)$ in which the subscripts on all parts are of the form $\ell a+b$ for some $a \geq 0$, where $b,\ell \geq 1$ are fixed, providing generating function and explicit formulas.  This extends recent work \cite{Sach} in the case $\ell=2$.  We consider further the case $\ell=b-1$, which yields several previously studied sequences from \cite{OEIS}, and find bijections between various restricted classes of binary words and compositions and the corresponding subset of $\mathcal{C}(\nu)$.  In the third section, we count members of $\mathcal{C}(\nu)$ in which only parts of the form $\ell a+b$ for some $a \geq 0$ satisfy a similar modular requirement with respect to their subscripts.  An explicit formula for the generating function is found which extends prior results \cite{Sach}.  Finally, a comparable formula can be given which counts members of $\mathcal{C}(\nu)$ in which parts of the form $\ell a+b$ where $a \geq 0$ and $1 \leq b \leq \ell$ must have subscripts of the same form.


\section{Generalized restricted \texorpdfstring{$n$}{n}-color compositions}
Given positive integers $\ell$ and $b$, let $\C_{\ell a + b}(\nu)$ denote the number of $n$-color compositions of $\nu$ into parts with subscripts of the form $\ell a +b$ for some integer  $a\geq 0$.   We also denote by $\C_{\ell a+ b}(m, \nu)$ the number of $n$-color compositions of $\nu$ into $m$ parts with subscripts of the form $\ell a +b$.

For example,  $\C_{3a + 1}(4)=9$, the compositions being
$$\{\texttt{4}_\texttt{1}\},\{\texttt{4}_\texttt{4}\},\{\texttt{3}_\texttt{1},\texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1}, \texttt{3}_\texttt{1}\},\{\texttt{2}_\texttt{1}, \texttt{2}_\texttt{1}\},\{\texttt{2}_\texttt{1},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1}, \texttt{2}_\texttt{1},\texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}, \texttt{2}_\texttt{1}\},\{\texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}\}.$$

\begin{theorem}\label{teo1}
Let $\mathcal{G}\C_{\ell a + b}(m, x)$  and  $\mathcal{G}\C_{\ell a + b}(x)$ denote  the generating functions for the sequences $\C_{\ell a + b}(m, \nu)$ and $\C_{\ell a + b}(\nu)$, respectively.  Then we have
\begin{align*}
\mathcal{G}\C_{\ell a + b}(m, x)&amp;=\left(\frac{x^{b}}{(1-x)(1-x^{\ell})}\right)^m, \\
\mathcal{G}\C_{\ell a + b}(x)&amp;=\frac{x^{b}}{1-x-x^\ell+x^{\ell+1}-x^b}.
\end{align*}
\end{theorem}
\begin{proof}
Let $\sigma=\sigma_1\cdots\sigma_m$ be a non-empty $n$-color composition having $m$ parts where each subscript is of the form $\ell a +b$ for some $a\geq 0$.   If $\sigma_j=i$ with  $i\geq b$, then $\sigma_j$ contributes to the generating function the term $w_ix^i$, where $$w_i=\left\lfloor \frac{i-b+\ell}{\ell}\right\rfloor,$$
while if $i&lt;b$, then it fails to contribute.

Note that the generating function of the sequence
 $$\left\{w_i\right\}_{i\geq 0}=\left\{\underbrace{0, \dots, 0}_{b}, \underbrace{1, \dots, 1}_{\ell}, \underbrace{2, \dots, 2}_{\ell}, \dots  \right\}$$
 is given by
 $$\frac{x^b}{(1-x)(1-x^{\ell})}.$$
 Therefore,
 $$ \mathcal{G}\C_{\ell a + b}(m, x)=\left(\sum_{i\geq 0}w_ix^i \right)^m=\left(\frac{x^b}{(1-x)(1-x^{\ell})} \right)^m.$$
 Finally, summing the last expression over $m \geq 1$, we get
 $$\mathcal{G}\C_{\ell a + b}(x)=\frac{\frac{x^b}{(1-x)(1-x^{\ell})} }{1-\frac{x^b}{(1-x)(1-x^{\ell})} }=\frac{x^{b}}{1-x-x^\ell+x^{\ell+1}-x^b}.$$
 \end{proof}

We have the following combinatorial formula for the sequence  $\C_{\ell a+ b}(m, \nu)$.

\begin{theorem}\label{teo1b}
The sequence $\C_{\ell a+ b}(m, \nu)$ is given by  the expression
$$\C_{\ell a+ b}(m, \nu)=\sum_{i=0}^{\left \lfloor\frac{\nu-bm}{\ell} \right\rfloor}\binom{m+i-1}{m-1}\binom{\nu-\ell i+m(1-b)-1}{m-1}.$$
Moreover,
$\C_{\ell a + b}(\nu)=\C_{\ell a + b}(\nu-1) + \C_{\ell a + b}(\nu-\ell) - \C_{\ell a + b}(\nu-\ell-1) + \C_{\ell a + b}(\nu-b)$ when $\nu&gt; \max\{\ell +1, b\}$.
\end{theorem}
\begin{proof}
By Theorem \ref{teo1}, we have
\begin{align*}
\mathcal{G}\C_{\ell a + b}(m, x)&amp;=\left(\frac{x^{b}}{(1-x)(1-x^{\ell})}\right)^m\\
&amp;=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\binom{m+i-1}{i}\binom{m+j-1}{j} x^{j+i\ell+ bm}.
\end{align*}
Taking $t=j+\ell i + bm$ gives
\begin{align*}
\mathcal{G}\C_{\ell a + b}(m, x)&amp;=\sum_{i=0}^{\infty}\sum_{t=i\ell +bm}^{\infty}\binom{m+i-1}{m-1}\binom{t-\ell i+m(1-b)-1}{m-1} x^{t}.
\end{align*}
By comparing the $\nu$-th coefficient of both sides of the last equation, we obtain the desired result.   The recurrence relation follows from the generating function formula for $\mathcal{G}\C_{\ell a + b}(x)$  given in Theorem \ref{teo1}.
\end{proof}

\begin{remark} Setting $\ell=b=1$ in Theorem \ref{teo1b}, and using the binomial identity \cite[Formula 5.26]{Concrete}, recovers the fact that there are $\binom{\nu+m-1}{2m-1}$ $n$-color compositions of $\nu$ with exactly $m$ parts and thus $F_{2\nu}$ altogether with no restriction as to the number of parts.
\end{remark}

By setting $\ell=2$ and $b=1$, we have the following corollary (see Theorem 2.1 of \cite{Sach}).
 \begin{corollary}
The generating functions for the number of $n$-color compositions  of $\nu$ into $m$ parts with odd subscripts  and  for the total  number of $n$-color compositions  of $\nu$  with odd subscripts are
\begin{align*}
\mathcal{G}\C_{2a + 1}(m, x)&amp;=\left(\frac{x}{(1-x)(1-x^{2})}\right)^m=\left(\frac{x}{(1+x)(1-x)^2}\right)^m,\\
\mathcal{G}\C_{2a + 1}(x)&amp;=\frac{x}{1-2x-x^2+x^{3}}.
\end{align*}
Moreover,
$$\C_{2a+ 1}(m, \nu)=\sum_{i=0}^{\left \lfloor\frac{\nu-m}{2} \right\rfloor}\binom{m+i-1}{m-1}\binom{\nu-2i -1}{m-1}$$
and
$\C_{2a+ 1}(\nu)=2\C_{2a + 1}(\nu-1) + \C_{2a + 1}(\nu-2) - \C_{2a + 1}(\nu-3)$ for $\nu&gt;3$, with the initial values $\C_{2a+ 1}(1)=1, \C_{2a+ 1}(2)=2, \C_{2a+ 1}(3)=5$.
\end{corollary}

Letting $\ell=2$ and $b=2$ yields the following corollary (see Theorem 2.3 of \cite{Sach}).

\begin{corollary}
The generating functions for the number of $n$-color compositions  of $\nu$ into $m$ parts with even subscripts  and  for the total  number of $n$-color compositions  of $\nu$  with even subscripts are
\begin{align*}
\mathcal{G}\C_{2a+2}(m, x)&amp;=\left(\frac{x^{2}}{(1-x)(1-x^{2})}\right)^m=\left(\frac{x^{2}}{(1+x)(1-x)^2}\right)^m,\\
\mathcal{G}\C_{2a+2}(x)&amp;=\frac{x^{2}}{1-x-2x^2+x^{3}}.
\end{align*}
Moreover,
$$\C_{2 a+ 2}(m, \nu)=\sum_{i=0}^{\left \lfloor\frac{\nu-2m}{2} \right\rfloor}\binom{m+i-1}{m-1}\binom{\nu-2i -m -1}{m-1}$$
and
$\C_{2a + 2}(\nu)=\C_{2a + 2}(\nu-1) + 2\C_{2a + 2}(\nu-2) - \C_{2a + 2}(\nu-3)$ for $\nu&gt;3$,  with the initial values $\C_{2a+ 2}(1)=0, \C_{2a+ 2}(2)=1, \C_{2a+ 2}(3)=1$.
\end{corollary}


Letting $\ell=2$ and $b=3$ yields the further corollary (see Theorem 2.2 of \cite{Sach}).
\begin{corollary}
The generating functions for the number of $n$-color compositions  of $\nu$ into $m$ parts with odd  subscripts $&gt;1$ and  for the total  number of $n$-color compositions  of $\nu$  with odd subscripts $&gt;1$ are
\begin{align*}
\mathcal{G}\C_{2a + 3}(m, x)&amp;=\left(\frac{x^3}{(1+x)(1-x)^2}\right)^m,\\
\mathcal{G}\C_{2a + 3}(x)&amp;=\frac{x^{3}}{1-x-x^{2}}.
\end{align*}
Moreover,
$$\C_{2a + 3}(m, \nu)=\sum_{i=0}^{\left \lfloor\frac{\nu-3m}{2} \right\rfloor}\binom{m+i-1}{m-1}\binom{\nu-2i -2m -1}{m-1}$$
and
$\C_{2a + 3}(\nu)=\C_{2a + 3}(\nu-1) + \C_{2a + 3}(\nu-2)$ for $\nu&gt;3$,  with the initial values $\C_{2a+ 3}(1)=0, \C_{2a+ 3}(2)=0, \C_{2a+ 3}(3)=1$.
\end{corollary}


When $\ell=3$, we obtain some known sequences from the OEIS \cite{OEIS}.  In Table \ref{ta1}, we give the first several non-zero values.

\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|} \hline
$\ell$ &amp; $b$ &amp; Sequence $\C_{\ell a + b}(\nu)$  &amp; A-Sequence \\ \hline \hline
3 &amp; 1 &amp;1, 2, 4, 9, 19, 40, 85, 180, 381, 807, 1709, 3619, 7664, 16230,
34370   &amp; \seqnum{A052908} \\ \hline
3 &amp; 2 &amp; 1, 1, 2, 4, 6, 11, 19, 32, 56, 96, 165, 285, 490, 844, 1454, 2503,
4311  &amp; \seqnum{A116732} \\ \hline
3 &amp; 3 &amp; 1, 1, 1, 3, 4, 5, 10, 15, 21, 36, 56, 83, 134, 210, 320, 505, 791,
1221  &amp;  \seqnum{A176848} \\ \hline
\end{tabular}\smallskip
\caption{Some particular cases for $\ell=3$.}
\label{ta1}
\end{table}

Note that the sequence \seqnum{A052908} does not have a combinatorial interpretation listed.  For the sequence \seqnum{A116732}, our combinatorial interpretation differs from the one given.  Let $\A$ be the set of compositions  with parts in $\{\texttt{1}, \texttt{2}, \texttt{3}\}$ such that  the order of adjacent \texttt{1}'s and \texttt{3}'s is unimportant. Let $a(n)$ be the number of elements in $\A$ of weight $n$. For example, $a(6)=19$, where the compositions are
\begin{align*}
&amp;\{\texttt{3},\texttt{3}\},\{\texttt{3},\texttt{2},\texttt{1}\},\{\texttt{3},\texttt{1},\texttt{2}\}, \{\texttt{2},\texttt{3},\texttt{1}\}, \{\texttt{1},\texttt{2},\texttt{3}\}, \{\texttt{3},\texttt{1},\texttt{1},\texttt{1}\}, \{\texttt{2},\texttt{2},\texttt{2}\}, \{\texttt{2},\texttt{2},\texttt{1},\texttt{1}\}, \{\texttt{2},\texttt{1},\texttt{2},\texttt{1}\},\\
&amp;\{\texttt{2},\texttt{1},\texttt{1},\texttt{2}\}, \{\texttt{1},\texttt{2},\texttt{2},\texttt{1}\}, \{\texttt{1},\texttt{2},\texttt{1},\texttt{2}\}, \{\texttt{1},\texttt{1},\texttt{2},\texttt{2}\}, \{\texttt{2},\texttt{1},\texttt{1},\texttt{1},\texttt{1}\}, \{\texttt{1},\texttt{2},\texttt{1},\texttt{1},\texttt{1}\}, \{\texttt{1},\texttt{1},\texttt{2},\texttt{1},\texttt{1}\},\\
 &amp;\{\texttt{1},\texttt{1},\texttt{1},\texttt{2},\texttt{1}\}, \{\texttt{1},\texttt{1},\texttt{1},\texttt{1},\texttt{2}\}, \{\texttt{1},\texttt{1},\texttt{1},\texttt{1},\texttt{1},\texttt{1}\}.
\end{align*}

 \begin{theorem}\label{a=C}
 For $n\geq 0$, $a(n)=\C_{3a + 2}(n+2)$.
 \end{theorem}
\begin{proof}
Let $w$ be a composition in $\A$. Then $w$ is either an integer  partition (non-ordered composition) with parts in $\{\texttt{1}, \texttt{3}\}$ or can be factorized as $p\, 2 \,  w'$, where $p$ is  a partition  with parts in  $\{\texttt{1}, \texttt{3}\}$  and $w' \in \A$. Thus, the generating function $A(x)$ of the sequence $a(n)$ satisfies the relation
$$A(x)=P_{1,3}(x) + P_{1,3}(x) x^2 A(x),$$
where $P_{1,3}(x)$ counts integer partitions with parts in $\{\texttt{1}, \texttt{3}\}$.
Since
$$P_{1,3}(x)=\frac{1}{(1-x)(1-x^3)},$$
we have
$$A(x)=\frac{1}{1 - x - x^2 - x^3 + x^4}.$$
Finally, by Theorem \ref{teo1}, $$\mathcal{G}\C_{3a + 2}(x)=x^2A(x),$$
which yields the desired result upon comparing $n$-th coefficients.
\end{proof}

Let $b(n)$ be the number of compositions of $n$ where each part of size $j$ for $j \geq 1$ comes in $\left\lfloor j/3\right\rfloor$ kinds (sequence \seqnum{A176848}). For example, $b(7)=4$, the enumerated compositions being $\{\texttt{7}_x\}, \{\texttt{7}_y\}, \{\texttt{3}_x,\texttt{4}_x\}, \{\texttt{4}_x,\texttt{3}_x\}$.
It is clear from the definitions that $b(n)=\C_{3a + 3}(n)$ for $n \geq 1$.

We now give a bijective proof of the prior theorem.\medskip

\noindent\textbf{Combinatorial proof of Theorem \ref{a=C}.}\medskip

Let $\mathcal{A}_n$ and $\mathcal{C}_n$ denote the set of compositions enumerated by $a(n)$ and $\mathcal{C}_{3a+2}(n)$, respectively.  We will define a bijection between $\mathcal{A}_n$ and $\mathcal{C}_{n+2}$ for $n \geq 0$.  Let us assume that 3 always precedes 1 whenever there is an adjacency of the two letters within a member of $\mathcal{A}_n$.  Let $\lambda \in \mathcal{A}_n$.  First assume $\lambda$ contains no $2$'s.  Then we may write $\lambda=3^i1^j$, where $i,j \geq 0$ with $3i+j=n$.  In this case, we map $\lambda$ to the colored composition $\lambda'=(3i+j+2)_{3i+2}$ of $n+2$ containing a single part.  So assume $\lambda$ contains at least one $2$, in which case we may write
$$\lambda=3^{i_0}1^{j_0}2^{a_1}3^{i_1}1^{j_1}2^{a_2}3^{i_2}1^{j_2}\cdots2^{a_r}3^{i_r}1^{j_r},$$
where all exponents are non-negative, $r \geq 1$, $a_1,\ldots,a_r \geq 1$, and $i_k+j_k \geq 1$ for $1 \leq k \leq r-1$. In this case, we let
$$\lambda'=(3i_0+j_0+2)_{3i_0+2},(2_2)^{a_1-1},(3i_1+j_1+2)_{3i_1+2},\ldots,(2_2)^{a_r-1},(3i_r+j_r+2)_{3i_r+2},$$
where $(2_2)^t$ denotes a run of the part $2_2$ of length $t$.

Note that $\lambda'$ contains $r+1$ parts and indeed belongs to $\mathcal{C}_{n+2}$.  Also, while it is possible for the first or the last part of $\lambda'$ to be $2_2$, all parts of the form $(3i_k+j_k+2)_{3i_k+2}$ where $1 \leq k \leq r-1$ are greater than 2.  Furthermore, since $j_k \geq 0$ for $0 \leq k \leq r$, arbitrary differences can occur between the part sizes and subscripts.  Thus, the mapping $\lambda \mapsto \lambda'$ may be reversed and hence is a bijection between $\mathcal{A}_n$ and $\mathcal{C}_{n+2}$, as desired, upon decomposing members of $\mathcal{C}_{n+2}$ in the same way $\lambda'$ was above.  \hfill \qed


\subsection{The case \texorpdfstring{$\ell=b-1$}{l=b-1}}

In this subsection, we provide additional combinatorial interpretations for the sequence  $\C_{\ell a + \ell +1}(n)$, where $\ell \geq 1$.  In Table \ref{tab2}, we give the first several non-zero values of these sequences for $2 \leq \ell \leq 6$.


\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|c|} \hline
$\ell$ &amp; $b$ &amp; Sequence $\C_{\ell a + b}(\nu)$  &amp; A-Sequence \\ \hline \hline
2 &amp; 3 &amp;1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597    &amp;  \seqnum{A000045} \\ \hline
3 &amp; 4 &amp;1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406,
595   &amp; \seqnum{A000930} \\ \hline
4 &amp; 5 &amp; 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181,
250  &amp; \seqnum{A003269} \\ \hline
5 &amp; 6 &amp; 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106,
140  &amp; \seqnum{A003520}  \\ \hline
6 &amp; 7 &amp; 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 34, 43, 55, 71,
 92  &amp; \seqnum{A005708}\\ \hline
\end{tabular}\smallskip
\caption{Some particular cases of $\ell=b-1$.}
\label{tab2}
\end{table}
Let $F_\ell(n):=\C_{\ell a + \ell +1}(n)$. By Theorem \ref{teo1}, we have

$$F_\ell(x):=\sum_{n=0}^\infty F_\ell(n) x^n = \frac{x^{\ell+1}}{1-x-x^\ell}.$$
Moreover,
$F_\ell(n)=F_\ell(n-1) + F_\ell(n-\ell)$ for $n&gt; \ell +1$, with the initial values $F_\ell(\ell+1)=1$ and $F_\ell(n)=0$ for $n \in [\ell]=\{1,2,\ldots,\ell\}$. For $\ell =2$, it is clear that the sequence $F_2(n)$  coincides with the Fibonacci numbers, i.e., $F_2(n)=F_{n-2}$ for $n \geq 2$.  Moreover, $F_3(n)$  is seen to correspond to the Narayana sequence (cf.\ \cite{RamSir}).


Let $\E_\ell$ be the set of compositions into parts $1$ and $\ell$, where $\ell \geq 2$. Let $e_\ell(n)$ denote the number of elements in $\E_\ell$ of weight $n$. Chinn and Heubach \cite{CH} studied this family of compositions and, in particular, found
$$E_\ell(x):=\sum_{n=0}^{\infty}e_\ell(n)x^n=\frac{1}{1-x-x^\ell}.$$
Then  $x^{\ell+1} E_\ell(x)=F_\ell(x)$ and we have the following result.
\begin{theorem}\label{F=e}
For $n\geq 0$, $F_\ell(n+\ell+1)=e_\ell(n)$.
\end{theorem}

Let $\Hl_\ell$ be the set of compositions into parts greater than or equal to $\ell$. Let $h_\ell(n)$ be the number of  elements in  $\Hl_\ell$ of weight $n$. It is not difficult to show that (see, for example, \cite[Theorem 3.13]{Mansour})
$$H_\ell(x):=\sum_{n=0}^{\infty}h_\ell(n)x^n=\frac{1}{1-(x^\ell + x^{\ell+1}+\cdots)}=\frac{1 - x}{1 - x - x^\ell}.$$
Therefore, we have the following relation.
\begin{theorem}\label{F=h}
For $n\geq 1$, $F_\ell(n+1)=h_\ell(n)$.
\end{theorem}

Let $\G_\ell$ be the set of binary words such that between any two successive ones there are at least $\ell-1$ zeros. Let $g_\ell(n)$ be the number of  words  in  $\G_\ell$ of length $n$.  Let $w$ be a binary word in  $\G_\ell$ of length $n&gt; \ell$. Then $w$ can be decomposed as $w=0w_1$ or $w=1\underbrace{0 \cdots 0}_{\ell-1}w_2$, where $w_1, w_2 \in \G_\ell$, which implies $g_\ell(n)=g_\ell(n-1)+g_\ell(n-\ell)$ for all $n&gt;\ell$.  Thus, this sequence satisfies the same recurrence relation as $F_\ell(n)$. Note that $g_\ell(n)=n+1$ if $n \in [\ell]$, which follows from the definitions.  Since $F_\ell(n+\ell)=1$ if $n \in [\ell]$, applying the recurrence for $F_\ell(n)$ implies $F_\ell(n+2\ell)=n+1$ for $n \in [\ell]$.  Comparing the recurrences and initial values gives the following relation.
\begin{theorem}\label{Fg}
For $n\geq 0$, $F_\ell(n+2\ell)=g_\ell(n)$.
\end{theorem}

We conclude this section by providing bijective proofs of the last three results.\medskip

\noindent\textbf{Combinatorial proofs of Theorems \ref{F=e} and \ref{F=h}.}\medskip

Let $\mathcal{E}_\ell(n)$ denote the set of compositions of $n$ with parts $1$ and $\ell$ and $\mathcal{F}_{\ell}(n)$ the set of colored compositions enumerated by $F_\ell(n)$.  We define a mapping $f: \mathcal{E}_\ell(n) \rightarrow \mathcal{F}_{\ell}(n+\ell+1)$ as follows.  If $\lambda=1^{n-b\ell}\ell^b$, where $0 \leq b \leq \lfloor n/\ell \rfloor$, then let $f(\lambda)=((b+1)\ell+n-b\ell+1)_{(b+1)\ell+1}$.  Otherwise, we have
$$\lambda=1^{a_0}\ell^{b_1}1^{a_1}\cdots\ell^{b_r}1^{a_r}\ell^{b_{r+1}},$$
where $r \geq 1$, $a_0 \geq 0$, $a_i,b_i \geq 1$ if $1 \leq i \leq r$ and $b_{r+1}\geq 0$.  In this case, let
$$f(\lambda)=(b_1\ell+a_0+1)_{b_1\ell+1},(b_2\ell+a_1)_{b_2\ell+1},\ldots,(b_r\ell+a_{r-1})_{b_r\ell+1},((b_{r+1}+1)\ell+a_r)_{(b_{r+1}+1)\ell+1}.$$
Note that $f(\lambda)$ contains $r+1$ parts and indeed belongs to $\mathcal{F}_{\ell}(n+\ell+1)$ (a $1$ not accounted for by $\lambda$ occurs in the first part and there is an extra $\ell$ in the last part).  Observe further that the last part of $f(\lambda)$ has subscript greater than or equal to $\ell+1$ depending on whether the last part of $\lambda$ is $\ell$ or $1$.  Upon considering the number of parts in a member of $\mathcal{F}_{\ell}(n+\ell+1)$, the mapping $f$ is seen to be reversible and hence yields the desired bijection.

To show Theorem \ref{F=h}, let $\mathcal{H}_\ell(n)$ denote the set of compositions of $n$ having parts of size $\ell$ or more.  We define $g: \mathcal{H}_\ell(n) \rightarrow \mathcal{F}_\ell(n+1)$ for $n \geq 1$ as follows. If $n \in [\ell-1]$, then both sets are empty, so assume $n \geq \ell$.  Then we may express $\lambda \in \mathcal{H}_\ell(n)$ as
$$\lambda=x_1\ell^{a_1}x_2\ell^{a_2}\cdots x_r\ell^{a_r},$$
where $r \geq 1$, $x_1 \geq \ell$, $x_i \geq \ell+1$ if $i&gt;1$ and $a_i\geq0$ for all $i$.  Let
$$g(\lambda)=(a_1\ell+x_1+1)_{(a_1+1)\ell+1},(a_2\ell+x_2)_{(a_2+1)\ell+1},\ldots,(a_r\ell+x_r)_{(a_r+1)\ell+1}.$$
One may verify that the mapping $g$ is a bijection, which completes the proof. \hfill \qed \medskip

\noindent\textbf{Combinatorial proof of Theorem \ref{Fg}.}\medskip

Let $\mathcal{G}_\ell(n)$ denote the set of binary words enumerated by $g_\ell(n)$.  We define a mapping $f: \mathcal{G}_\ell(n) \rightarrow \mathcal{F}_\ell(n+2\ell)$ in several steps as follows.  Let $\lambda=\lambda_1\lambda_2\cdots\lambda_n \in \mathcal{G}_\ell(n)$ and first assume $n \in [\ell]$.  In this case, let
 $$f(\lambda)=\begin{cases}
 (n+2\ell)_{\ell+1}, &amp; \text{ if }  \lambda=0^n;\\
 (n-s+\ell)_{\ell+1},(s+\ell)_{\ell+1},&amp; \text{ if } \lambda=0^s10^{n-1-s}, \text{ where } 1 \leq s \leq n-1;\\
 (n+2\ell)_{2\ell+1}, &amp; \text{ if } \lambda=10^{n-1}.
 \end{cases}
 $$
Henceforth, assume $n&gt;\ell$.  We will also assume $\ell &gt; 1$, as the adjustments necessary in the $\ell=1$ case will be apparent. Note that $\lambda \in \mathcal{G}_\ell(n)$ may start with an initial (possibly empty) run of 0's with the remainder of $\lambda$ being decomposed into sections of the form $u=10^{\ell-1}$ (1 followed by $\ell-1$ 0's) and $v=10^{m-1}$ where $m\geq \ell+1$ is arbitrary (to be specified).  Furthermore, it is possible for $\lambda$ to end in a section $w$ of the form $w=10^p$, where $0 \leq p \leq \ell-2$.

First assume $\lambda$ contains no section of the form $v$ above.  Then either
\begin{equation}\label{form1}
\lambda=0^{n-i\ell }u^i, \qquad 0 \leq i \leq \lfloor n/\ell \rfloor,
\end{equation}
or
\begin{equation}\label{form2}
\lambda=0^{n-p-1-i\ell }u^i w, \qquad 0 \leq p \leq \ell-2~\text{ and }~0 \leq i \leq \lfloor (n-p-1)/\ell \rfloor,
\end{equation}
where $w=10^p$.  We define $f$ in this case by considering whether or not $n$ is divisible by $\ell$.  If $\ell$ divides $n$, then let $f(\lambda)=(n+2\ell)_{(i+1)\ell+1}$, if $\lambda$ is of the form \eqref{form1}, and let
$$f(\lambda)=(\ell+p+1)_{\ell+1},((i+1)\ell+n-p-1-i\ell)_{(i+1)\ell+1},$$
if of form \eqref{form2}. If $\ell$ does not divide $n$, then we define $f(\lambda)$ the same way as before provided $\lambda$ is not of the form \eqref{form2} with $n-p-1 = i\ell$.  Note that $n-p-1=i\ell$ corresponds to exactly one $\lambda$ in \eqref{form2} since $0 \leq p \leq \ell-2$.  We set $f(\lambda)=(n+2\ell)_{q\ell+1}$ in this case where $q=\lfloor n/\ell\rfloor +2$ (note that $q\ell+1 \leq n+2\ell$ if and only if $\ell$ does not divide $n$).  Observe that in either case $f$ maps the members of $\mathcal{G}_\ell(n)$ not containing a $v$ section in a one-to-one manner to the subset of $\mathcal{F}_\ell(n+2\ell)$ whose members either have one part or have two parts where the first part is less than $2\ell$.

Assume henceforth that $\lambda$ contains at least one section of the form $v$ above.  Then we may write
\begin{equation}\label{form3}
\lambda=0^ju^{i_1}v_1\cdots u^{i_r}v_ru^{i_{r+1}},
\end{equation}
where $r \geq 1$, $j,i_1,\ldots,i_{r+1}\geq 0$, and $v_i=10^{m_i-1}$ with $m_i\geq \ell+1$ for $1 \leq i \leq r$, or
\begin{equation}\label{form4}
\lambda=0^ju^{i_1}v_1\cdots u^{i_r}v_ru^{i_{r+1}}w,
\end{equation}
with all the same restrictions as before and $w=10^p$ for some $0 \leq p \leq \ell-2$.  If $\lambda$ is of the form \eqref{form3}, then let
$$f(\lambda)=((i_1+2)\ell+j)_{(i_1+1)\ell+1},(i_2\ell+m_1)_{(i_2+1)\ell+1},\ldots,(i_{r+1}\ell+m_r)_{(i_{r+1}+1)\ell+1}.$$
Observe that $r \geq 1$ implies $f(\lambda)$ contains at least two parts in this case and $m_i\geq \ell+1$ for all $i$ implies the size of the part always exceeds the size of the subscript (with the first part of size at least $2\ell$).

Now suppose $\lambda$ is of form \eqref{form4}.  To define $f$, we consider cases on $j$.  If $j \geq 1$ in \eqref{form4}, then let
$$f(\lambda)=(\ell+p+1)_{\ell+1},((i_1+1)\ell+j)_{(i_1+1)\ell+1},(i_2\ell+m_1)_{(i_2+1)\ell+1},\ldots,(i_{r+1}\ell+m_r)_{(i_{r+1}+1)\ell+1}.$$
Note $f(\lambda)$ here must contain at least three parts and therefore this covers the remaining cases where the first part is less than $2\ell$.  If $j=0$ in \eqref{form4}, then let
$$f(\lambda)=((i_1+2)\ell+p+1)_{(i_1+2)\ell+1},(i_2\ell+m_1)_{(i_2+1)\ell+1},\ldots,(i_{r+1}\ell+m_r)_{(i_{r+1}+1)\ell+1}.$$
Notice that this covers the remaining $\rho \in \mathcal{F}_\ell(n+2\ell)$ in which the first part of $\rho$ is at least $2\ell$ with $\rho$ containing at least two parts.  The inverse of $f$ can then be constructed (we leave the details to the reader) in a composite manner in much the same way as $f$ was above upon considering the number of parts and whether or not the first part is at least $2\ell$.  \hfill \qed

 \section{Subscript restrictions only on certain parts}
 Given  integers $\ell, \ell', b, b' \geq  1$, let $\D_{\ell a + b}^{\ell'a'+b'}(\nu)$ denote the number of $n$-color compositions of $\nu$ such that the parts of the form  $\ell a +b$ for some $a \geq 0$  have only subscripts of the form $\ell' a' + b'$ for some  $a' \geq 0$.  Additionally, we denote by $\D_{\ell a + b}^{\ell'a'+b'}(m, \nu)$ the number of such $n$-color compositions of $\nu$ that have exactly $m$ parts.

For example,  $\D_{4a + 3}^{3a'+1}(3)=6$, the compositions being
\begin{align*}
\{\texttt{3}_\texttt{1}\},\{\texttt{2}_\texttt{1},\texttt{1}_\texttt{1}\},\{\texttt{2}_\texttt{2},\texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1},\texttt{2}_\texttt{1}\},\{\texttt{1}_\texttt{1},\texttt{2}_\texttt{2}\},\{\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1}\}.
   \end{align*}

\begin{theorem}\label{teo2}
Let $\mathcal{G}\D_{\ell a + b}^{\ell' a' + b'}(m, x)$  and  $\mathcal{G}\D_{\ell a + b}^{\ell' a' + b'}(x)$ denote  the generating functions for the sequences $\D_{\ell a + b}^{\ell'a'+b'}(m, \nu)$ and $\D_{\ell a + b}^{\ell'a'+b'}(\nu)$, respectively.  Then we have
\begin{align*}
\mathcal{G}\D_{\ell a + b}^{\ell' a' + b'}(m, x)&amp;=\left(x^bH(x^\ell) + P(x)+\sum_{i=1,~i \not\equiv b\pmod*{\ell}}^\ell \frac{i+(\ell-i)x^\ell}{(1-x^\ell)^2}x^i \right)^m, \\
\mathcal{G}\D_{\ell a + b}^{\ell' a' + b'}(x)&amp;=\frac{x^bH(x^\ell) + P(x)+\sum_{i=1,~i \not\equiv b\pmod*{\ell}}^\ell \frac{i+(\ell-i)x^\ell}{(1-x^\ell)^2}x^i}{1-\left(x^bH(x^\ell) + P(x)+\sum_{i=1,~i \not\equiv b\pmod*{\ell}}^\ell \frac{i+(\ell-i)x^\ell}{(1-x^\ell)^2}x^i\right)},
\end{align*}
where $H(x)$ is the generating function of the sequence
 $$h_n=\begin{cases}
 \left\lfloor \frac{\ell n + b -b'}{\ell'}\right\rfloor + 1, &amp; \text{ if }  \ell n + b\geq b' \text{ and } n \geq 0;\\
 0,&amp; \text{otherwise},
 \end{cases}
 $$
and $P(x)$ is the polynomial given by
$$P(x)=\sum_{\substack{ i \equiv b \pmod*{\ell}\\ 0\leq i &lt; b}} i x^i.$$
\end{theorem}
\begin{proof}
Summing the first expression over $m \geq 1$ gives the second, so we need only prove the first. Let $\sigma=\sigma_1\sigma_2\cdots \sigma_m$ be a non-empty $n$-color composition having $m$ parts such that  parts of the form  $\ell a +b$  where $a \geq 0$ have only subscripts of the form $\ell' a' + b'$ where $a'\geq0$.  First assume $\sigma_j \equiv b$ (mod $\ell$) and suppose $\sigma_j=r=\ell a+b$. If $a \geq 0$ and $r \geq b'$, then $\sigma_j$ contributes to the generating function a $w_ax^r$ term, where $$w_a=\left\lfloor \frac{\ell a + b-b'}{\ell'}\right\rfloor+1.$$
If $a\geq0$ and $r&lt;b'$, then there are no possible such parts for otherwise the index would exceed the part (note that this case can occur only if $b&lt;b'$).

If $a&lt;0$, then $\sigma_j=r&lt;b$ and there is a contribution to the generating function of $rx^r$ per the definitions, and combining all such $r$ yields the polynomial $P(x)$ defined above.  If $\sigma_j \not\equiv b$ (mod $\ell$), then there is again a contribution of $r x^r$. Thus, for each $i \in [\ell]$ such that $ i \not\equiv b$ (mod $\ell$), we have a total contribution of
\begin{align*}
&amp;ix^i+(\ell+i)x^{\ell+i}+(2\ell+i)x^{2\ell+i}+\cdots\\
&amp;=ix^i(1+x^\ell+x^{2\ell}+\cdots)+\ell x^i(x^\ell+2x^{2\ell}+3x^{3\ell}+\cdots)\\
&amp;=\frac{ix^i}{1-x^\ell}+\ell x^i\left[\frac{y}{(1-y)^2}\right]_{y=x^\ell}=\frac{ix^i}{1-x^\ell}+\frac{\ell x^{i+\ell}}{(1-x^\ell)^2},
\end{align*}
which gives the final part of the formula for $\mathcal{G}\D_{\ell a + b}^{\ell' a' + b'}(m, x)$ above.
\end{proof}

For example, the generating function for the sequence $\D_{3a +7}^{4a'+3}(m, \nu)$ is given by

\begin{align*}
\mathcal{G}\D_{3a +7}^{4a'+3}(m, x)=\left(x^7H(x^3) + x + 4x^4+\frac{\left(2+ x^3\right)}{\left(1-x^3\right)^2}x^2 + \frac{3}{\left(1-x^3\right)^2}x^3\right)^m,
\end{align*}
where $H(x)=\frac{2 + x^2 + x^3 - x^4}{(1-x)^2 \left(1 + x + x^2 + x^3\right)}$.
Note that $H(x)$ is the generating function for the sequence
$$\{2, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10, 11, 11, 12, 13, 14, 14, 15, 16,
17, 17, 18, 19, 20, 20, 21, 22,\dots\}.$$
Moreover, \footnotesize
\begin{align*}
&amp;\mathcal{G}\D_{3a +7}^{4a'+3}(x)\\
&amp;=\frac{-3 x^{19}+2 x^{16}-x^{14}-3 x^{12}-3
   x^{11}-3 x^9-3 x^8+2 x^7-3 x^6-3 x^5-3 x^4-3
   x^3-2 x^2-x}{3 x^{19}-2
   x^{16}-x^{15}+x^{14}+4 x^{12}+3 x^{11}+3
   x^9+3 x^8-2 x^7+3 x^6+3 x^5+3 x^4+4 x^3+2
   x^2+x-1} \\
 &amp;=x+3 x^2+8 x^3+21 x^4+55 x^5+144 x^6+372 x^7+977x^8+2549 x^9+6647
   x^{10}+\cdots.
\end{align*}
\normalsize
For example, $\D_{3a +7}^{4a'+3}(7)=372$, as all $n$-color compositions of $n=7$ are counted except
$$ \{\texttt{7}_\texttt{1}\},  \{\texttt{7}_\texttt{2}\},   \{\texttt{7}_\texttt{4}\}, \{\texttt{7}_\texttt{5}\}, \{\texttt{7}_\texttt{6}\}. $$

\begin{remark} Taking all of the relevant parameters to be one in Theorem \ref{teo2} gives
$$\mathcal{G}\D_{a + 1}^{a' + 1}(m, x)=\frac{x^m}{(1-x)^{2m}}, \qquad m \geq 1,$$
and
$$\mathcal{G}\D_{a + 1}^{a' + 1}(x)=\frac{x}{1-3x+x^2},$$
which are the generating functions for the number with $m$ parts and the total number of $n$-color compositions of $\nu$ for $\nu \geq 1$, respectively.
\end{remark}

By setting $\ell=2=\ell'$ in Theorem \ref{teo2}, we have the following corollaries.
 \begin{corollary}[Theorem 2.4 of \cite{Sach}]
The generating functions for the number of $n$-color compositions  of $\nu$ into $m$ parts such that the odd parts have only even subscripts and for the total  number of $n$-color compositions  of $\nu$  such that the odd parts have only even subscripts are
\begin{align*}
\mathcal{G}\D_{2a+1}^{2a'+2}(m, x)&amp;=\left(\frac{2x^2+x^3}{(1-x^{2})^2}\right)^m,\\
\mathcal{G}\D_{2a+1}^{2a'+2}(x)&amp;=\frac{2x^2+x^3}{1-4x^2 -x^3  + x^4}.
\end{align*}
\end{corollary}

 \begin{corollary}[Theorem 2.5 of \cite{Sach}]
The generating functions for the number of $n$-color compositions  of $\nu$ into $m$ parts such that the odd parts have only odd subscripts and for the total  number of $n$-color compositions  of $\nu$  such that the odd parts have only odd subscripts are
\begin{align*}
\mathcal{G}\D_{2a+1}^{2a'+1}(m, x)&amp;=\left(\frac{x+2x^2}{(1-x^{2})^2}\right)^m,\\
\mathcal{G}\D_{2a+1}^{2a'+1}(x)&amp;=\frac{x+2x^2}{1-x -4x^2  + x^4}.
\end{align*}
\end{corollary}


 \begin{corollary}[Theorem 2.6 of \cite{Sach}]
The generating functions for the number of $n$-color compositions  of $\nu$ into $m$ parts such that the even parts have only even (odd) subscripts and for the total  number of $n$-color compositions  of $\nu$  such that the even parts have only even (odd) subscripts are
\begin{align*}
\mathcal{G}\D_{2a+2}^{2a'+2}(m, x)&amp;=\mathcal{G}\D_{2a+2}^{2a'+1}(m, x)=\left(\frac{x + x^2 + x^3}{(1-x^{2})^2}\right)^m,\\
\mathcal{G}\D_{2a+2}^{2a'+2}(x)&amp;=\mathcal{G}\D_{2a+2}^{2a'+1}(x)=\frac{x + x^2 + x^3}{1 - x - 3 x^2 - x^3 + x^4}.
\end{align*}
\end{corollary}


 \section{A further related restriction}

 Given $\ell \geq 1$, let $\T_{\ell}(\nu)$ denote the number of $n$-color compositions of $\nu$ such that any part of the form  $\ell a +b$ for some $a \geq 0$  and $1\leq b \leq \ell$ has a subscript of the same form.  Additionally, we denote by $\T_{\ell}(m, \nu)$ the number of such $n$-color compositions of $\nu$ that have  $m$ parts.

For example,  $\T_{4}(5)=17$, the compositions being
\begin{align*}
&amp;\{\texttt{5}_\texttt{1}\},\{\texttt{5}_\texttt{5}\},\{\texttt{4}_\texttt{4},\texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1},\texttt{4}_\texttt{4}\},\{\texttt{3}_\texttt{3},\texttt{2}_\texttt{2}\},\{\texttt{2}_\texttt{2},\texttt{3}_\texttt{3}\},\{\texttt{3}_\texttt{3},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1},\texttt{3}_\texttt{3},\texttt{1}_\texttt{1}\}, \{\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{3}_\texttt{3}\}, \\
&amp;\{\texttt{2}_\texttt{2},\texttt{2}_\texttt{2},\texttt{1}_\texttt{1}\},\{\texttt{2}_\texttt{2},\texttt{1}_\texttt{1},\texttt{2}_\texttt{2}\},\{\texttt{1}_\texttt{1},\texttt{2}_\texttt{2},\texttt{2}_\texttt{2}\},\{\texttt{2}_\texttt{2},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1}\},\{\texttt{1}_\texttt{1},\texttt{2}_\texttt{2},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1}\}, \{\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{2}_\texttt{2},\texttt{1}_\texttt{1}\},\\
&amp;\{\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{2}_\texttt{2}\},\{\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1},\texttt{1}_\texttt{1}\}.
   \end{align*}
Similar to the proof of Theorems \ref{teo1} and \ref{teo1b} above, we have the following result.
\begin{theorem}\label{teo3}
Let $\mathcal{G}\T_{\ell}(m, x)$  and  $\mathcal{G}\T_{\ell}(x)$ denote  the generating functions for the sequences $\T_{\ell}(m,\nu)$ and $\T_{\ell}(\nu)$, respectively.  Then we have
\begin{align*}
\mathcal{G}\T_{\ell}(m, x)&amp;=\left(\frac{x}{(1-x)(1-x^{\ell})}\right)^m, \\
\mathcal{G}\T_{\ell}(x)&amp;=\frac{x}{1-2x-x^\ell+x^{\ell+1}}.
\end{align*}
Moreover, the sequence $\T_{\ell}(m, \nu)$ for $1 \leq m \leq \nu$ is given explicitly by
$$\T_{\ell}(m, \nu)=\sum_{i=0}^{\left \lfloor\frac{\nu-m}{\ell} \right\rfloor}\binom{m+i-1}{m-1}\binom{\nu-\ell i-1}{m-1},$$
with $\T_{\ell}(\nu)=2\T_{\ell}(\nu-1) + \T_{\ell}(\nu-\ell) - \T_{\ell}(\nu-\ell-1)$ for $\nu&gt;\ell +1$.
\end{theorem}

Note that the sequences  $\T_{\ell}(\nu)$ and $\C_{\ell a + 1}(\nu)$ are the same which can be shown using the definitions.

We now describe a statistic on $n$-color compositions which accounts for the expression given for $\mathcal{T}_\ell(m,\nu)$ above.  More precisely, let $\mathcal{S}_\ell(m,\nu)$ denote the set of $n$-color compositions enumerated by $\mathcal{T}_\ell(m,\nu)$ and we determine a statistic $\sigma$ on $\mathcal{S}_\ell(m,\nu)$ such that
$$|\{\pi \in \mathcal{S}_\ell(m,\nu):\sigma(\pi)=i\}|=\binom{m+i-1}{m-1}\binom{\nu-\ell i-1}{m-1}.$$
Given a part $\alpha_\beta$ of $\pi \in \mathcal{S}_\ell(m,\nu)$, let $\sigma(\alpha_\beta)=\lfloor(\beta-1)/\ell\rfloor$.  Define $\sigma(\pi)$ to be the sum of the $\sigma$-values of its individual parts.  For example, if $\ell=3$ and
$\pi=5_2,7_7,8_5,12_9,3_3\in \mathcal{S}_3(5,35)$,
then $\sigma(\pi)=0+2+1+2+0=5$.  Note that if $\beta$ corresponds to the $i$-th smallest possible subscript on a part of $\pi$ of size $\alpha$, then $\alpha_\beta$ contributes $i-1$ towards the $\sigma(\pi)$ statistic value.  If $\ell=1$, then it is seen that $\sigma(\pi)$ is simply the sum of the subscripts of all the parts minus the number of parts of $\pi$.  Define
$$t_{\nu,m}^{(\ell)}(q)=\sum_{\pi\in\mathcal{S}_\ell(m,\nu)}q^{\sigma(\pi)},\qquad \nu \geq m \geq 1,$$
where $q$ is an indeterminate.  We have the following explicit formula for $t_{\nu,m}^{(\ell)}(q)$.

\begin{theorem}\label{qgen}
If $\nu \geq m \geq 1$ and $\ell \geq 1$, then
\begin{equation}\label{qgen1}
t_{\nu,m}^{(\ell)}(q)=\sum_{i=0}^{\left \lfloor\frac{\nu-m}{\ell} \right\rfloor}\binom{m+i-1}{m-1}\binom{\nu-\ell i-1}{m-1}q^i.
\end{equation}
\end{theorem}
\begin{proof}
Let $\sigma'$ be the statistic defined on $\pi \in \mathcal{S}_\ell(m,\nu)$ as follows.  Given a part $\alpha_\beta$ of $\pi$, let $\sigma'(\alpha_\beta)=\frac{\alpha-\beta}{\ell}$ and define $\sigma'(\pi)$ to be the sum of the $\sigma'$ values of its parts.  For example, if $\pi \in \mathcal{S}_3(5,35)$ is as before, then $\sigma'(\pi)=3$.  We first show that $\sigma$ and $\sigma'$ are identically distributed on $\mathcal{S}_\ell(m,\nu)$.  To do so, we change the subscripts on each part of $\pi \in \mathcal{S}_\ell(m,\nu)$ as follows. Let $r_s$ be a part of $\pi$.  First assume $r$ is not divisible by $\ell$.  Then $r=\ell a+b$ where $a \geq 0$ and $1 \leq b \leq \ell-1$ and $s=\ell a'+b$ for some $0 \leq a' \leq a$.  In this case, we replace $r_s$ with $r_t$, where $t=\ell(a-a')+b$.  If $r$ is divisible be $\ell$, then $r=\ell a$ and $s=\ell a'$ for some $1 \leq a' \leq a$, in which case we replace the part $r_s$ with $r_t$, where $t=\ell(a-a'+1)$.  Let $\pi'$ denote the resulting member of $\mathcal{S}_\ell(m,\nu)$.  One may verify that the mapping $\pi \mapsto \pi'$ is a bijection with $\sigma(\pi)=\sigma'(\pi')$ for all $\pi$.

We now count members $\pi\in\mathcal{S}_\ell(m,\nu)$ such that $\sigma'(\pi)=i$ where $0 \leq i \leq \lfloor (\nu -m)/\ell\rfloor$.  We denote these $\pi$ by
$$\pi=(a_1+\ell b_1)_{a_1},\ldots,(a_m+\ell b_m)_{a_m},$$
where $a_j \geq 1$ and $b_j \geq 0$ for all $j$.  Then $b_1+\cdots+b_m=i$ implies there are $\binom{m+i-1}{m-1}$ possibilities for the $b_j$. Thus, $a_1+\cdots+a_m=\nu-\ell i$ so that there are $\binom{\nu-\ell i-1}{m-1}$ possibilities for the $a_j$.  Since the $a_j$ and $b_j$ may be chosen independently of one another, it follows that there are $\binom{m+i-1}{m-1}\binom{\nu-\ell i-1}{m-1}$ such $\pi$, which completes the proof of \eqref{qgen1}.
\end{proof}

Let $t_\nu^{(\ell)}(q,u)=\sum_{m=1}^\nu t_{\nu,m}^{(\ell)}(q)u^m$ for $\nu \geq 1$ and define the generating function $$T^{(\ell)}(x;q,u)=\sum_{\nu\geq 1}t_\nu^{(\ell)}(q,u)x^\nu.$$ Using \eqref{qgen1} and interchanging summation yields the following result.

\begin{corollary}\label{qgencor}
We have
\begin{equation}\label{qgencore1}
T^{(\ell)}(x;q,u)=\frac{xu}{1-x(1+u)-x^\ell q+x^{\ell+1}q}
\end{equation}
and thus
\begin{equation}\label{qgencore2}
t_\nu^{(\ell)}(q,u)=(1+u)t_{\nu-1}^{(\ell)}(q,u)+qt_{\nu-\ell}^{(\ell)}(q,u)-qt_{\nu-\ell-1}^{(\ell)}(q,u), \qquad \nu&gt;\ell+1.
\end{equation}
\end{corollary}

Formulas \eqref{qgencore1} and \eqref{qgencore2} reduce, respectively, to the generating function and recurrence formulas for $\mathcal{T}_\ell(\nu)$ in Theorem \ref{teo3} when $q=u=1$.  Note that the $\ell=u=1$ case of recurrence \eqref{qgencore2} was previously considered in \cite{ManSha}.  A combinatorial proof may be given for \eqref{qgencore2} by considering whether or not the last part is $1_1$, and if not, whether or not the last part is equal to its subscript.  Finally, taking $\ell=2$ in the preceding yields a polynomial generalization of the problem of counting $n$-color compositions of a given size in which each part and its respective subscript always have the same parity.



\section{Acknowledgments}

The fourth author thanks an invitation from the Department of Mathematics and Statistics of Universidad del Tolima, Tolima, Colombia, where the presented work was initiated. Additionally, the research of the fourth author was partially supported by Universidad Nacional de Colombia, Project No.\ 46240.


\begin{thebibliography}{99}
\bibitem{Aga} A.~K.~Agarwal, $n$-Colour compositions, \emph{Indian J. Pure Appl. Math.}  {\bf31} (2000), 1421--1427.

\bibitem{Aga3} A.~K.~Agarwal, Combinatorial properties of $n$-color
compositions, in \emph{Ramanujan Math. Soc. Lect. Notes Ser.}, Vol.~20,
Ramanujan Math. Soc., 2013, pp.\ 13--28.

\bibitem{CH} P.~Chinn and S.~Heubach, $(1,k)$-compositions, \emph{Congr.  Numer.} {\bf164} (2003), 183--194.

\bibitem{Coll} A.~Collins, C.~Dedrickson, and  H.~Wang, Binary words, $n$-color compositions and bisection of the Fibonacci numbers, \emph{Fibonacci Quart.} {\bf51} (2013), 130--136.

\bibitem{Concrete} R.~L.~Graham, D.~E.~Knuth, and O.~Patashnik,
\emph{Concrete Mathematics: A Foundation for Computer Science}, 2nd  
edition,  Addison-Wesley, 1994.

\bibitem{Guo1} Y.-H.~Guo, Some $n$-color compositions, \emph{J. Integer Sequences} {\bf15} (2012), \href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Guo/guo4.html}{Article 12.1.2}.

\bibitem{Guo2} Y.-H.~Guo, $n$-Color even compositions, \emph{Ars Combin.} {\bf109} (2013), 425--432.

\bibitem{Mansour} S.~Heubach and T.~Mansour, \emph{Combinatorics of Compositions and Words}, CRC Press, 2009.

\bibitem{ManSha} T.~Mansour and M.~Shattuck, A statistic on $n$-color compositions and related sequences, \emph{Proc. Indian Acad. Sci. Math. Sci.} {\bf124} (2014), 127--140.

\bibitem{Nar1} G.~Narang and A.~K.~Agarwal, $n$-Color self-inverse compositions, \emph{Proc. Indian Acad. Sci. Math. Sci.} {\bf116} (2006), 257--266.

\bibitem{Nar3}  G.~Narang and A.~K.~Agarwal, Lattice paths and $n$-color compositions, \emph{Discrete Math.} {\bf308} (2008),  1732--1740.

\bibitem{RamSir} J.~L.~Ram\'irez and  V.~Sirvent,  A note on the $k$-Narayana sequence,  \emph{Ann. Math. Inform.} {\bf45} (2015), 91--105.


\bibitem{Sach} R.~Sachdeva and A.~K.~Agarwal, Combinatorics of certain restricted $n$-color composition functions, \emph{Discrete Math.} {\bf340} (2017), 361--372.

\bibitem{Shap1} C.~Shapcott, $C$-color compositions and palindromes, \emph{Fibonacci Quart.} {\bf50} (2012), 297--303.

\bibitem{Shap2} C.~Shapcott, New bijections from $n$-color compositions, \emph{J. Comb.} {\bf4} (2013), 373--385.

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

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: }
$n$-color composition, generating function, combinatorial identity.

\bigskip
\hrule
\bigskip

\noindent(Concerned with sequences  \seqnum{A000045},  \seqnum{A000930},   \seqnum{A003269}, \seqnum{A003520},  \seqnum{A005708}, \seqnum{A052908}, \linebreak \seqnum{A116732},  \seqnum{A176848}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 26 2019; revised version received August 15 2019.
Published in {\it Journal of Integer Sequences}, August 24 2019.

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


\end{document}
</pre></body></html>