\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}}} \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 Maximum Part-Products of Odd \\ \vskip .11in Palindromic Compositions } \vskip 1cm \large Andrew Kenney and Caroline Shapcott\\ Department of Mathematical Sciences\\ Indiana University South Bend\\ 1700 Mishawaka Avenue\\ South Bend, IN 46634-7111\\ USA \\ \href{mailto:ankenney@iusb.edu}{\tt ankenney@iusb.edu} \\ \href{shapcott@iusb.edu}{\tt shapcott@iusb.edu} \\ \end{center} \vskip .2 in \begin{abstract} We derive explicit formulas for the maximum part-product over the set of palindromic compositions of a given integer and over the set of palindromic compositions of a given integer with only odd parts. These results are extensions of the well-known elementary formula for the maximum part-product over the set of classical partitions. \end{abstract} \section{Introduction} An {\em integer composition of $n$}, or simply a {\em composition of $n$}, is a sequence of positive integers that sum to $n$. A question that frequently arises as a challenge problem (for instance, during math competitions and Putnam exams) is to find the maximum product of such a sequence for a given integer $n$. The following well-known result is noted by Beevers \cite{Beevers} and derived by the second author \cite{Shapcott}, and the continuous analogue of the problem is studied by Goodman \cite{Goodman}. The sequence itself is found in Sloane's Online Encyclopedia of Integer Sequences as sequence number \seqnum{A000792} \cite{Sloane}. We record the result as a lemma for easy reference. \begin{lemma} \label{Mn} The maximum part-product over all compositions of $n$, for $n\geq 2$, is $$M_n= \begin{cases} 3^{\frac{n}{3}}, & \mathrm{if} \ n\equiv 0 \ (\mathrm{mod} \ 3); \\ 4 \cdot 3^{\frac{n-4}{3}}, & \mathrm{if} \ n\equiv 1 \ (\mathrm{mod} \ 3);\\ 2 \cdot 3^{\frac{n-2}{3}}, & \mathrm{if} \ n\equiv 2 \ (\mathrm{mod} \ 3). \end{cases}$$ Note that $M_0=M_1=1$. \end{lemma} A more interesting question to consider is how the part-product is affected when restrictions are placed on the part-sizes. Do\v sli\' c extends the result to the case when the composition (equivalently, partition) is required to have either distinct parts or only odd parts \cite{Doslic}. In this paper, we consider two cases. First, we consider compositions (no longer partitions) that are palindromic, meaning the part-sequence must be the same whether read from left-to-right or right-to-left. Second, we consider the case when a palindromic composition contains only odd parts. The proofs are elementary and are completed through a detailed analysis of cases. Throughout the paper, we will repeatedly use $j$ to denote an arbitrary nonnegative integer, especially when referring to modular equivalence. \section{Palindromic compositions} A {\em palindromic composition of $n$} is a sequence of positive integers or {\em parts} that sum to $n$ and whose part-sequence is the same whether it is read from left-to-right or right-to-left. For example, $(1,1,2,1,1)$ is a palindromic composition of $n=6$. See Heubach and Mansour's comprehensive text for an overview of the literature on palindromic compositions \cite{Heubach0}. Throughout the proofs of Theorems \ref{Pn} and \ref{On}, we will use the term {\em subword of a composition} to mean a list of parts of the composition that are in the order in which they appear in the composition but are not necessarily consecutive within the composition. \begin{theorem} \label{Pn} The maximum part-product over all palindromic compositions of $n$ is $$P_n=\begin{cases} 5, & \mathrm{if} \ n=5;\\ 16 \cdot 3^{\frac{n-8}{3}}, & \mathrm{if} \ n \equiv 5 \ (\mathrm{mod} \ 6) \text{ and } n>5;\\ M_n, & \mathrm{if} \ n \not\equiv 5 \ (\mathrm{mod} \ 6). \end{cases}$$ Note that $M_n$ is the maximum product defined in Lemma \ref{Mn}. \end{theorem} \begin{proof} Let $X_n$ be the set of all compositions of $n$ and let $Y_n$ be the set of all palindromic compositions of $n$. Note that $Y_n\subseteq X_n$; therefore, if there is a composition in $Y_n$ whose product equals $M_n$, then $P_n=M_n$. At this point, we must understand something about the structure of a composition attaining $M_n$. For all $n\geq 2$, the product $M_n$ is attained by a composition of only 2s and 3s. Specifically, the composition contains either zero, one, or two parts of size 2 (depending on the equivalence class of $n$), and the remaining parts of the composition are all parts of size 3. Let $a$ be the number of 2s and $b$ be the number of 3s needed to attain $M_n$. If $a$ and $b$ are both even, or if only one of $a$ and $b$ is odd, then there does exist a palindromic composition in $Y_n$ that attains $M_n$ (for example, $(2,3,2)$, $(3,2,3)$, or $(2,3,3,2)$). However, when $a$ and $b$ are both odd, no such composition exists in $Y_n$. In this situation, $a=1$ and $b=\frac{n-2}{3}=2j+1$, for some nonnegative integer $j$, and therefore $n=6j+5$. Specifically, we have the following six cases: \begin{itemize} \item If $n\equiv 0 \ (\mathrm{mod} \ 6)$, i.e., $n=6j$, then $n\equiv 0 \ (\mathrm{mod} \ 3)$ and we can attain $M_n$ by letting $a=0$ and $b=\frac{6j}{3}=2j$. In this case, we have the palindromic composition consisting of an even number of 3s. \item If $n\equiv 1 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+1$, then $n\equiv 1 \ (\mathrm{mod} \ 3)$ and we can attain $M_n$ by letting $a=2$ and $b=\frac{6j+1-4}{3}=2j-1$. In this case, we have the palindromic composition consisting of an odd number of 3s in the center flanked by one 2 on either side. \item If $n\equiv 2 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+2$, then $n\equiv 2 \ (\mathrm{mod} \ 3)$ and we can attain $M_n$ by letting $a=1$ and $b=\frac{6j+2-2}{3}=2j$. In this case, we have the palindromic composition consisting of one 2 in the center flanked by an equal number of 3s on either side. \item If $n\equiv 3 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+3$, then $n\equiv 0 \ (\mathrm{mod} \ 3)$ and we can attain $M_n$ by letting $a=0$ and $b=\frac{6j+3}{3}=2j+1$. In this case, we have the palindromic composition consisting of an odd number of 3s. \item If $n\equiv 4 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+4$, then $n\equiv 1 \ (\mathrm{mod} \ 3)$ and we can attain $M_n$ by letting $a=2$ and $b=\frac{6j+4-4}{3}=2j$. In this case, we have the palindromic composition consisting of an even number of 3s in the center flanked by one 2 on either side. \item Finally, let $n\equiv 5 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+5$. Suppose, to the contrary, that there exists a palindromic composition that attains $M_n$. Since $n\equiv 2 \ (\mathrm{mod} \ 3)$, we have $a=1$. However, then $b=\frac{6j+5-2}{3}=2j+1$ and we are unable to form a palindromic composition with both an odd number of 3s and an odd number of 2s. \end{itemize} By inspection, we see that $P_5=5$. Therefore, we need only consider the case when $n\equiv 5 \ (\mathrm{mod} \ 6)$ and $n>5$. Note that in this case $n$ is odd and therefore the composition must have a center part; moreover, the center part itself must be odd. Let $\lambda$ be the center part of a palindromic composition attaining the maximum part-product $P_n$. If $\lambda\geq 7$ and $\lambda \equiv 1 \ (\mathrm{mod} \ 4)$, i.e., $\lambda=4j+1$, then $\lambda$ can be replaced with one 1 and $2j$ 2s, in order to obtain a palindromic composition with a greater product. If $\lambda\geq 7$ and $\lambda \equiv 3 \ (\mathrm{mod} \ 4)$, i.e., $\lambda=4j+3$, then $\lambda$ can be replaced with one 3 and $2j$ 2s, in order to obtain a palindromic composition with a greater product. Thus, there is no need for a center part of any size other than 1, 3, or 5. Next consider the side parts. Suppose there are $k$ parts of size 1 on either side of the center part $\lambda$. If $k$ is even, replace the 1s on each side with $\frac{k}{2}$ 2s. If $k$ is odd, replace the 1s on each side with $\frac{k-1}{2}$ 2s and one 1. In this way we obtain a palindromic composition with a greater product, so there is no need for more than one 1 on either side of the center part. If there is a part of size 4 on either side of the center part $\lambda$, replace the subword $(4,4)$ with $(2,2,2,2)$ to obtain a palindromic composition with the same product. If there is a part of size 5 on either side of the center part $\lambda$, replace the subword $(5,5)$ with $(2,3,3,2)$ to obtain a palindromic composition with a greater product. If there is a part of size $m\geq 6$ on either side of the center part, replace each $m$ with $\frac{m}{2}$ 2s if $m$ is even or $\frac{m-1}{2}$ 2s and one 1 if $m$ is odd to obtain a palindromic composition with a greater product. In this way, we see that there is no need for side parts of any size other than 1, 2, or 3. Hence, a palindromic composition attaining the maximum product must have the form $$P_n=1^a \cdot 2^b \cdot 3^c \cdot 5^d$$ where $b$ and $c$ are nonnegative integers and $a$ and $d$ are nonnegative integers such that $0\leq a \leq 3$ and $0\leq d \leq 1$. Now let us assume that $n\geq 11$. Suppose that $d=1$, meaning that the center part $\lambda$ is a 5. If there is a pair of 2s (one on either side of $\lambda$), then the subword $(2,5,2)$ can be replaced with $(3,3,3)$ to obtain a palindromic composition with a greater product. If there is not a pair of 2s, then there must be at least one pair of 3s (since $n\geq 11$), in which case the subword $(3,5,3)$ can be replaced with $(2,2,3,2,2)$ to obtain a palindromic composition with a greater product. Therefore, the center part of a composition attaining $P_n$ is not equal to 5 and we must have $d=0$. Suppose that the center part $\lambda$ is a 1. If there is a pair of 3s (one on either side of $\lambda$), then the subword $(3,1,3)$ can be replaced with $(2,3,2)$ to obtain a palindromic composition with a greater product. If there is not a pair of 3s, then there must be at least two pairs of 2s (since $n\geq 11$ and there is not more than one 1 on each side), in which case the subword $(2,2,1,2,2)$ can be replaced with $(3,3,3)$ to obtain a palindromic composition with a greater product. Therefore, the center part cannot be a 1; moreover, it must be true that $a$ is even, i.e., $a=0$ or $a=2$. If $a=2$, meaning there is one part of size 1 on each side of the center part, then the subword $(1,2,2,1)$ can be replaced with $(3,3)$ or the subword $(1,3,3,1)$ can be replaced with $(2,2,2,2)$. In either case, a palindromic composition with a greater product is attained. Therefore, the center part of a composition attaining $P_n$ is not equal to 1 and we must have $a=0$. Since $\lambda\neq 1$ and $\lambda\neq 5$, there is no other choice but for the center part to be a 3, and since $a=0$ and $d=0$, the remaining parts of the composition must be either 2s or 3s: $$P_n=2^b \cdot 3^c.$$ Since the center part is 3 and we must maintain the palindromic structure, $b$ must be even. If $b\geq 6$, then there are at least three 2s on each side of the center part, in which case the subword $(2,2,2,2,2,2)$ can be replaced with $(3,3,3,3)$. Therefore, either $b=0$, $b=2$, or $b=4$. If $b=0$, then $3c=n=6j+5=3(2j)+2$ for some integer $j$, which is a contradiction. If $b=2$, then $4+3c=n=6j+5$ and $3c=6j+1=3(2j)+1$ for some integer $j$, which is another contradiction. The only remaining possibility is that $b=4$, in which case $c=\frac{n-8}{3}$. \end{proof} \section{Odd palindromic compositions} An {\em odd palindromic composition of $n$} is a palindromic composition containing only odd parts. For example, $(1,1,3,1,1)$ is an odd palindromic composition of $n=7$. \begin{theorem} \label{On} The maximum part-product over all odd palindromic compositions of $n$, for $n>5$, is $$O_n=\begin{cases} M_n, & \mathrm{if} \ n\equiv 0 \ (\mathrm{mod} \ 3);\\ 3^{\frac{n-1}{3}}, & \mathrm{if} \ n\equiv 1 \ (\mathrm{mod} \ 6);\\ 3^{\frac{n-2}{3}}, & \mathrm{if} \ n\equiv 2 \ (\mathrm{mod} \ 6);\\ 25 \cdot 3^{\frac{n-10}{3}}, & \mathrm{if} \ n\equiv 4 \ (\mathrm{mod} \ 6);\\ 5\cdot 3^{\frac{n-5}{3}}, & \mathrm{if} \ n\equiv 5 \ (\mathrm{mod} \ 6). \end{cases}$$ Note that $M_n$ is again the maximum product defined in Lemma \ref{Mn}. By direct computation, $O_1=1$, $O_2=1$, $O_3=3$, $O_4=1$, and $O_5=5$. \end{theorem} \begin{proof} Consider an odd palindromic composition of $n$ that attains the maximum product $O_n$. If such a composition contains a part of size $m=6j+\ell \geq 7$, with $\ell=1,3,5$, then we can replace $m$ by one $\ell$ and $2j$ 3s, which results in a greater product in each case while maintaining the palindromic structure. If $m$ is a center part, then we can replace it with the part sequence $(3,\dots,3, \ell, 3, \dots, 3)$ which again maintains the palindromic structure. Therefore, there is no need for parts of any size other than 1, 3, or 5 and an odd palindromic composition attaining the maximum product must have the form $$O_n=1^a \cdot 3^b \cdot 5^c$$ where $a$, $b$, and $c$ are nonnegative integers. Let $\lambda$ be the center part of a composition attaining the maximum product. Suppose there are $k$ parts of size 1 on either side of $\lambda$. Replace every three 1s (on each side) with a 3 instead. In other words, if $k\equiv j \ (\mathrm{mod} \ 3)$, replace the $k$ parts of size 1 with $\frac{k-j}{3}$ 3s and $j$ 1s. In this way, we obtain a palindromic composition with a greater product, so there is no need for more than two 1s on either side of the center part and we must have $0\leq a\leq 5$. Now suppose there are $k$ parts of size 5 on either side of $\lambda$. Replace every two 5s (on each side) with three 3s and a 1 instead. In other words, if $k\equiv j \ (\mathrm{mod} \ 2)$, replace the $k$ parts of size 5 with $\frac{3(k-j)}{2}$ 3s, $\frac{k-j}{2}$ 1s, and $j$ 5s. In this way, we obtain a palindromic composition with a greater product, so there is no need for more than one 5 on either side of the center part and we must have $0\leq c\leq 3$. We now consider several cases according to the value of $n$. In each case, there is a finite number of possible sets of part sizes that meet the restrictions on $a$ and $c$ and that, in addition, allow a palindromic composition of $n$ to be constructed. For each set of part sizes, we choose a model arrangement that achieves a palindromic structure for the composition being constructed; however, note that there may also be other satisfactory arrangements. Specifically, we have the following five cases: \begin{itemize} \item If $n\equiv 0 \ (\mathrm{mod} \ 3)$, i.e., $n=3j$, then there is an odd palindromic composition that attains the maximum product $M_n$ from Lemma \ref{Mn}, namely the composition containing $\frac{n}{3}$ 3s. \item If $n\equiv 2 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+2$, then in particular $n$ is even and there is no center part. Therefore, the possible values of $a$ and $c$ are $a=0,2,4$ and $c=0,2$. However, only two of the six resulting combinations are feasible under the given restrictions. (To illustrate the reasoning, suppose $a=0$ and $c=0$. Then the composition must be composed of only 3s, yet $n=6j+2$ is not divisible by 3. Reasoning for the other combinations follows similarly but is not included here.) The feasible combinations are as follows: \subitem $a=4$ and $c=2$, creating the subword $(1,1,5,5,1,1)$ \subitem $a=2$ and $c=0$, creating the subword $(1,3,3,3,3,1)$ Surrounding these two subwords are additional parts of size 3 to fill out the composition. The second subword has a greater product and therefore reveals the maximum part-product to be $O_n=1^2 \cdot 3^{\frac{n-2}{3}}$. Note that the subwords created in this case (and similar for each following case) have the same sum in order to enable direct comparison. \item If $n\equiv 4 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+4$, then again $n$ is even and there is no center part. Therefore, the possible values of $a$ and $c$ are again $a=0,2,4$ and $c=0,2$. However, only two of the six resulting combinations are feasible under the given restrictions: \subitem $a=0$ and $c=2$, creating the subword $(5,5)$ \subitem $a=4$ and $c=0$, creating the subword $(1,1,3,3,1,1)$ Surrounding these two subwords are additional parts of size 3 to fill out the composition. The first subword has a greater product and therefore reveals the maximum part-product to be $O_n= 3^{\frac{n-10}{3}}\cdot 5^2$. \item If $n\equiv 1 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+1$, then in particular $n$ is odd and must have a center part. Taking each possible choice of the center part $\lambda$ (which can equal 1, 3, or 5) into consideration, there are six feasible combinations: \subitem $\lambda=5$, $a=4$, and $c=2$, creating the subword $(1,1,5,5,5,1,1)$ \subitem $\lambda=5$, $a=2$, and $c=0$, creating the subword $(1,3,3,5,3,3,1)$ \subitem $\lambda=3$, $a=0$, and $c=2$, creating the subword $(5,3,3,3,5)$ \subitem $\lambda=3$, $a=4$, and $c=0$, creating the subword $(1,1,3,3,3,3,3,1,1)$ \subitem $\lambda=1$, $a=2$, and $c=2$, creating the subword $(1,5,3,1,3,5,1)$ \subitem $\lambda=1$, $a=0$, and $c=0$, creating the subword $(3,3,3,1,3,3,3)$ Surrounding these six subwords are additional parts of size 3 to fill out the composition. The sixth subword has the greatest product and therefore reveals the maximum part-product to be $O_n= 1^1\cdot 3^{\frac{n-1}{3}}$. \item If $n\equiv 5 \ (\mathrm{mod} \ 6)$, i.e., $n=6j+5$, then again $n$ is odd and must have a center part. Taking each possible choice of the center part $\lambda$ into consideration, there are six feasible combinations: \subitem $\lambda=5$, $a=2$, and $c=2$, creating the subword $(1,5,5,5,1)$ \subitem $\lambda=5$, $a=0$, and $c=0$, creating the subword $(3,3,5,3,3)$ \subitem $\lambda=3$, $a=4$, and $c=2$, creating the subword $(1,1,5,3,5,1,1)$ \subitem $\lambda=3$, $a=2$, and $c=0$, creating the subword $(1,3,3,3,3,3,1)$ \subitem $\lambda=1$, $a=0$, and $c=2$, creating the subword $(5,3,1,3,5)$ \subitem $\lambda=1$, $a=4$, and $c=0$, creating the subword $(1,1,3,3,1,3,3,1,1)$ Surrounding these six subwords are additional parts of size 3 to fill out the composition. The second subword has the greatest product and therefore reveals the maximum part-product to be $O_n= 3^{\frac{n-5}{3}}\cdot 5^1$. \qedhere \end{itemize} \end{proof} %% \section{Remarks} In his paper, Do\v sli\' c analyzes partitions with distinct parts \cite{Doslic}. A natural extension to our results would be to consider palindromic compositions restricted by some suitable definition of ``distinct parts.'' For example, one could consider palindromic compositions that have distinct parts on either side of a center part, either allowing or disallowing the case when a composition has no center part. If a center part is required, a discernable pattern for the maximum part-product appears; however, the pattern is quite complex and its proof would certainly require a different approach than the method of cases employed in this paper. \begin{thebibliography}{9} \bibitem{Sloane} {\em The On-Line Encyclopedia of Integer Sequences}, \newblock published electronically at \newline \url{http://oeis.org}, 2014. \bibitem{Beevers} B.~S.\ Beevers, \newblock The greatest product, \newblock {\em Math. Gazette}, {\bf 77} (1993), 91. \bibitem{Doslic} T.\ Do{\v{s}}li{\'c}, \newblock Maximum product over partitions into distinct parts, \newblock {\em J. Integer Seq.}, {\bf 8} (2005), \href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Doslic/doslic15.html}{Article 05.5.8}. \bibitem{Goodman} T.~N.~T.\ Goodman, \newblock Notes: maximum products and {$\lim\big(1 + \frac{1}{n}\big)^n = e$}. \newblock {\em Amer. Math. Monthly}, {\bf 93} (1986), 638--640. \bibitem{Heubach0} S.\ Heubach and T.\ Mansour, \newblock {\em Combinatorics of Compositions and Words}, \newblock CRC Press, 2010. \bibitem{Shapcott} C.\ Shapcott, \newblock {\em Part-Products of Random Integer Compositions}, \newblock PhD thesis, Drexel University, 2012. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A17; Secondary 05A15. \noindent \emph{Keywords: } integer composition, palindromic composition, odd composition, maximum product. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000792}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 2 2014; revised versions received January 2 2015; January 4 2015. Published in {\it Journal of Integer Sequences}, January 25 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}