<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}}, &amp; \mathrm{if} \ n\equiv 0 \ (\mathrm{mod} \ 3); \\
4 \cdot 3^{\frac{n-4}{3}}, &amp;  \mathrm{if} \  n\equiv 1 \ (\mathrm{mod} \ 3);\\
2 \cdot 3^{\frac{n-2}{3}}, &amp;  \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, &amp; \mathrm{if} \ n=5;\\
16 \cdot 3^{\frac{n-8}{3}}, &amp;  \mathrm{if} \  n \equiv 5 \ (\mathrm{mod} \ 6) \text{ and } n&gt;5;\\
M_n, &amp;  \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&gt;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&gt;5$, is
$$O_n=\begin{cases} 
M_n, &amp;  \mathrm{if} \ n\equiv 0 \ (\mathrm{mod} \ 3);\\
3^{\frac{n-1}{3}}, &amp;  \mathrm{if} \ n\equiv 1 \ (\mathrm{mod} \ 6);\\
3^{\frac{n-2}{3}}, &amp;  \mathrm{if} \ n\equiv 2 \ (\mathrm{mod} \ 6);\\
25 \cdot 3^{\frac{n-10}{3}}, &amp;  \mathrm{if} \ n\equiv 4 \ (\mathrm{mod} \ 6);\\
5\cdot 3^{\frac{n-5}{3}}, &amp;  \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}


</pre></body></html>