\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} .