\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}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\usepackage{slashbox}
\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
$n$-Color Odd Self-Inverse Compositions
}
\vskip 1cm
\large
Yu-hong Guo\footnote{This work is supported by the
National Natural Science Foundation of China (Grant No.\ 11461020)
and the Fund of the Education Department of
Gansu Province (No.\ 2010-04.)}\\
School of Mathematics and Statistics \\
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 self-inverse composition is an $n$-color
self-inverse composition with odd parts. In this paper, we obtain
generating functions, explicit formulas, and recurrence formulas for
$n$-color odd self-inverse compositions.
\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$, $211$, $1111$ and the compositions are $4$, $31$, $13$, $22$, $211$, $121$,
$112$, $1111$.
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}$. In analogy with MacMahon's ordinary
compositions, Agarwal $\cite{c}$ defined an
$n$-color composition as an $n$-color ordered partition. Thus,
for example, there are $8$ $n$-color compositions of $3$, viz.,
\[
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}.
\]
More properties of $n$-color compositions were given in
$\cite{d,e}$.
\begin{definition}${(\cite{a})}$
A composition is said to be self-inverse when the parts of the
composition read from left to right are identical with the parts when read
from right to left.
\end{definition}
In analogy with the definition above for classical self-inverse
compositions, Narang and Agarwal $\cite{f}$ defined an $n$-color
self-inverse composition and gave some properties of them.
\begin{definition}${(\cite{f})}$
An $n$-color odd composition is an $n$-color composition with odd
parts.
\end{definition}
For example there are $8$ $n$-color self-inverse compositions of
$4$, viz.,
\[
4_{1}, 4_{2},4_{3},4_{4}, 2_{1}2_{1},
2_{2}2_{2},1_{1}2_{1}1_{1},1_{1}2_{2}1_{1}.
\]
In 2010, the author $\cite{g}$ also defined an $n$-color even self-inverse
composition and gave some properties.
\begin{definition}${(\cite{g})}$
An $n$-color even composition is an $n$-color composition whose parts
are even.
\end{definition}
\begin{definition}${(\cite{g})}$
An $n$-color even composition whose parts read from left to right are
identical with when read from right to left is called an $n$-color
even self-inverse composition.
\end{definition}
Thus, for example, there are $8$ $n$-color even self-inverse
compositions of $4$, viz.,
\[
4_{1}, 4_{2}, 4_{3}, 4_{4}, 2_{1}2_{1}, 2_{1}2_{2}, 2_{2}2_{1},
2_{2}2_{2}.
\]
And there are $6$ $n$-color even self-inverse compositions of $4$,
viz.,
\[
4_{1}, 4_{2},4_{3},4_{4}, 2_{1}2_{1}, 2_{2}2_{2}.
\]
Recently, the author $\cite{h}$ studied $n$-color odd compositions.
\begin{definition}${(\cite{h})}$
An $n$-color odd composition is an $n$-color composition whose parts
are odd.
\end{definition}
Thus, for example, there are $7$ $n$-color odd compositions of $4$,
viz.,
\[
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}.
\]
In this paper, we shall study $n$-color odd self-inverse
compositions.
\begin{definition}
An $n$-color odd composition whose parts read from left to right are
identical with when read from right to left is called an $n$-color odd
self-inverse composition.
\end{definition}
Thus, for example, there are $4$ $n$-color odd self-inverse
compositions of $6$, viz.,
\[
3_{1}3_{1}, 3_{2}3_{2}, 3_{3}3_{3}, 1_{1}1_{1}1_{1}1_{1}1_{1}1_{1}.
\]
\par
In section \ref{sec2} we shall give explicit formulas, recurrence formulas, generating functions
for $n$-color odd self-inverse compositions.
The author $\cite{h}$ proved the following theorems.
\begin{theorem}${(\cite{h})}$
Let $C_{o}(m,q)$ and $C_{o}(q)$ denote the enumerative generating
functions for $C_{o}(m,\nu)$ and $C_{o}(\nu)$, respectively, where
$C_{o}(m,\nu)$ is the number of $n$-color odd compositions of $\nu$
into $m$ parts and $C_{o}(\nu)$ is the number of $n$-color odd
compositions of $\nu$. Then
\begin{eqnarray}\label{squaresum}
&&C_{o}(m,q)=\frac{q^{m}(1+q^{2})^{m}}{(1-q^{2})^{2m}},\\
&&C_{o}(q)=\frac{q+q^{3}}{1-q-2q^{2}-q^{3}+q^{4}},\\
&&C_{o}(m,\nu)=\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}, \label{a}\\
&&C_{o}(\nu)=\sum_{m \leq \nu}
~\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}
\label{b}.
\end{eqnarray}
where $(\nu-m)$ is even, and $(\nu-m) \geq 0$; $0\leq i,j$ are
integers.
\end{theorem}
\begin{theorem}${(\cite{h})}$ \label{th1}
Let $C_{o}(\nu)$ denote the number of $n$-color odd compositions of
$\nu$. Then
\begin{eqnarray*}
&&C_{o}(1)=1, C_{o}(2)=1, C_{o}(3)=4, C_{o}(4)=7~~and\\
&&C_{o}(\nu) = C_{o}(\nu-1)+2C_{o}(\nu-2)+C_{o}(\nu-3)-C_{o}(\nu-4)~for~\nu>4.
\end{eqnarray*}
\end{theorem}
\section{Main results}\label{sec2}
In this section, we first prove the following explicit formulas for
the number of $n$-color odd self-inverse compositions.
\begin{theorem}\label{th2}
Let $S(O, \nu)$ denote the number of $n$-color odd self-inverse
compositions of $\nu$. Then
\begin{eqnarray*}
(1)~~S(O,
2\nu+1)=(2\nu+1)+\sum_{t=1}^{2\nu-1}\sum_{m\leq\frac{2\nu+1-t}{2}}\sum_{i+j=\frac{2\nu+1-t-2m}{4}}t{{2m+i-1}\choose{2m-1}}{{m}\choose{j}},
\end{eqnarray*}
where $\nu=0,1,2,\ldots$;~~~$t=2k+1,k=0,1,2,\ldots,(\nu-1)$;~~$0
\leq\frac{2\nu+1-t-2m}{2}$ is even; $0\leq i,j$ are integers.
\begin{eqnarray*}
(2) ~~S(O, 2\nu)=\sum_{m \leq \nu}
~\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}},
\end{eqnarray*}
where $0 \leq\nu-m$ is even, and $0\leq i,j$ are integers.
\end{theorem}
\begin{proof} $(1)$~~~Obviously, an odd number which is
$2\nu+1~(\nu=0,1,2,\ldots)$ can have odd self-inverse $n$-color
compositions only when the number of parts is odd. There are
$2\nu+1$ $n$-color odd self-inverse compositions when the number of
parts is only one. An odd self-inverse compositions of $2\nu+1$ into
$2m+1~(m\geq1)$ parts can be read as a central part, say, $t$ (where
$t$ is odd) and two identical odd $n$-color compositions of
$\frac{2\nu+1-t}{2}$ into $m$ parts on each side of the central
part. The number of odd $n$-color compositions of
$\frac{2\nu+1-t}{2}$ into $m$ parts is $C_{o}(m,\frac{2\nu+1-t}{2})$
by equation (\ref{a}). Now the central part can appear in $t$ ways.
Therefore, the number of $n$-color odd self-inverse compositions of
$2\nu+1$ is
\begin{eqnarray*}
S(O,
2\nu+1)&=&(2\nu+1)+\sum_{t=1}^{2\nu-1}\sum_{m\leq\frac{2\nu+1-t}{2}}t
C_{o}\left(m,\frac{2\nu+1-t}{2}\right)\\
&=&(2\nu+1)+\sum_{t=1}^{2\nu-1}\sum_{m\leq\frac{2\nu+1-t}{2}}\sum_{i+j=\frac{2\nu+1-t-2m}{4}}t{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}.
\end{eqnarray*}
\par
~$(2)$ ~~For even numbers $2\nu~(\nu=1, 2, \ldots)$, we can have odd
self-inverse $n$-color compositions only when the number of parts is
even, and the two identical odd $n$-color compositions are exactly
odd $n$-color compositions of $\nu$, from equation (\ref{b}) we see that
the number of these is
\[
\sum_{m\leq
\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}.
\]
\par
Hence, the number of $n$-color odd self-inverse compositions of
$2\nu$ is
\begin{eqnarray*}
S(O, 2\nu)=\sum_{m\leq
\nu}\sum_{i+j=\frac{\nu-m}{2}}{{2m+i-1}\choose{2m-1}}{{m}\choose{j}}.
\end{eqnarray*}
We complete the proof of this theorem.
\end{proof}
From the proof of this theorem we can see that odd $n$ have
$n$-color odd self-inverse compositions where the number of parts is
odd. And even $n$ have $n$-color odd self-inverse
compositions where the number of parts is even. Let $S_{o}(\nu,m)$
denote the number of $n$-color odd self-inverse compositions of
$\nu$ into $m$ parts. Then we can get the following formula easily.
\[
S_{o}(2k+1, 2l+1)=\sum_{t=1}^{2k-1}\sum_{i+j=\frac{2k+1-t-2l}{4}}{{2l+i-1}\choose{2l-1}}{{l}\choose{j}}.
\]
where $t$ is odd, $k,l$ are integers and $k,l\geq 0$.
\[
S_{o}(2k, 2l)=
\sum_{i+j=\frac{k-l}{2}}{{2l+i-1}\choose{2l-1}}{{l}\choose{j}}.
\]
where $k,l$ are integers and $k,l\geq 0$.
Now $S_{o}(\nu,m)$ with $\nu, m=1,2,\ldots,20$ is given in Tables
\ref{tab:time} and \ref{tab:time1}.
\begin{table}[htp]
\centering
\caption{$S_{o}(\nu,m)$ when both $\nu$ and $m$ are
odd}\label{tab:time}
\begin{tabular}{c|cccccccccc|c}
\hline
\backslashbox{$\nu$}{$m$} &1 &3 &5 &7 &9 &11 &13 &15 &17 &19 &
$s_{\nu}$
\\
\hline
1 &1 & 0 &0 &0 &0 &0 &0 &0 &0 &0 &1\\
3 &3 & 1 &0 &0 &0 &0 &0 &0 &0 &0 &4\\
5 &5 & 3 &1 &0 &0 &0 &0 &0 &0 &0 &9\\
7 &7 & 8 &3 &1 &0 &0 &0 &0 &0 &0 &19\\
9 &9 & 16 &11 &3 &1 &0 &0 &0 &0 &0 &40\\
11 &11 & 29 &25 &16 &3 &1 &0 &0 &0 &0 &83\\
13 &13 & 49 &56 &34 &17 &3 &1 &0 &0 &0 &173\\
15 &15 & 72 &110 &96 &43 &20 &3 &1 &0 &0 &360\\
17 &17 &104 &206 &200 &143 &52 &23 &3 &1 &0 &749\\
19 &19 &145 &346 &442 &317 &199 &61 &26 &3 &1 &1559\\
\hline
\end{tabular}
\end{table}
From Tables \ref{tab:time} and \ref{tab:time1} we can see the
recurrence formulas for the number of the $n$-color odd self-inverse
compositions of $\nu$. So we prove the following recurrence
relations.
\begin{table}[h]
\centering
\caption{$S_{o}(\nu,m)$ when both $\nu$ and $m$ are even}\label{tab:time1}
\begin{tabular}{c|cccccccccc|c}
\hline
\backslashbox{$\nu$}{$m$} &2 &4 &6 &8 &10 &12 &14 &16 &18 &20 &
$t_{\nu}$
\\
\hline
2 &1 & 0 &0 &0 &0 &0 &0 &0 &0 &0 &1\\
4 &0 & 1 &0 &0 &0 &0 &0 &0 &0 &0 &1\\
6 &3 & 0 &1 &0 &0 &0 &0 &0 &0 &0 &4\\
8 &0 & 6 &0 &1 &0 &0 &0 &0 &0 &0 &7\\
10 &5 & 0 &9 &0 &1 &0 &0 &0 &0 &0 &15\\
12 &0 & 19 &0 &12 &0 &1 &0 &0 &0 &0 &32\\
14 &7 & 0 &42 &0 &15 &0 &1 &0 &0 &0 &65\\
16 &0 & 44 &0 &74 &0 &18 &0 &1 &0 &0 &137\\
18 &9 &0 &138 &0 &115 &0 &21 &0 &1 &0 &284\\
20 &0 &85 &0 &316 &0 &165 &0 &24 &0 &1 &591\\
\hline
\end{tabular}
\end{table}
\begin{theorem}\label{th3}
Let $s_{\nu}$ and $t_{\nu}$ denote the number of $n$-color odd
self-inverse compositions for $2\nu+1$ and $2\nu$, respectively.
Then
\begin{eqnarray*}
(1)~~&s_{0}&=1,~ s_{1}=4, ~s_{2}=9,~ s_{3}=19 ~~and\\
&s_{\nu}&=s_{\nu-1}+2s_{\nu-2}+s_{\nu-3}-s_{\nu-4}~~~for~~~\nu>3\\
(2)~~ &t_{1}&=1,~t_{2}=1, ~ t_{3}=4, ~t_{4}=7~~ and \\
&t_{\nu}&=t_{\nu-1}+2t_{\nu-2}+t_{\nu-3}-t_{\nu-4}~~~for~~~\nu>4.
\end{eqnarray*}
\end{theorem}
\begin{proof} (Combinatorial)~~$(1)$~ To prove that
$s_{\nu}=s_{\nu-1}+2s_{\nu-2}+s_{\nu-3}-s_{\nu-4}$, we split the
$n$-color odd self-inverse
compositions enumerated by $s_{\nu}+s_{\nu-4}$ into four classes:
\medskip
\noindent (A)~$s_{\nu}$ with $1_{1}$ on both ends.\\
(B)~$s_{\nu}$ with $3_{3}$ on both ends.\\
(C)~$s_{\nu}$ with $h_{t}$ on both ends, $h>1$, $1\leq t \leq h-2$
and $n$-color odd self-inverse
compositions of $2\nu+1$ of form $(2\nu+1)_{u}$, $1\leq u \leq 2\nu-3$.\\
(D)~$s_{\nu}$ with $h_{t}$ on both ends except $3_{3}$, $h>1$,
$h-1\leq t \leq h$, $(2\nu+1)_{u}$, $2\nu-2 \leq u \leq2\nu+1$ and
those enumerated by $s_{\nu-4}$. \vskip 10pt
\par
We transform the $n$-color odd self-inverse compositions in class
(A) by deleting $1_{1}$ on both ends. This produces $n$-color odd
self-inverse compositions enumerated by $s_{\nu-1}$. Conversely, for
any $n$-color odd composition enumerated by $s_{\nu-1}$ we add
$1_{1}$ on both ends to produce the elements of the class (A). In
this way we establish that there are exactly $s_{\nu-1}$ elements in
the class (A).
\par
Similarly, we can produce $s_{\nu-3}$ $n$-color odd self-inverse
compositions in class (B) by deleting $3_{3}$ on both ends.
\par
Next, we transform the $n$-color odd self-inverse compositions
in class (C) by subtracting $2$ from $h$, that is, replacing $h_{t}$
by $(h-2)_{t}$ and subtracting $4$ from $2\nu+1$ of $(2\nu+1)_{u}$,
$1\leq u \leq 2\nu-3 $. This transformation also establishes the
fact that there are exactly $s_{\nu-2}$ elements in class (C).
\par
Finally, we transform the elements in class (D) as follows: Subtract
$2_{2}$ from $h_{t}$ on both ends, that is, replace $h_{t}$ by
$(h-2)_{(t-2)}$, $h>3$, $h-1\leq t\leq h$, while replace $h_{t}$ by
$(h-2)_{(t-1)}$ when $h=3$, $ t= 2$. We will get those $n$-color
odd self-inverse compositions of $2\nu-3$ with $h_{t}$ on both
ends,~$h-1\leq t\leq h$ except self-inverse odd compositions in one
part. We also replace $(2\nu+1)_{u}$ by $(2\nu-3)_{u-4}$, $2\nu-2
\leq u \leq 2\nu+1$. To get the remaining $n$-color odd compositions
from $s_{\nu-4}$ we add $2$ to both ends, that is, replace $h_{t}$
by $(h+2)_{t}$. For $n$-color odd self-inverse compositions into one
part we add $4$ ,that is, replace $(2\nu-7)_{t}$ by $(2\nu-3)_{t},
1\leq t \leq 2\nu-7 $. We see that the number of $n$-color odd
self-inverse compositions in class (D) is also equal to $s_{\nu-2}$.
Hence, we have $s_{\nu}+s_{\nu-4}=s_{\nu-1}+2s_{\nu-2}+s_{\nu-3}$.
viz., $s_{\nu}=s_{\nu-1}+2s_{\nu-2}+s_{\nu-3}-s_{\nu-4}$.
$(2)$ From Theorem \ref{th1} and Theorem \ref{th2}, we obtain the
recurrence formula of $t_{\nu}$ easily. Thus, we complete the proof.
\end{proof}
We easily get the following generating functions by the
recurrence relations.
\begin{corollary}\label{th7}
\begin{eqnarray*}
&(1)& ~~~~~~\sum_{\nu=0}^{\infty}s_{\nu}q^{\nu}=\frac{(1+q)^{3}}{1-q-2q^{2}-q^{3}+q^{4}}.\\
&(2)& ~~~~~~\sum_{\nu=1}^{\infty}t_{\nu}q^{\nu}=\frac{q+q^{3}}{1-q-2q^{2}-q^{3}+q^{4}}.
\end{eqnarray*}
\end{corollary}
\section{Acknowledgments}\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}{99}
\bibitem{b}{A. K. Agarwal and G. E. Andrews, Rogers-Ramanujan identities for partition 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{j} G. E. Andrews, \emph{The Theory of Partitions},
Encyclopedia of Mathematics and Its Applications,
Cambridge University Press, 1998.
\bibitem{e} {Yu-Hong Guo, Some identities between partitions and compositions, \emph{Acta Math. Sinica (Chin. Ser.)} {\bf 50} (2007), 707--710.}
\bibitem{g} {Yu-Hong Guo, $N$-colour even self-inverse compositions, \emph{Proc. Indian Acad. Sci. Math. Sci.} {\bf 120} (2010), 27--33.}
\bibitem{h} Yu-Hong Guo, Some $n$-color compositions, \emph{J. Integer
Sequences} {\bf 15} (2012),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Guo/guo4.html}{Article 12.1.2}.
\bibitem{i} B. Hopkins, Spotted tilling and $n$-color compositions,
\emph{Integers} {\bf 12B} (2012/13), Article A6.
\bibitem{a} P. A. MacMahon, \emph{Combinatory Analysis}, AMS Chelsea
Publishing, 2001.
\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.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: 05A17.
\noindent \emph{Keywords: } $n$-color odd self-inverse composition,
generating function, explicit formula, recurrence formula.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received November 18 2013;
revised versions received May 5 2014; September 16 2014.
Published in {\it Journal of Integer Sequences}, November 4 2014.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}