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