\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Some $n$-Color Compositions
}
\vskip 1cm
\large
Yu-hong Guo\footnote{This work is supported by the Fund
of the Education Department of
Gansu Province (No.\ 200809-04) and the fund of Hexi University.}\\
Department of Mathematics \\
Hexi University \\
Gansu, Zhangye, 734000 \\
P. R. China \\
\href{mailto:gyh7001@163.com}{\tt gyh7001@163.com}\\
\end{center}

\vskip .2 in

\begin{abstract}
An $n$-color odd composition is defined as an $n$-color composition
with odd parts, and an $n$-color composition with parts $\neq 1$ is
an $n$-color composition whose parts are $> 1$. In this paper,  we
get generating functions, explicit formulas and recurrence formulas
for $n$-color odd compositions and $n$-color compositions with parts
$\neq 1$.
\end{abstract}

\section{Introduction}\label{sec1}

In the classical theory of partitions, compositions were first
defined  by MacMahon \cite{a} as ordered partitions. For example,
there are  $5$ partitions and $8$ compositions of $4$. The
partitions are  $4$, $31$, $22$, $21^{2}$, $1^{4}$ and the
compositions are $4$, $31$, $13$, $22$, $21^{2}$, $121$, $1^{2}2$,
$1^{4}$.

Agarwal and Andrews \cite{b} defined an $n$-color partition as a
partition in which a part of size $n$ can come in $n$ different
colors. They denoted different colors by subscripts: $n_{1}$,
$n_{2}$, $\ldots$, $n_{n}$. Analogous to MacMahon's ordinary
compositions Agarwal \cite{c} defined an  $n$-color composition as
an $n$-color ordered partition. Thus,  for example, there are $21$
$n$-color compositions of $4$, viz.,
 \begin{eqnarray*}
& &4_{1}, 4_{2},4_{3},4_{4},\\
& &3_{1}1_{1}, 3_{2}1_{1}, 3_{3}1_{1}, 1_{1}3_{1},1_{1}3_{2},
1_{1}3_{3},\\
& &2_{1}2_{1}, 2_{1}2_{2}, 2_{2}2_{2},2_{2}2_{1},\\
& &2_{1}1_{1}1_{1}, 2_{2}1_{1}1_{1},1_{1}2_{1}1_{1},
1_{1}1_{1}2_{1}, 1_{1}2_{2}1_{1}, 1_{1}1_{1}2_{2},\\
& &1_{1}1_{1}1_{1}1_{1}.
\end{eqnarray*}

More properties of $n$-color compositions were found in \cite{d,e}.
In 2006, G. Narang and Agarwal \cite{f,g} also defined an $n$-color
self-inverse  composition and gave some properties. In 2010, Guo
\cite{h} defined an $n$-color even self-inverse  composition and
proved some properties.

In this paper, we shall study some $n$-color  compositions. We first
give the following definitions.

\begin{definition}
An $n$-color odd composition is an $n$-color  composition with odd
parts.
\end{definition}

Thus, for example, there are $7$ $n$-color odd compositions of $4$,
viz.,
\begin{eqnarray*}
& &3_{1}1_{1}, 3_{2}1_{1},3_{3}1_{1},\\
& &1_{1}3_{1}, 1_{1}3_{2}, 1_{1}3_{3},1_{1}1_{1}1_{1}1_{1}.
\end{eqnarray*}
\begin{definition}
An $n$-color  composition with parts $\neq 1$ is an $n$-color
composition whose parts are $>1$.
\end{definition}

For example, there are $17$ $n$-color compositions with parts
$\neq1$ of $5$, viz.,
\begin{eqnarray*}
& &5_{1}, 5_{2}, 5_{3}, 5_{4},5_{5},\\
& &2_{1}3_{1}, 2_{1}3_{2}, 2_{1}3_{3}, 2_{2}3_{1}, 2_{2}3_{2}, 2_{2}3_{3},\\
& &3_{1}2_{1}, 3_{2}2_{1}, 3_{3}2_{1}, 3_{1}2_{2}, 3_{2}2_{2},
3_{3}2_{2}.\\
\end{eqnarray*}

In section \ref{sec2} we shall give generating functions, recurrence
formulas and explicit formulas for $n$-color compositions above.

Agarwal \cite{c} proved the following theorem.

\begin{theorem}{(\cite{c})}
Let $C(m,q)$ and $C(q)$ denote the enumerative generating functions
for $C(m,\nu)$ and $C(\nu)$, respectively, where $C(m,\nu)$ is the
number of $n$-color  compositions of $\nu$ into $m$ parts and
$C(\nu)$ is the number of $n$-color  compositions of $\nu$. Then

\begin{equation}
C(m,q)=\frac{q^{m}}{(1-q)^{2m}},
\end{equation}
\begin{equation}
C(q)=\frac{q}{1-3q+q^{2}},
\end{equation}
\begin{equation}
C(m,\nu)={{\nu+m-1}\choose{2m-1}},
\end{equation}
\begin{equation}
C(\nu)= F_{2\nu}.
\end{equation}
\end{theorem}
\section{Main results}\label{sec2}

We denote the number of $n$-color  odd compositions of $\nu$ by
$C(o,\nu)$ and the number of $n$-color  odd compositions of $\nu$
into $m$ parts by $C(m,o,\nu)$, respectively. In this section, we
first prove the following theorem.
\begin{theorem}\label{th1}
Let $C(m,o,q)$ and $C(o,q)$ denote the enumerative generating
functions for $C(m,o,\nu)$ and $C(o,\nu)$, respectively. Then

\begin{equation}
C(m,o,q)=\frac{q^{m}(1+q^{2})^{m}}{(1-q^{2})^{2m}},\label{eq5}
\end{equation}
\begin{equation}
C(o,q)=\frac{q+q^{3}}{1-q-2q^{2}-q^{3}+q^{4}},\label{eq6}
\end{equation}
\begin{equation}
C(m,o,\nu)=\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}},\label{eq7}
\end{equation}
\begin{equation}
C(o,\nu)=\sum_{m \leq \nu}
\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}.\label{eq8}
\end{equation}
where $(\nu-m)$ is even, and $(\nu-m) \geq 0$; $0\leq i,j$ are
integers.
\end{theorem}

\begin{proof}  Similar to the proof of Agarwal \cite{c}, we
have
\begin{equation*}
C(m,o,q)=\sum_{\nu=1}^{\infty}C(m,o,\nu)q^{\nu}=(q+3q^{3}+\cdots+)^{m}
=\frac{q^{m}(1+q^{2})^{m}}{(1-q^{2})^{2m}}.
\end{equation*}
This proves (\ref{eq5}).

\begin{equation*}
C(o,q)=\sum_{m=1}^{\infty}C(m,o,q)\\
=\sum_{m=1}^{\infty}\frac{q^{m}(1+q^{2})^{m}}{(1-q^{2})^{2m}}\\
=\frac{q+q^{3}}{1-q-2q^{2}-q^{3}+q^{4}}.
\end{equation*}
We get (\ref{eq6}).

On equating the coefficients of $q^{\nu}$ in (\ref{eq5}), we have
\begin{equation*}
C(m,o,\nu)=\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}.
\end{equation*}

Since $\nu$ is even if $m$ is even, and $\nu$ is odd if $m$ is odd,
then $\nu-m$ is even. This proves (\ref{eq7}).

Obviously $m \leq \nu$, so (\ref{eq8}) is also proven.

We complete the proof of this theorem.
\end{proof}

In this section, we also prove the following recurrence formula.
\begin{theorem}\label{th2}
Let $O_{\nu}$ denote the number of $n$-color  odd compositions  of
$\nu$. Then
\begin{equation*}
O_{1}=1, O_{2}=1, O_{3}=4, O_{4}=7
\end{equation*}
and
\begin{equation*}
O_{\nu}=O_{\nu-1}+2O_{\nu-2}+O_{\nu-3}-O_{\nu-4},~\text{for}~\nu>4.
\end{equation*}
\end{theorem}

\begin{proof}
(Combinatorial)
To prove that
$O_{\nu}=O_{\nu-1}+2O_{\nu-2}+O_{\nu-3}-O_{\nu-4}$,  we split the
$n$-color compositions enumerated by $O_{\nu}+O_{\nu-4}$ into four classes:

(A) enumerated by $O_{\nu}$ with $1_{1}$ on the right.

(B) enumerated by $O_{\nu}$ with $3_{3}$ on the right.

(C) enumerated by $O_{\nu}$ with $h_{t}$ on the right, $h>1$, $1\leq
t \leq h-2$ (where, $h$ is odd).

(D) enumerated by $O_{\nu}$ with $h_{t}$ on the right,
$h>1$,$h-1\leq t \leq h$ except $3_{3}$ and those enumerated by
$O_{\nu-4}$.

We transform the $n$-color odd compositions in class (A) by deleting
$1_{1}$ on the right. This produces $n$-color compositions
enumerated by $O_{\nu-1}$. Conversely, for any $n$-color composition
enumerated by $O_{\nu-1}$ we add $1_{1}$ on the right to produce the
elements of the  class (A). In this way we prove that there are
exactly $O_{\nu-1}$ elements in the class (A).

Similarly, we can produce $O_{\nu-3}$ $n$-color odd compositions in
the class (B) by deleting $3_{3}$ on the right.

Next, we transform the $n$-color odd compositions in
class (C) by subtracting $2$ from $h$, that is, replacing $h_{t}$ by
$(h-2)_{t}$. This transformation also establishes the fact that
there are exactly $O_{\nu-2}$ elements in class (C). This
correspondence being one to one.

Finally, we transform the elements in class (D) as follows: Subtract
$2_{2}$ from $h_{t}$ on the right when $h>3$, $h-1\leq t\leq h$,
that is, replace $h_{t}$ by $(h-2)_{(t-2)}$; in this way we will get
$n$-color odd compositions of $\nu-2$ with part $h^{'}_{t^{'}}$ on
the right, where, $h^{'}>1, t^{'}\geq h^{'}-1$. After that we
replace $h_{t}$ by $(h-2)_{(t-1)}$ when $h=3$, $ t=2$. This produces
$n$-color odd compositions of $\nu-2$ with part $1_{1}$ on the
right. To get the remaining $n$-color odd compositions from
$O_{\nu-4}$, we add $2$ to the right parts, that is, replace $h_{t}$
by $(h+2)_{t}$ to get the $n$-color odd compositions of $(\nu-2)$
with part $h^{'}_{t^{'}}$ on the right, where, $h^{'}>1,1 \leq t^{'}
\leq h^{'}-2$.  We see that the number of $n$-color odd compositions
in class (D) is also equal to $O_{\nu-2}$. Hence,
$O_{\nu}+O_{\nu-4}=O_{\nu-1}+2O_{\nu-2}+O_{\nu-3}$.
viz.,$O_{\nu}=O_{\nu-1}+2O_{\nu-2}+O_{\nu-3}-O_{\nu-4}$.

Thus, we complete the proof.
\end{proof}

We also give another proof of Theorem \ref{th2}.

\begin{proof}
We have
\allowdisplaybreaks{\begin{eqnarray*}
O_{\nu}&\,=\,&\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&\,=\,&\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+(i-1)-1}\choose{2m-1}}{{m}\choose{j}}
+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+(i-1)-1}\choose{2m-2}}{{m}\choose{j}}\\
&&(\text{by the binomial identity} {{n}\choose{m}}={{n-1}\choose{m}}+{{n-1}\choose{m-1}})\\
&\,=\,&\sum_{m\leq\nu-2}\sum_{i+j=\frac{(\nu-2)-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}+{{2\nu-2}\choose{2\nu-1}}{{\nu}\choose{0}}\\
&&{}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}
-\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-2}\choose{2m-1}}{{m}\choose{j}}\\
&\,=\,&O_{\nu-2}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}-\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+(i-2)-1}\choose{2m-1}}{{m}\choose{j}}-
\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-3}\choose{2m-2}}{{m}\choose{j}}\\
&\,=\,&O_{\nu-2}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}-\sum_{m\leq\nu-4}\sum_{i+j=\frac{(\nu-4)-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}
-{{2\nu-2-1}\choose{2\nu-1}}{{\nu}\choose{0}}\\
&&{}-{{2(\nu-2)-2-1}\choose{2(\nu-2)-1}}{{\nu-2}\choose{1}}
-{{2(\nu-2)-1-1}\choose{2(\nu-2)-1}}{{\nu-2}\choose{0}}\\
&&{}-\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-3}\choose{2m-2}}{{m}\choose{j}}\\
&\,=\,&O_{\nu-2}-O_{\nu-4}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+(i-1)-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-2}\choose{2m-2}}{{m}\choose{j}}-
\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-3}\choose{2m-2}}{{m}\choose{j}}\\
&\,=\,&2O_{\nu-2}-O_{\nu-4}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-3}\choose{2m-3}}{{m}\choose{j}}\\
&\,=\,&2O_{\nu-2}-O_{\nu-4}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2(m-1)+i-1}\choose{2(m-1)-1}}{{m-1}\choose{j}}\\
&&{}+\sum_{m\leq\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2(m-1)+i-1}\choose{2(m-1)-1}}{{m-1}\choose{j-1}}\\
&\,=\,&2O_{\nu-2}-O_{\nu-4}+\sum_{m\leq\nu-1}\sum_{i+j=\frac{(\nu-1)-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\nu-3}\sum_{i+j=\frac{(\nu-3)-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&\,=\,&O_{\nu-1}+2O_{\nu-2}+O_{\nu-3}-O_{\nu-4}.
\end{eqnarray*}}
So we have $O_{\nu}=O_{\nu-1}+2O_{\nu-2}+O_{\nu-3}-O_{\nu-4}.$
\end{proof}
From recurrence formula above we have the following corollary
easily.

\begin{corollary}\label{th3}
~~If $\nu>4$, then
\begin{eqnarray*}
&&\sum_{m \leq
\nu-4}(\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}-\sum_{i+j=\frac{\nu-1-m}
{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}-2\sum_{i+j=\frac{\nu-2-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}-
\sum_{i+j=\frac{\nu-3-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}+\sum_{i+j=\frac{\nu-4-m}{2}}{{2m+i-1}\choose{2m-1}}
{{m}\choose{j}})=0.
\end{eqnarray*}
\end{corollary}

Next, we shall study $n$-color compositions with parts $\neq 1$. We
denote the number of $n$-color  compositions with parts $\neq 1$ of
$\nu$ by $C_{\neq 1}(\nu)$ and the number of $n$-color compositions
with parts $\neq 1$ of $\nu$ into $m$ parts by $C_{\neq 1}(m, \nu)$,
respectively. In this section, we present the following theorem.
\begin{theorem}\label{th4}
Let $C_{\neq1}(m,q)$ and $C_{\neq1}(q)$ denote the enumerative
generating functions for $C_{\neq1}(m,\nu)$ and $C_{\neq1}(\nu)$,
respectively. Then

\begin{equation}
C_{\neq1}(m,q)=\frac{q^{2m}(2-q)^{m}}{(1-q)^{2m}},\label{eq9}
\end{equation}
\begin{equation}
C_{\neq1}(q)=\frac{2q^{2}-q^{3}}{1-2q-q^{2}+q^{3}},\label{eq10}
\end{equation}
\begin{equation}
C_{\neq1}(m,\nu)=\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}},\label{eq11}
\end{equation}
\begin{equation}
C_{\neq1}(\nu)=\sum_{m \leq
\frac{\nu}{2}}~\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}.\label{eq12}
\end{equation}
where $(\nu-2m)$ is an integer, and $(\nu-2m) \geq 0$; $0\leq i,j$ are
integers.
\end{theorem}

\begin{proof}  Similar to the proof of Agarwal \cite{c}, we
have
\begin{equation*}
C_{\neq1}(m,q)=\sum_{\nu=1}^{\infty}C_{\neq1}(m,\nu)q^{\nu}
=(2q^{2}+3q^{3}+\cdots+)^{m}
=\frac{q^{2m}(2-q)^{m}}{(1-q)^{2m}}.
\end{equation*}

This proves (\ref{eq9}).


\begin{equation*}
C_{\neq1}(q)=\sum_{m=1}^{\infty}C_{\neq1}(m,q)
=\sum_{m=1}^{\infty}\frac{q^{2m}(2-q)^{m}}{(1-q)^{2m}}
=\frac{2q^{2}-q^{3}}{1-2q-q^{2}+q^{3}}.
\end{equation*}

This proves (\ref{eq10}).

On equating the coefficients of $q^{\nu}$ in (\ref{eq9}), we have
\begin{equation*}
C_{\neq1}(m,\nu)=\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}.
\end{equation*}

Since $\nu \geq 2m$, then $\nu-2m \geq 0$, $i+j \geq 0,$ and $0 \leq
i,j$ are integers. This proves (\ref{eq11}).

Obviously $m \leq \frac{\nu}{2}$, therefore (\ref{eq12}) is also
proven.

We complete the proof of this theorem.
\end{proof}

In this section, we also prove the following recurrence formula.
\begin{theorem}\label{th5}
Let $C_{\neq1}(\nu)$ denote the number of $n$-color compositions
with parts ${\neq1}$ of $\nu$. Then
\begin{equation*}
C_{\neq1}(2)=2, C_{\neq1}(3)=3, C_{\neq1}(4)=8,
\end{equation*}
and
\begin{equation*}
C_{\neq1}(\nu)=2C_{\neq1}(\nu-1)+C_{\neq1}(\nu-2)-C_{\neq1}(\nu-3)~~\text{for}~~\nu>4.
\end{equation*}
\end{theorem}

\begin{proof} (Combinatorial) To prove that
$C_{\neq1}(\nu)=2C_{\neq1}(\nu-1)+C_{\neq1}(\nu-2)-C_{\neq1}(\nu-3)$,
we split the $n$-color
compositions enumerated by $C_{\neq1}(\nu)+C_{\neq1}(\nu-3)$ into three classes:

(A)~enumerated by $C_{\neq1}(\nu)$ with $2_{1}$ on the right.

(B)~enumerated by $C_{\neq1}(\nu)$ with $h_{t}$ on the right,
$h>2$,$1\leq t \leq h-1$.

(C)~enumerated by $C_{\neq1}(\nu)$ with $h_{h}$ on the right, $h
\geq 2$ and those enumerated by $C_{\neq1}(\nu-3)$.

We transform the $n$-color compositions in class (A) by deleting
$2_{1}$ on the right. This produces $n$-color compositions
enumerated by $C_{\neq1}(\nu-2)$. Conversely, for any $n$-color
composition enumerated by $C_{\neq1}(\nu-2)$ we add $2_{1}$ on the
right to produce the elements of the  class (A). In this way we
prove that there are exactly $C_{\neq1}(\nu-2)$ elements in the
class (A).

Next, we transform the $n$-color  compositions in class (B) by
subtracting $1$ from $h$, that is, replacing $h_{t}$ by $(h-1)_{t}$;
this transformation also establishes the fact that there are exactly
$C_{\neq1}(\nu-1)$ elements in class (B). This correspondence being
one to one.

Finally, we transform the elements in class (C) as follows: Subtract
$1_{1}$ from $h_{h}$ on the right when $h>2$, that is, replace
$h_{h}$ by $(h-1)_{(h-1)}$; in this way we will get $n$-color
compositions of $\nu-1$ with part $h^{'}_{h^{'}}(h^{'}>1)$ on the
right. We also replace $h_{h}$ by $(h-1)_{(h-1)}$ when $h=2$. This
produces $n$-color  compositions of $\nu-1$ with part $1_{1}$ on the
right. Now we delete $1_{1}$ and add $1$ to the preceding part of
it. For example,
$2_{1}2_{2}2_{2}$$\longrightarrow$$2_{1}2_{2}1_{1}$$\longrightarrow$$2_{1}3_{2}$;
$4_{1}2_{2}$$\longrightarrow$$4_{1}1_{1}$$\longrightarrow$$5_{1}$.
Then we have $n$-color  compositions of $\nu-1$ with part
$h^{'}_{t}$ on the right, where, $h^{'}>2, 1\leq t\leq h^{'}-1$. To
get the remaining $n$-color compositions from $C_{\neq1}(\nu-3)$, we
set $2_{1}$ on the right. This produces $n$-color  compositions with
parts $\neq 1$ of $\nu-1$ with $2_{1}$ on the right. We see that the
number of $n$-color compositions in class (C) is also equal to
$C_{\neq 1}(\nu-1)$. Hence, $C_{\neq 1}(\nu)+C_{\neq
1}(\nu-3)=2C_{\neq 1}(\nu-1)+C_{\neq 1}(\nu-2)$. viz.,
$C_{\neq1}(\nu)=2C_{\neq1}(\nu-1)+C_{\neq1}(\nu-2)-C_{\neq1}(\nu-3)$.

Thus, we complete the proof.
\end{proof}

We also give another proof of Theorem \ref{th5}.

\begin{proof} We have
\allowdisplaybreaks{\begin{eqnarray*}
C_{\neq1}(\nu)&\,=\,&\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&\,=\,&\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+(i-1)-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-1}\choose{2m-2}}{{m}\choose{j}}\\
&&(\text{by the binomial identity} {{n}\choose{m}}={{n-1}\choose{m}}+{{n-1}\choose{m-1}})\\
&\,=\,&\sum_{m\leq\frac{\nu-1}{2}}\sum_{i+j=(\nu-1)-2m}(-1)^{j}2^{m-j}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-2}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-3}}{{m}\choose{j}}\\
&\,=\,&C_{\neq1}(\nu-1)+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-2}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-3}}{{m-1}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2(m-1)+i-1}\choose{2(m-1)-1}}{{m-1}\choose{j-1}}\\
&\,=\,&C_{\neq1}(\nu-1)+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-2}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2}\choose{2m-2}}{{m-1}\choose{j}}\\
&&{}-\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-2}}{{m-1}\choose{j}}\\
&&{}+\sum_{m\leq\frac{(\nu-3)}{2}}\sum_{i+j=(\nu-3)-2m}(-1)^{j+1}2^{m-j}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&\,=\,&C_{\neq1}(\nu-1)-C_{\neq1}(\nu-3)\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-2}}{{m-1}\choose{j-1}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-2}}{{m-1}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-3}}{{m-1}\choose{j}}\\
&\,=\,&C_{\neq1}(\nu-1)-C_{\neq1}(\nu-3)\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-2}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2(m-1)+i-1}\choose{2(m-1)-1}}{{m-1}\choose{j}}\\
&\,=\,&C_{\neq1}(\nu-1)-C_{\neq1}(\nu-3)\\
&&{}+\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2}\choose{2m-1}}{{m}\choose{j}}\\
&&{}-\sum_{m\leq\frac{\nu}{2}}\sum_{i+j=\nu-2m}(-1)^{j}2^{m-j}{{2m+i-2-1}\choose{2m-1}}{{m}\choose{j}}\\
&&{}+\sum_{m\leq\frac{\nu-2}{2}}\sum_{i+j=(\nu-2)-2m}(-1)^{j}2^{m+1-j}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}\\
&\,=\,&C_{\neq1}(\nu-1)-C_{\neq1}(\nu-3)+C_{\neq1}(\nu-1)-C_{\neq1}(\nu-2)+2C_{\neq1}(\nu-2)\\
&\,=\,&2C_{\neq1}(\nu-1)+C_{\neq1}(\nu-2)-C_{\neq1}(\nu-3).
\end{eqnarray*}}
Thus we have
$C_{\neq1}(\nu)=2C_{\neq1}(\nu-1)+C_{\neq1}(\nu-2)-C_{\neq1}(\nu-3).$
\end{proof}

\section{Acknowledgement}\label{sec3}
 The author would like to thank the referee
for his/her suggestions and comments which have improved the
quality of this paper. 

\begin{thebibliography}{8}
\bibitem{a} P. A. MacMahon, \emph{Combinatory Analysis},
AMS Chelsea  Publishing, 2001.

\bibitem{b} A. K. Agarwal and G. E. Andrews, Rogers-Ramanujan identities 
for partitions with ``$n$ copies of $n$'',
\emph{J. Combin. Theory Ser. A} {\bf 45} (1987), 40--49.

\bibitem{c} A. K. Agarwal, $n$-colour compositions, \emph{Indian J. Pure Appl. Math.} {\bf 31} (2000), 1421--1427.

\bibitem{d} A. K. Agarwal, An analogue of Euler's identity and new combinatorial  properties of $n$-colour compositions, \emph{J. Comput. Appl. Math.} {\bf 160} (2003), 9--15.

\bibitem{e} Yu-Hong Guo, Some identities between partitions and compositions, \emph{Acta Math. Sinica (Chin. Ser.)} {\bf 50} (2007), 707--710.

\bibitem{f} G. Narang and A. K. Agarwal, $n$-colour self-inverse compositions,
\emph{Proc. Indian Acad. Sci. Math. Sci.} {\bf 116} (2006), 257--266.

\bibitem{g} G. Narang and A. K. Agarwal, Lattice paths and n-color compositions, \emph{Discrete Math.} {\bf
308} (2008), 1732--1740.

\bibitem{h} Yu-Hong Guo, $n$-colour even self-inverse compositions, \emph{Proc. Indian Acad. Sci. Math. Sci.} {\bf 120} (2010), 27--33.

\bibitem{i} G. E. Andrews, \emph{The Theory of Partitions},
Encyclopedia of Mathematics and Its Applications,
Cambridge University Press, 1998.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } $n$-color odd composition, $n$-color
composition, generating function, explicit
formula, recurrence formula.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 12 2011
revised version received November 27 2011.
Published in {\it Journal of Integer Sequences}, December 26 2011.

\bigskip
\hrule
\bigskip

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


\end{document}