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